func()

in s2/shapeindex.go [1131:1243]

• 64 lines of code
• 19 McCabe index (conditional complexity)

func (s *ShapeIndex) makeIndexCell(p *PaddedCell, edges []*clippedEdge, t *tracker) bool {
	// If the cell is empty, no index cell is needed. (In most cases this
	// situation is detected before we get to this point, but this can happen
	// when all shapes in a cell are removed.)
	if len(edges) == 0 && len(t.shapeIDs) == 0 {
		return true
	}

	// Count the number of edges that have not reached their maximum level yet.
	// Return false if there are too many such edges.
	count := 0
	for _, ce := range edges {
		if p.Level() < ce.faceEdge.maxLevel {
			count++
		}

		if count > s.maxEdgesPerCell {
			return false
		}
	}

	// Possible optimization: Continue subdividing as long as exactly one child
	// of the padded cell intersects the given edges. This can be done by finding
	// the bounding box of all the edges and calling ShrinkToFit:
	//
	// cellID = p.ShrinkToFit(RectBound(edges));
	//
	// Currently this is not beneficial; it slows down construction by 4-25%
	// (mainly computing the union of the bounding rectangles) and also slows
	// down queries (since more recursive clipping is required to get down to
	// the level of a spatial index cell). But it may be worth trying again
	// once containsCenter is computed and all algorithms are modified to
	// take advantage of it.

	// We update the InteriorTracker as follows. For every Cell in the index
	// we construct two edges: one edge from entry vertex of the cell to its
	// center, and one from the cell center to its exit vertex. Here entry
	// and exit refer the CellID ordering, i.e. the order in which points
	// are encountered along the 2 space-filling curve. The exit vertex then
	// becomes the entry vertex for the next cell in the index, unless there are
	// one or more empty intervening cells, in which case the InteriorTracker
	// state is unchanged because the intervening cells have no edges.

	// Shift the InteriorTracker focus point to the center of the current cell.
	if t.isActive && len(edges) != 0 {
		if !t.atCellID(p.id) {
			t.moveTo(p.EntryVertex())
		}
		t.drawTo(p.Center())
		s.testAllEdges(edges, t)
	}

	// Allocate and fill a new index cell. To get the total number of shapes we
	// need to merge the shapes associated with the intersecting edges together
	// with the shapes that happen to contain the cell center.
	cshapeIDs := t.shapeIDs
	numShapes := s.countShapes(edges, cshapeIDs)
	cell := NewShapeIndexCell(numShapes)

	// To fill the index cell we merge the two sources of shapes: edge shapes
	// (those that have at least one edge that intersects this cell), and
	// containing shapes (those that contain the cell center). We keep track
	// of the index of the next intersecting edge and the next containing shape
	// as we go along. Both sets of shape ids are already sorted.
	eNext := 0
	cNextIdx := 0
	for i := 0; i < numShapes; i++ {
		var clipped *clippedShape
		// advance to next value base + i
		eshapeID := int32(s.Len())
		cshapeID := eshapeID // Sentinels

		if eNext != len(edges) {
			eshapeID = edges[eNext].faceEdge.shapeID
		}
		if cNextIdx < len(cshapeIDs) {
			cshapeID = cshapeIDs[cNextIdx]
		}
		eBegin := eNext
		if cshapeID < eshapeID {
			// The entire cell is in the shape interior.
			clipped = newClippedShape(cshapeID, 0)
			clipped.containsCenter = true
			cNextIdx++
		} else {
			// Count the number of edges for this shape and allocate space for them.
			for eNext < len(edges) && edges[eNext].faceEdge.shapeID == eshapeID {
				eNext++
			}
			clipped = newClippedShape(eshapeID, eNext-eBegin)
			for e := eBegin; e < eNext; e++ {
				clipped.edges[e-eBegin] = edges[e].faceEdge.edgeID
			}
			if cshapeID == eshapeID {
				clipped.containsCenter = true
				cNextIdx++
			}
		}
		cell.shapes[i] = clipped
	}

	// Add this cell to the map.
	s.cellMap[p.id] = cell
	s.cells = append(s.cells, p.id)

	// Shift the tracker focus point to the exit vertex of this cell.
	if t.isActive && len(edges) != 0 {
		t.drawTo(p.ExitVertex())
		s.testAllEdges(edges, t)
		t.setNextCellID(p.id.Next())
	}
	return true
}