in s2/shapeindex.go [994:1127]
func (s *ShapeIndex) updateEdges(pcell *PaddedCell, edges []*clippedEdge, t *tracker, disjointFromIndex bool) {
// This function is recursive with a maximum recursion depth of 30 (maxLevel).
// Incremental updates are handled as follows. All edges being added or
// removed are combined together in edges, and all shapes with interiors
// are tracked using tracker. We subdivide recursively as usual until we
// encounter an existing index cell. At this point we absorb the index
// cell as follows:
//
// - Edges and shapes that are being removed are deleted from edges and
// tracker.
// - All remaining edges and shapes from the index cell are added to
// edges and tracker.
// - Continue subdividing recursively, creating new index cells as needed.
// - When the recursion gets back to the cell that was absorbed, we
// restore edges and tracker to their previous state.
//
// Note that the only reason that we include removed shapes in the recursive
// subdivision process is so that we can find all of the index cells that
// contain those shapes efficiently, without maintaining an explicit list of
// index cells for each shape (which would be expensive in terms of memory).
indexCellAbsorbed := false
if !disjointFromIndex {
// There may be existing index cells contained inside pcell. If we
// encounter such a cell, we need to combine the edges being updated with
// the existing cell contents by absorbing the cell.
iter := s.Iterator()
r := iter.LocateCellID(pcell.id)
if r == Disjoint {
disjointFromIndex = true
} else if r == Indexed {
// Absorb the index cell by transferring its contents to edges and
// deleting it. We also start tracking the interior of any new shapes.
s.absorbIndexCell(pcell, iter, edges, t)
indexCellAbsorbed = true
disjointFromIndex = true
} else {
// DCHECK_EQ(SUBDIVIDED, r)
}
}
// If there are existing index cells below us, then we need to keep
// subdividing so that we can merge with those cells. Otherwise,
// makeIndexCell checks if the number of edges is small enough, and creates
// an index cell if possible (returning true when it does so).
if !disjointFromIndex || !s.makeIndexCell(pcell, edges, t) {
// TODO(roberts): If it turns out to have memory problems when there
// are 10M+ edges in the index, look into pre-allocating space so we
// are not always appending.
childEdges := [2][2][]*clippedEdge{} // [i][j]
// Compute the middle of the padded cell, defined as the rectangle in
// (u,v)-space that belongs to all four (padded) children. By comparing
// against the four boundaries of middle we can determine which children
// each edge needs to be propagated to.
middle := pcell.Middle()
// Build up a vector edges to be passed to each child cell. The (i,j)
// directions are left (i=0), right (i=1), lower (j=0), and upper (j=1).
// Note that the vast majority of edges are propagated to a single child.
for _, edge := range edges {
if edge.bound.X.Hi <= middle.X.Lo {
// Edge is entirely contained in the two left children.
a, b := s.clipVAxis(edge, middle.Y)
if a != nil {
childEdges[0][0] = append(childEdges[0][0], a)
}
if b != nil {
childEdges[0][1] = append(childEdges[0][1], b)
}
} else if edge.bound.X.Lo >= middle.X.Hi {
// Edge is entirely contained in the two right children.
a, b := s.clipVAxis(edge, middle.Y)
if a != nil {
childEdges[1][0] = append(childEdges[1][0], a)
}
if b != nil {
childEdges[1][1] = append(childEdges[1][1], b)
}
} else if edge.bound.Y.Hi <= middle.Y.Lo {
// Edge is entirely contained in the two lower children.
if a := s.clipUBound(edge, 1, middle.X.Hi); a != nil {
childEdges[0][0] = append(childEdges[0][0], a)
}
if b := s.clipUBound(edge, 0, middle.X.Lo); b != nil {
childEdges[1][0] = append(childEdges[1][0], b)
}
} else if edge.bound.Y.Lo >= middle.Y.Hi {
// Edge is entirely contained in the two upper children.
if a := s.clipUBound(edge, 1, middle.X.Hi); a != nil {
childEdges[0][1] = append(childEdges[0][1], a)
}
if b := s.clipUBound(edge, 0, middle.X.Lo); b != nil {
childEdges[1][1] = append(childEdges[1][1], b)
}
} else {
// The edge bound spans all four children. The edge
// itself intersects either three or four padded children.
left := s.clipUBound(edge, 1, middle.X.Hi)
a, b := s.clipVAxis(left, middle.Y)
if a != nil {
childEdges[0][0] = append(childEdges[0][0], a)
}
if b != nil {
childEdges[0][1] = append(childEdges[0][1], b)
}
right := s.clipUBound(edge, 0, middle.X.Lo)
a, b = s.clipVAxis(right, middle.Y)
if a != nil {
childEdges[1][0] = append(childEdges[1][0], a)
}
if b != nil {
childEdges[1][1] = append(childEdges[1][1], b)
}
}
}
// Now recursively update the edges in each child. We call the children in
// increasing order of CellID so that when the index is first constructed,
// all insertions into cellMap are at the end (which is much faster).
for pos := 0; pos < 4; pos++ {
i, j := pcell.ChildIJ(pos)
if len(childEdges[i][j]) > 0 || len(t.shapeIDs) > 0 {
s.updateEdges(PaddedCellFromParentIJ(pcell, i, j), childEdges[i][j],
t, disjointFromIndex)
}
}
}
if indexCellAbsorbed {
// Restore the state for any edges being removed that we are tracking.
t.restoreStateBefore(s.pendingAdditionsPos)
}
}