Method getCellsForEdge

s2/crossing_edge_query.go:254–296

getCellsForEdge populates the cells field to the set of index cells intersected by an edge AB.

(a, b Point)

// getCellsForEdge populates the cells field to the set of index cells intersected by an edge AB.
func (c *CrossingEdgeQuery) getCellsForEdge(a, b Point) {
	c.cells = nil

	segments := FaceSegments(a, b)
	for _, segment := range segments {
		c.a = segment.a
		c.b = segment.b

		// Optimization: rather than always starting the recursive subdivision at
		// the top level face cell, instead we start at the smallest S2CellId that
		// contains the edge (the edge root cell). This typically lets us skip
		// quite a few levels of recursion since most edges are short.
		edgeBound := r2.RectFromPoints(c.a, c.b)
		pcell := PaddedCellFromCellID(CellIDFromFace(segment.face), 0)
		edgeRoot := pcell.ShrinkToFit(edgeBound)

		// Now we need to determine how the edge root cell is related to the cells
		// in the spatial index (cellMap). There are three cases:
		//
		//  1. edgeRoot is an index cell or is contained within an index cell.
		//     In this case we only need to look at the contents of that cell.
		//  2. edgeRoot is subdivided into one or more index cells. In this case
		//     we recursively subdivide to find the cells intersected by AB.
		//  3. edgeRoot does not intersect any index cells. In this case there
		//     is nothing to do.
		relation := c.iter.LocateCellID(edgeRoot)
		switch relation {
		case Indexed:
			// edgeRoot is an index cell or is contained by an
			// index cell (case 1).
			c.cells = append(c.cells, c.iter.IndexCell())
		case Subdivided:
			// edgeRoot is subdivided into one or more index cells
			// (case 2). We find the cells intersected by AB using
			// recursive subdivision.
			if !edgeRoot.isFace() {
				pcell = PaddedCellFromCellID(edgeRoot, 0)
			}
			c.computeCellsIntersected(pcell, edgeBound)
		case Disjoint:
		}
	}
}

// computeCellsIntersected computes the index cells intersected by the current
// edge that are descendants of pcell and adds them to this queries set of cells.