func()

in s2/edge_query.go [416:491]

• 40 lines of code
• 13 McCabe index (conditional complexity)

func (e *EdgeQuery) findEdgesInternal(target distanceTarget, opts *queryOptions) {
	e.target = target
	e.opts = opts

	e.testedEdges = make(map[ShapeEdgeID]uint32)
	e.distanceLimit = target.distance().fromChordAngle(opts.distanceLimit)
	e.results = make([]EdgeQueryResult, 0)

	if e.distanceLimit == target.distance().zero() {
		return
	}

	if opts.includeInteriors {
		shapeIDs := map[int32]struct{}{}
		e.target.visitContainingShapes(e.index, func(containingShape Shape, targetPoint Point) bool {
			shapeIDs[e.index.idForShape(containingShape)] = struct{}{}
			return len(shapeIDs) < opts.maxResults
		})
		for shapeID := range shapeIDs {
			e.addResult(EdgeQueryResult{target.distance().zero(), shapeID, -1})
		}

		if e.distanceLimit == target.distance().zero() {
			return
		}
	}

	// If maxError > 0 and the target takes advantage of this, then we may
	// need to adjust the distance estimates to ShapeIndex cells to ensure
	// that they are always a lower bound on the true distance. For example,
	// suppose max_distance == 100, maxError == 30, and we compute the distance
	// to the target from some cell C0 as d(C0) == 80. Then because the target
	// takes advantage of maxError, the true distance could be as low as 50.
	// In order not to miss edges contained by such cells, we need to subtract
	// maxError from the distance estimates. This behavior is controlled by
	// the useConservativeCellDistance flag.
	//
	// However there is one important case where this adjustment is not
	// necessary, namely when distanceLimit < maxError, This is because
	// maxError only affects the algorithm once at least maxEdges edges
	// have been found that satisfy the given distance limit. At that point,
	// maxError is subtracted from distanceLimit in order to ensure that
	// any further matches are closer by at least that amount. But when
	// distanceLimit < maxError, this reduces the distance limit to 0,
	// i.e. all remaining candidate cells and edges can safely be discarded.
	// (This is how IsDistanceLess() and friends are implemented.)
	targetUsesMaxError := opts.maxError != target.distance().zero().chordAngle() &&
		e.target.setMaxError(opts.maxError)

	// Note that we can't compare maxError and distanceLimit directly
	// because one is a Delta and one is a Distance. Instead we subtract them.
	e.useConservativeCellDistance = targetUsesMaxError &&
		(e.distanceLimit == target.distance().infinity() ||
			target.distance().zero().less(e.distanceLimit.sub(target.distance().fromChordAngle(opts.maxError))))

	// Use the brute force algorithm if the index is small enough. To avoid
	// spending too much time counting edges when there are many shapes, we stop
	// counting once there are too many edges. We may need to recount the edges
	// if we later see a target with a larger brute force edge threshold.
	minOptimizedEdges := e.target.maxBruteForceIndexSize() + 1
	if minOptimizedEdges > e.indexNumEdgesLimit && e.indexNumEdges >= e.indexNumEdgesLimit {
		e.indexNumEdges = e.index.NumEdgesUpTo(minOptimizedEdges)
		e.indexNumEdgesLimit = minOptimizedEdges
	}

	if opts.useBruteForce || e.indexNumEdges < minOptimizedEdges {
		// The brute force algorithm already considers each edge exactly once.
		e.avoidDuplicates = false
		e.findEdgesBruteForce()
	} else {
		// If the target takes advantage of maxError then we need to avoid
		// duplicate edges explicitly. (Otherwise it happens automatically.)
		e.avoidDuplicates = targetUsesMaxError && opts.maxResults > 1
		e.findEdgesOptimized()
	}
}