diff options
Diffstat (limited to 'vendor/github.com/golang/geo/s2/edge_query.go')
| -rw-r--r-- | vendor/github.com/golang/geo/s2/edge_query.go | 803 |
1 files changed, 803 insertions, 0 deletions
diff --git a/vendor/github.com/golang/geo/s2/edge_query.go b/vendor/github.com/golang/geo/s2/edge_query.go new file mode 100644 index 000000000..2d443d1ce --- /dev/null +++ b/vendor/github.com/golang/geo/s2/edge_query.go @@ -0,0 +1,803 @@ +// Copyright 2019 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +package s2 + +import ( + "sort" + + "github.com/golang/geo/s1" +) + +// EdgeQueryOptions holds the options for controlling how EdgeQuery operates. +// +// Options can be chained together builder-style: +// +// opts = NewClosestEdgeQueryOptions(). +// MaxResults(1). +// DistanceLimit(s1.ChordAngleFromAngle(3 * s1.Degree)). +// MaxError(s1.ChordAngleFromAngle(0.001 * s1.Degree)) +// query = NewClosestEdgeQuery(index, opts) +// +// or set individually: +// +// opts = NewClosestEdgeQueryOptions() +// opts.IncludeInteriors(true) +// +// or just inline: +// +// query = NewClosestEdgeQuery(index, NewClosestEdgeQueryOptions().MaxResults(3)) +// +// If you pass a nil as the options you get the default values for the options. +type EdgeQueryOptions struct { + common *queryOptions +} + +// DistanceLimit specifies that only edges whose distance to the target is +// within, this distance should be returned. Edges whose distance is equal +// are not returned. To include values that are equal, specify the limit with +// the next largest representable distance. i.e. limit.Successor(). +func (e *EdgeQueryOptions) DistanceLimit(limit s1.ChordAngle) *EdgeQueryOptions { + e.common = e.common.DistanceLimit(limit) + return e +} + +// IncludeInteriors specifies whether polygon interiors should be +// included when measuring distances. +func (e *EdgeQueryOptions) IncludeInteriors(x bool) *EdgeQueryOptions { + e.common = e.common.IncludeInteriors(x) + return e +} + +// UseBruteForce sets or disables the use of brute force in a query. +func (e *EdgeQueryOptions) UseBruteForce(x bool) *EdgeQueryOptions { + e.common = e.common.UseBruteForce(x) + return e +} + +// MaxError specifies that edges up to dist away than the true +// matching edges may be substituted in the result set, as long as such +// edges satisfy all the remaining search criteria (such as DistanceLimit). +// This option only has an effect if MaxResults is also specified; +// otherwise all edges closer than MaxDistance will always be returned. +func (e *EdgeQueryOptions) MaxError(dist s1.ChordAngle) *EdgeQueryOptions { + e.common = e.common.MaxError(dist) + return e +} + +// MaxResults specifies that at most MaxResults edges should be returned. +// This must be at least 1. +func (e *EdgeQueryOptions) MaxResults(n int) *EdgeQueryOptions { + e.common = e.common.MaxResults(n) + return e +} + +// NewClosestEdgeQueryOptions returns a set of edge query options suitable +// for performing closest edge queries. +func NewClosestEdgeQueryOptions() *EdgeQueryOptions { + return &EdgeQueryOptions{ + common: newQueryOptions(minDistance(0)), + } +} + +// NewFurthestEdgeQueryOptions returns a set of edge query options suitable +// for performing furthest edge queries. +func NewFurthestEdgeQueryOptions() *EdgeQueryOptions { + return &EdgeQueryOptions{ + common: newQueryOptions(maxDistance(0)), + } +} + +// EdgeQueryResult represents an edge that meets the target criteria for the +// query. Note the following special cases: +// +// - ShapeID >= 0 && EdgeID < 0 represents the interior of a shape. +// Such results may be returned when the option IncludeInteriors is true. +// +// - ShapeID < 0 && EdgeID < 0 is returned to indicate that no edge +// satisfies the requested query options. +type EdgeQueryResult struct { + distance distance + shapeID int32 + edgeID int32 +} + +// Distance reports the distance between the edge in this shape that satisfied +// the query's parameters. +func (e EdgeQueryResult) Distance() s1.ChordAngle { return e.distance.chordAngle() } + +// ShapeID reports the ID of the Shape this result is for. +func (e EdgeQueryResult) ShapeID() int32 { return e.shapeID } + +// EdgeID reports the ID of the edge in the results Shape. +func (e EdgeQueryResult) EdgeID() int32 { return e.edgeID } + +// newEdgeQueryResult returns a result instance with default values. +func newEdgeQueryResult(target distanceTarget) EdgeQueryResult { + return EdgeQueryResult{ + distance: target.distance().infinity(), + shapeID: -1, + edgeID: -1, + } +} + +// IsInterior reports if this result represents the interior of a Shape. +func (e EdgeQueryResult) IsInterior() bool { + return e.shapeID >= 0 && e.edgeID < 0 +} + +// IsEmpty reports if this has no edge that satisfies the given edge query options. +// This result is only returned in one special case, namely when FindEdge() does +// not find any suitable edges. +func (e EdgeQueryResult) IsEmpty() bool { + return e.shapeID < 0 +} + +// Less reports if this results is less that the other first by distance, +// then by (shapeID, edgeID). This is used for sorting. +func (e EdgeQueryResult) Less(other EdgeQueryResult) bool { + if e.distance.chordAngle() != other.distance.chordAngle() { + return e.distance.less(other.distance) + } + if e.shapeID != other.shapeID { + return e.shapeID < other.shapeID + } + return e.edgeID < other.edgeID +} + +// EdgeQuery is used to find the edge(s) between two geometries that match a +// given set of options. It is flexible enough so that it can be adapted to +// compute maximum distances and even potentially Hausdorff distances. +// +// By using the appropriate options, this type can answer questions such as: +// +// - Find the minimum distance between two geometries A and B. +// - Find all edges of geometry A that are within a distance D of geometry B. +// - Find the k edges of geometry A that are closest to a given point P. +// +// You can also specify whether polygons should include their interiors (i.e., +// if a point is contained by a polygon, should the distance be zero or should +// it be measured to the polygon boundary?) +// +// The input geometries may consist of any number of points, polylines, and +// polygons (collectively referred to as "shapes"). Shapes do not need to be +// disjoint; they may overlap or intersect arbitrarily. The implementation is +// designed to be fast for both simple and complex geometries. +type EdgeQuery struct { + index *ShapeIndex + opts *queryOptions + target distanceTarget + + // True if opts.maxError must be subtracted from ShapeIndex cell distances + // in order to ensure that such distances are measured conservatively. This + // is true only if the target takes advantage of maxError in order to + // return faster results, and 0 < maxError < distanceLimit. + useConservativeCellDistance bool + + // The decision about whether to use the brute force algorithm is based on + // counting the total number of edges in the index. However if the index + // contains a large number of shapes, this in itself might take too long. + // So instead we only count edges up to (maxBruteForceIndexSize() + 1) + // for the current target type (stored as indexNumEdgesLimit). + indexNumEdges int + indexNumEdgesLimit int + + // The distance beyond which we can safely ignore further candidate edges. + // (Candidates that are exactly at the limit are ignored; this is more + // efficient for UpdateMinDistance and should not affect clients since + // distance measurements have a small amount of error anyway.) + // + // Initially this is the same as the maximum distance specified by the user, + // but it can also be updated by the algorithm (see maybeAddResult). + distanceLimit distance + + // The current set of results of the query. + results []EdgeQueryResult + + // This field is true when duplicates must be avoided explicitly. This + // is achieved by maintaining a separate set keyed by (shapeID, edgeID) + // only, and checking whether each edge is in that set before computing the + // distance to it. + avoidDuplicates bool + + // testedEdges tracks the set of shape and edges that have already been tested. + testedEdges map[ShapeEdgeID]uint32 + + // For the optimized algorihm we precompute the top-level CellIDs that + // will be added to the priority queue. There can be at most 6 of these + // cells. Essentially this is just a covering of the indexed edges, except + // that we also store pointers to the corresponding ShapeIndexCells to + // reduce the number of index seeks required. + indexCovering []CellID + indexCells []*ShapeIndexCell + + // The algorithm maintains a priority queue of unprocessed CellIDs, sorted + // in increasing order of distance from the target. + queue *queryQueue + + iter *ShapeIndexIterator + maxDistanceCovering []CellID + initialCells []CellID +} + +// NewClosestEdgeQuery returns an EdgeQuery that is used for finding the +// closest edge(s) to a given Point, Edge, Cell, or geometry collection. +// +// You can find either the k closest edges, or all edges within a given +// radius, or both (i.e., the k closest edges up to a given maximum radius). +// E.g. to find all the edges within 5 kilometers, set the DistanceLimit in +// the options. +// +// By default *all* edges are returned, so you should always specify either +// MaxResults or DistanceLimit options or both. +// +// Note that by default, distances are measured to the boundary and interior +// of polygons. For example, if a point is inside a polygon then its distance +// is zero. To change this behavior, set the IncludeInteriors option to false. +// +// If you only need to test whether the distance is above or below a given +// threshold (e.g., 10 km), you can use the IsDistanceLess() method. This is +// much faster than actually calculating the distance with FindEdge, +// since the implementation can stop as soon as it can prove that the minimum +// distance is either above or below the threshold. +func NewClosestEdgeQuery(index *ShapeIndex, opts *EdgeQueryOptions) *EdgeQuery { + if opts == nil { + opts = NewClosestEdgeQueryOptions() + } + e := &EdgeQuery{ + testedEdges: make(map[ShapeEdgeID]uint32), + index: index, + opts: opts.common, + queue: newQueryQueue(), + } + + return e +} + +// NewFurthestEdgeQuery returns an EdgeQuery that is used for finding the +// furthest edge(s) to a given Point, Edge, Cell, or geometry collection. +// +// The furthest edge is defined as the one which maximizes the +// distance from any point on that edge to any point on the target geometry. +// +// Similar to the example in NewClosestEdgeQuery, to find the 5 furthest edges +// from a given Point: +func NewFurthestEdgeQuery(index *ShapeIndex, opts *EdgeQueryOptions) *EdgeQuery { + if opts == nil { + opts = NewFurthestEdgeQueryOptions() + } + e := &EdgeQuery{ + testedEdges: make(map[ShapeEdgeID]uint32), + index: index, + opts: opts.common, + queue: newQueryQueue(), + } + + return e +} + +// Reset resets the state of this EdgeQuery. +func (e *EdgeQuery) Reset() { + e.indexNumEdges = 0 + e.indexNumEdgesLimit = 0 + e.indexCovering = nil + e.indexCells = nil +} + +// FindEdges returns the edges for the given target that satisfy the current options. +// +// Note that if opts.IncludeInteriors is true, the results may include some +// entries with edge_id == -1. This indicates that the target intersects +// the indexed polygon with the given ShapeID. +func (e *EdgeQuery) FindEdges(target distanceTarget) []EdgeQueryResult { + return e.findEdges(target, e.opts) +} + +// Distance reports the distance to the target. If the index or target is empty, +// returns the EdgeQuery's maximal sentinel. +// +// Use IsDistanceLess()/IsDistanceGreater() if you only want to compare the +// distance against a threshold value, since it is often much faster. +func (e *EdgeQuery) Distance(target distanceTarget) s1.ChordAngle { + return e.findEdge(target, e.opts).Distance() +} + +// IsDistanceLess reports if the distance to target is less than the given limit. +// +// This method is usually much faster than Distance(), since it is much +// less work to determine whether the minimum distance is above or below a +// threshold than it is to calculate the actual minimum distance. +// +// If you wish to check if the distance is less than or equal to the limit, use: +// +// query.IsDistanceLess(target, limit.Successor()) +// +func (e *EdgeQuery) IsDistanceLess(target distanceTarget, limit s1.ChordAngle) bool { + opts := e.opts + opts = opts.MaxResults(1). + DistanceLimit(limit). + MaxError(s1.StraightChordAngle) + return !e.findEdge(target, opts).IsEmpty() +} + +// IsDistanceGreater reports if the distance to target is greater than limit. +// +// This method is usually much faster than Distance, since it is much +// less work to determine whether the maximum distance is above or below a +// threshold than it is to calculate the actual maximum distance. +// If you wish to check if the distance is less than or equal to the limit, use: +// +// query.IsDistanceGreater(target, limit.Predecessor()) +// +func (e *EdgeQuery) IsDistanceGreater(target distanceTarget, limit s1.ChordAngle) bool { + return e.IsDistanceLess(target, limit) +} + +// IsConservativeDistanceLessOrEqual reports if the distance to target is less +// or equal to the limit, where the limit has been expanded by the maximum error +// for the distance calculation. +// +// For example, suppose that we want to test whether two geometries might +// intersect each other after they are snapped together using Builder +// (using the IdentitySnapFunction with a given "snap radius"). Since +// Builder uses exact distance predicates (s2predicates), we need to +// measure the distance between the two geometries conservatively. If the +// distance is definitely greater than "snap radius", then the geometries +// are guaranteed to not intersect after snapping. +func (e *EdgeQuery) IsConservativeDistanceLessOrEqual(target distanceTarget, limit s1.ChordAngle) bool { + return e.IsDistanceLess(target, limit.Expanded(minUpdateDistanceMaxError(limit))) +} + +// IsConservativeDistanceGreaterOrEqual reports if the distance to the target is greater +// than or equal to the given limit with some small tolerance. +func (e *EdgeQuery) IsConservativeDistanceGreaterOrEqual(target distanceTarget, limit s1.ChordAngle) bool { + return e.IsDistanceGreater(target, limit.Expanded(-minUpdateDistanceMaxError(limit))) +} + +// findEdges returns the closest edges to the given target that satisfy the given options. +// +// Note that if opts.includeInteriors is true, the results may include some +// entries with edgeID == -1. This indicates that the target intersects the +// indexed polygon with the given shapeID. +func (e *EdgeQuery) findEdges(target distanceTarget, opts *queryOptions) []EdgeQueryResult { + e.findEdgesInternal(target, opts) + // TODO(roberts): Revisit this if there is a heap or other sorted and + // uniquing datastructure we can use instead of just a slice. + e.results = sortAndUniqueResults(e.results) + if len(e.results) > e.opts.maxResults { + e.results = e.results[:e.opts.maxResults] + } + return e.results +} + +func sortAndUniqueResults(results []EdgeQueryResult) []EdgeQueryResult { + if len(results) <= 1 { + return results + } + sort.Slice(results, func(i, j int) bool { return results[i].Less(results[j]) }) + j := 0 + for i := 1; i < len(results); i++ { + if results[j] == results[i] { + continue + } + j++ + results[j] = results[i] + } + return results[:j+1] +} + +// findEdge is a convenience method that returns exactly one edge, and if no +// edges satisfy the given search criteria, then a default Result is returned. +// +// This is primarily to ease the usage of a number of the methods in the DistanceTargets +// and in EdgeQuery. +func (e *EdgeQuery) findEdge(target distanceTarget, opts *queryOptions) EdgeQueryResult { + opts.MaxResults(1) + e.findEdges(target, opts) + if len(e.results) > 0 { + return e.results[0] + } + + return newEdgeQueryResult(target) +} + +// findEdgesInternal does the actual work for find edges that match the given options. +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() + } +} + +func (e *EdgeQuery) addResult(r EdgeQueryResult) { + e.results = append(e.results, r) + if e.opts.maxResults == 1 { + // Optimization for the common case where only the closest edge is wanted. + e.distanceLimit = r.distance.sub(e.target.distance().fromChordAngle(e.opts.maxError)) + } + // TODO(roberts): Add the other if/else cases when a different data structure + // is used for the results. +} + +func (e *EdgeQuery) maybeAddResult(shape Shape, edgeID int32) { + if _, ok := e.testedEdges[ShapeEdgeID{e.index.idForShape(shape), edgeID}]; e.avoidDuplicates && !ok { + return + } + edge := shape.Edge(int(edgeID)) + dist := e.distanceLimit + + if dist, ok := e.target.updateDistanceToEdge(edge, dist); ok { + e.addResult(EdgeQueryResult{dist, e.index.idForShape(shape), edgeID}) + } +} + +func (e *EdgeQuery) findEdgesBruteForce() { + // Range over all shapes in the index. Does order matter here? if so + // switch to for i = 0 .. n? + for _, shape := range e.index.shapes { + // TODO(roberts): can this happen if we are only ranging over current entries? + if shape == nil { + continue + } + for edgeID := int32(0); edgeID < int32(shape.NumEdges()); edgeID++ { + e.maybeAddResult(shape, edgeID) + } + } +} + +func (e *EdgeQuery) findEdgesOptimized() { + e.initQueue() + // Repeatedly find the closest Cell to "target" and either split it into + // its four children or process all of its edges. + for e.queue.size() > 0 { + // We need to copy the top entry before removing it, and we need to + // remove it before adding any new entries to the queue. + entry := e.queue.pop() + + if !entry.distance.less(e.distanceLimit) { + e.queue.reset() // Clear any remaining entries. + break + } + // If this is already known to be an index cell, just process it. + if entry.indexCell != nil { + e.processEdges(entry) + continue + } + // Otherwise split the cell into its four children. Before adding a + // child back to the queue, we first check whether it is empty. We do + // this in two seek operations rather than four by seeking to the key + // between children 0 and 1 and to the key between children 2 and 3. + id := entry.id + ch := id.Children() + e.iter.seek(ch[1].RangeMin()) + + if !e.iter.Done() && e.iter.CellID() <= ch[1].RangeMax() { + e.processOrEnqueueCell(ch[1]) + } + if e.iter.Prev() && e.iter.CellID() >= id.RangeMin() { + e.processOrEnqueueCell(ch[0]) + } + + e.iter.seek(ch[3].RangeMin()) + if !e.iter.Done() && e.iter.CellID() <= id.RangeMax() { + e.processOrEnqueueCell(ch[3]) + } + if e.iter.Prev() && e.iter.CellID() >= ch[2].RangeMin() { + e.processOrEnqueueCell(ch[2]) + } + } +} + +func (e *EdgeQuery) processOrEnqueueCell(id CellID) { + if e.iter.CellID() == id { + e.processOrEnqueue(id, e.iter.IndexCell()) + } else { + e.processOrEnqueue(id, nil) + } +} + +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++ + } + } + } + } +} + +func (e *EdgeQuery) initCovering() { + // Find the range of Cells spanned by the index and choose a level such + // that the entire index can be covered with just a few cells. These are + // the "top-level" cells. There are two cases: + // + // - If the index spans more than one face, then there is one top-level cell + // per spanned face, just big enough to cover the index cells on that face. + // + // - If the index spans only one face, then we find the smallest cell "C" + // that covers the index cells on that face (just like the case above). + // Then for each of the 4 children of "C", if the child contains any index + // cells then we create a top-level cell that is big enough to just fit + // those index cells (i.e., shrinking the child as much as possible to fit + // its contents). This essentially replicates what would happen if we + // started with "C" as the top-level cell, since "C" would immediately be + // split, except that we take the time to prune the children further since + // this will save work on every subsequent query. + e.indexCovering = make([]CellID, 0, 6) + + // TODO(roberts): Use a single iterator below and save position + // information using pair {CellID, ShapeIndexCell}. + next := NewShapeIndexIterator(e.index, IteratorBegin) + last := NewShapeIndexIterator(e.index, IteratorEnd) + last.Prev() + if next.CellID() != last.CellID() { + // The index has at least two cells. Choose a level such that the entire + // index can be spanned with at most 6 cells (if the index spans multiple + // faces) or 4 cells (it the index spans a single face). + level, ok := next.CellID().CommonAncestorLevel(last.CellID()) + if !ok { + level = 0 + } else { + level++ + } + + // Visit each potential top-level cell except the last (handled below). + lastID := last.CellID().Parent(level) + for id := next.CellID().Parent(level); id != lastID; id = id.Next() { + // Skip any top-level cells that don't contain any index cells. + if id.RangeMax() < next.CellID() { + continue + } + + // Find the range of index cells contained by this top-level cell and + // then shrink the cell if necessary so that it just covers them. + cellFirst := next.clone() + next.seek(id.RangeMax().Next()) + cellLast := next.clone() + cellLast.Prev() + e.addInitialRange(cellFirst, cellLast) + break + } + + } + e.addInitialRange(next, last) +} + +// addInitialRange adds an entry to the indexCovering and indexCells that covers the given +// inclusive range of cells. +// +// This requires that first and last cells have a common ancestor. +func (e *EdgeQuery) addInitialRange(first, last *ShapeIndexIterator) { + if first.CellID() == last.CellID() { + // The range consists of a single index cell. + e.indexCovering = append(e.indexCovering, first.CellID()) + e.indexCells = append(e.indexCells, first.IndexCell()) + } else { + // Add the lowest common ancestor of the given range. + level, _ := first.CellID().CommonAncestorLevel(last.CellID()) + e.indexCovering = append(e.indexCovering, first.CellID().Parent(level)) + e.indexCells = append(e.indexCells, nil) + } +} + +// processEdges processes all the edges of the given index cell. +func (e *EdgeQuery) processEdges(entry *queryQueueEntry) { + for _, clipped := range entry.indexCell.shapes { + shape := e.index.Shape(clipped.shapeID) + for j := 0; j < clipped.numEdges(); j++ { + e.maybeAddResult(shape, int32(clipped.edges[j])) + } + } +} + +// processOrEnqueue the given cell id and indexCell. +func (e *EdgeQuery) processOrEnqueue(id CellID, indexCell *ShapeIndexCell) { + if indexCell != nil { + // If this index cell has only a few edges, then it is faster to check + // them directly rather than computing the minimum distance to the Cell + // and inserting it into the queue. + const minEdgesToEnqueue = 10 + numEdges := indexCell.numEdges() + if numEdges == 0 { + return + } + if numEdges < minEdgesToEnqueue { + // Set "distance" to zero to avoid the expense of computing it. + e.processEdges(&queryQueueEntry{ + distance: e.target.distance().zero(), + id: id, + indexCell: indexCell, + }) + return + } + } + + // Otherwise compute the minimum distance to any point in the cell and add + // it to the priority queue. + cell := CellFromCellID(id) + dist := e.distanceLimit + var ok bool + if dist, ok = e.target.updateDistanceToCell(cell, dist); !ok { + return + } + if e.useConservativeCellDistance { + // Ensure that "distance" is a lower bound on the true distance to the cell. + dist = dist.sub(e.target.distance().fromChordAngle(e.opts.maxError)) + } + + e.queue.push(&queryQueueEntry{ + distance: dist, + id: id, + indexCell: indexCell, + }) +} + +// TODO(roberts): Remaining pieces +// GetEdge +// Project |