func()

in s2/edge_query.go [580:673]

• 60 lines of code
• 16 McCabe index (conditional complexity)

func (e *EdgeQuery) initQueue() {
	if len(e.indexCovering) == 0 {
		// We delay iterator initialization until now to make queries on very
		// small indexes a bit faster (i.e., where brute force is used).
		e.iter = NewShapeIndexIterator(e.index)
	}

	// Optimization: if the user is searching for just the closest edge, and the
	// center of the target's bounding cap happens to intersect an index cell,
	// then we try to limit the search region to a small disc by first
	// processing the edges in that cell.  This sets distance_limit_ based on
	// the closest edge in that cell, which we can then use to limit the search
	// area.  This means that the cell containing "target" will be processed
	// twice, but in general this is still faster.
	//
	// TODO(roberts): Even if the cap center is not contained, we could still
	// process one or both of the adjacent index cells in CellID order,
	// provided that those cells are closer than distanceLimit.
	cb := e.target.capBound()
	if cb.IsEmpty() {
		return // Empty target.
	}

	if e.opts.maxResults == 1 && e.iter.LocatePoint(cb.Center()) {
		e.processEdges(&queryQueueEntry{
			distance:  e.target.distance().zero(),
			id:        e.iter.CellID(),
			indexCell: e.iter.IndexCell(),
		})
		// Skip the rest of the algorithm if we found an intersecting edge.
		if e.distanceLimit == e.target.distance().zero() {
			return
		}
	}
	if len(e.indexCovering) == 0 {
		e.initCovering()
	}
	if e.distanceLimit == e.target.distance().infinity() {
		// Start with the precomputed index covering.
		for i := range e.indexCovering {
			e.processOrEnqueue(e.indexCovering[i], e.indexCells[i])
		}
	} else {
		// Compute a covering of the search disc and intersect it with the
		// precomputed index covering.
		coverer := &RegionCoverer{MaxCells: 4, LevelMod: 1, MaxLevel: maxLevel}

		radius := cb.Radius() + e.distanceLimit.chordAngleBound().Angle()
		searchCB := CapFromCenterAngle(cb.Center(), radius)
		maxDistCover := coverer.FastCovering(searchCB)
		e.initialCells = CellUnionFromIntersection(e.indexCovering, maxDistCover)

		// Now we need to clean up the initial cells to ensure that they all
		// contain at least one cell of the ShapeIndex. (Some may not intersect
		// the index at all, while other may be descendants of an index cell.)
		i, j := 0, 0
		for i < len(e.initialCells) {
			idI := e.initialCells[i]
			// Find the top-level cell that contains this initial cell.
			for e.indexCovering[j].RangeMax() < idI {
				j++
			}

			idJ := e.indexCovering[j]
			if idI == idJ {
				// This initial cell is one of the top-level cells.  Use the
				// precomputed ShapeIndexCell pointer to avoid an index seek.
				e.processOrEnqueue(idJ, e.indexCells[j])
				i++
				j++
			} else {
				// This initial cell is a proper descendant of a top-level cell.
				// Check how it is related to the cells of the ShapeIndex.
				r := e.iter.LocateCellID(idI)
				if r == Indexed {
					// This cell is a descendant of an index cell.
					// Enqueue it and skip any other initial cells
					// that are also descendants of this cell.
					e.processOrEnqueue(e.iter.CellID(), e.iter.IndexCell())
					lastID := e.iter.CellID().RangeMax()
					for i < len(e.initialCells) && e.initialCells[i] <= lastID {
						i++
					}
				} else {
					// Enqueue the cell only if it contains at least one index cell.
					if r == Subdivided {
						e.processOrEnqueue(idI, nil)
					}
					i++
				}
			}
		}
	}
}