1 // Copyright 2019 Google Inc. All rights reserved. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 package s2 16 17 import ( 18 "sort" 19 20 "github.com/golang/geo/s1" 21 ) 22 23 // EdgeQueryOptions holds the options for controlling how EdgeQuery operates. 24 // 25 // Options can be chained together builder-style: 26 // 27 // opts = NewClosestEdgeQueryOptions(). 28 // MaxResults(1). 29 // DistanceLimit(s1.ChordAngleFromAngle(3 * s1.Degree)). 30 // MaxError(s1.ChordAngleFromAngle(0.001 * s1.Degree)) 31 // query = NewClosestEdgeQuery(index, opts) 32 // 33 // or set individually: 34 // 35 // opts = NewClosestEdgeQueryOptions() 36 // opts.IncludeInteriors(true) 37 // 38 // or just inline: 39 // 40 // query = NewClosestEdgeQuery(index, NewClosestEdgeQueryOptions().MaxResults(3)) 41 // 42 // If you pass a nil as the options you get the default values for the options. 43 type EdgeQueryOptions struct { 44 common *queryOptions 45 } 46 47 // DistanceLimit specifies that only edges whose distance to the target is 48 // within, this distance should be returned. Edges whose distance is equal 49 // are not returned. To include values that are equal, specify the limit with 50 // the next largest representable distance. i.e. limit.Successor(). 51 func (e *EdgeQueryOptions) DistanceLimit(limit s1.ChordAngle) *EdgeQueryOptions { 52 e.common = e.common.DistanceLimit(limit) 53 return e 54 } 55 56 // IncludeInteriors specifies whether polygon interiors should be 57 // included when measuring distances. 58 func (e *EdgeQueryOptions) IncludeInteriors(x bool) *EdgeQueryOptions { 59 e.common = e.common.IncludeInteriors(x) 60 return e 61 } 62 63 // UseBruteForce sets or disables the use of brute force in a query. 64 func (e *EdgeQueryOptions) UseBruteForce(x bool) *EdgeQueryOptions { 65 e.common = e.common.UseBruteForce(x) 66 return e 67 } 68 69 // MaxError specifies that edges up to dist away than the true 70 // matching edges may be substituted in the result set, as long as such 71 // edges satisfy all the remaining search criteria (such as DistanceLimit). 72 // This option only has an effect if MaxResults is also specified; 73 // otherwise all edges closer than MaxDistance will always be returned. 74 func (e *EdgeQueryOptions) MaxError(dist s1.ChordAngle) *EdgeQueryOptions { 75 e.common = e.common.MaxError(dist) 76 return e 77 } 78 79 // MaxResults specifies that at most MaxResults edges should be returned. 80 // This must be at least 1. 81 func (e *EdgeQueryOptions) MaxResults(n int) *EdgeQueryOptions { 82 e.common = e.common.MaxResults(n) 83 return e 84 } 85 86 // NewClosestEdgeQueryOptions returns a set of edge query options suitable 87 // for performing closest edge queries. 88 func NewClosestEdgeQueryOptions() *EdgeQueryOptions { 89 return &EdgeQueryOptions{ 90 common: newQueryOptions(minDistance(0)), 91 } 92 } 93 94 // NewFurthestEdgeQueryOptions returns a set of edge query options suitable 95 // for performing furthest edge queries. 96 func NewFurthestEdgeQueryOptions() *EdgeQueryOptions { 97 return &EdgeQueryOptions{ 98 common: newQueryOptions(maxDistance(0)), 99 } 100 } 101 102 // EdgeQueryResult represents an edge that meets the target criteria for the 103 // query. Note the following special cases: 104 // 105 // - ShapeID >= 0 && EdgeID < 0 represents the interior of a shape. 106 // Such results may be returned when the option IncludeInteriors is true. 107 // 108 // - ShapeID < 0 && EdgeID < 0 is returned to indicate that no edge 109 // satisfies the requested query options. 110 type EdgeQueryResult struct { 111 distance distance 112 shapeID int32 113 edgeID int32 114 } 115 116 // Distance reports the distance between the edge in this shape that satisfied 117 // the query's parameters. 118 func (e EdgeQueryResult) Distance() s1.ChordAngle { return e.distance.chordAngle() } 119 120 // ShapeID reports the ID of the Shape this result is for. 121 func (e EdgeQueryResult) ShapeID() int32 { return e.shapeID } 122 123 // EdgeID reports the ID of the edge in the results Shape. 124 func (e EdgeQueryResult) EdgeID() int32 { return e.edgeID } 125 126 // newEdgeQueryResult returns a result instance with default values. 127 func newEdgeQueryResult(target distanceTarget) EdgeQueryResult { 128 return EdgeQueryResult{ 129 distance: target.distance().infinity(), 130 shapeID: -1, 131 edgeID: -1, 132 } 133 } 134 135 // IsInterior reports if this result represents the interior of a Shape. 136 func (e EdgeQueryResult) IsInterior() bool { 137 return e.shapeID >= 0 && e.edgeID < 0 138 } 139 140 // IsEmpty reports if this has no edge that satisfies the given edge query options. 141 // This result is only returned in one special case, namely when FindEdge() does 142 // not find any suitable edges. 143 func (e EdgeQueryResult) IsEmpty() bool { 144 return e.shapeID < 0 145 } 146 147 // Less reports if this results is less that the other first by distance, 148 // then by (shapeID, edgeID). This is used for sorting. 149 func (e EdgeQueryResult) Less(other EdgeQueryResult) bool { 150 if e.distance.chordAngle() != other.distance.chordAngle() { 151 return e.distance.less(other.distance) 152 } 153 if e.shapeID != other.shapeID { 154 return e.shapeID < other.shapeID 155 } 156 return e.edgeID < other.edgeID 157 } 158 159 // EdgeQuery is used to find the edge(s) between two geometries that match a 160 // given set of options. It is flexible enough so that it can be adapted to 161 // compute maximum distances and even potentially Hausdorff distances. 162 // 163 // By using the appropriate options, this type can answer questions such as: 164 // 165 // - Find the minimum distance between two geometries A and B. 166 // - Find all edges of geometry A that are within a distance D of geometry B. 167 // - Find the k edges of geometry A that are closest to a given point P. 168 // 169 // You can also specify whether polygons should include their interiors (i.e., 170 // if a point is contained by a polygon, should the distance be zero or should 171 // it be measured to the polygon boundary?) 172 // 173 // The input geometries may consist of any number of points, polylines, and 174 // polygons (collectively referred to as "shapes"). Shapes do not need to be 175 // disjoint; they may overlap or intersect arbitrarily. The implementation is 176 // designed to be fast for both simple and complex geometries. 177 type EdgeQuery struct { 178 index *ShapeIndex 179 opts *queryOptions 180 target distanceTarget 181 182 // True if opts.maxError must be subtracted from ShapeIndex cell distances 183 // in order to ensure that such distances are measured conservatively. This 184 // is true only if the target takes advantage of maxError in order to 185 // return faster results, and 0 < maxError < distanceLimit. 186 useConservativeCellDistance bool 187 188 // The decision about whether to use the brute force algorithm is based on 189 // counting the total number of edges in the index. However if the index 190 // contains a large number of shapes, this in itself might take too long. 191 // So instead we only count edges up to (maxBruteForceIndexSize() + 1) 192 // for the current target type (stored as indexNumEdgesLimit). 193 indexNumEdges int 194 indexNumEdgesLimit int 195 196 // The distance beyond which we can safely ignore further candidate edges. 197 // (Candidates that are exactly at the limit are ignored; this is more 198 // efficient for UpdateMinDistance and should not affect clients since 199 // distance measurements have a small amount of error anyway.) 200 // 201 // Initially this is the same as the maximum distance specified by the user, 202 // but it can also be updated by the algorithm (see maybeAddResult). 203 distanceLimit distance 204 205 // The current set of results of the query. 206 results []EdgeQueryResult 207 208 // This field is true when duplicates must be avoided explicitly. This 209 // is achieved by maintaining a separate set keyed by (shapeID, edgeID) 210 // only, and checking whether each edge is in that set before computing the 211 // distance to it. 212 avoidDuplicates bool 213 214 // testedEdges tracks the set of shape and edges that have already been tested. 215 testedEdges map[ShapeEdgeID]uint32 216 217 // For the optimized algorihm we precompute the top-level CellIDs that 218 // will be added to the priority queue. There can be at most 6 of these 219 // cells. Essentially this is just a covering of the indexed edges, except 220 // that we also store pointers to the corresponding ShapeIndexCells to 221 // reduce the number of index seeks required. 222 indexCovering []CellID 223 indexCells []*ShapeIndexCell 224 225 // The algorithm maintains a priority queue of unprocessed CellIDs, sorted 226 // in increasing order of distance from the target. 227 queue *queryQueue 228 229 iter *ShapeIndexIterator 230 maxDistanceCovering []CellID 231 initialCells []CellID 232 } 233 234 // NewClosestEdgeQuery returns an EdgeQuery that is used for finding the 235 // closest edge(s) to a given Point, Edge, Cell, or geometry collection. 236 // 237 // You can find either the k closest edges, or all edges within a given 238 // radius, or both (i.e., the k closest edges up to a given maximum radius). 239 // E.g. to find all the edges within 5 kilometers, set the DistanceLimit in 240 // the options. 241 // 242 // By default *all* edges are returned, so you should always specify either 243 // MaxResults or DistanceLimit options or both. 244 // 245 // Note that by default, distances are measured to the boundary and interior 246 // of polygons. For example, if a point is inside a polygon then its distance 247 // is zero. To change this behavior, set the IncludeInteriors option to false. 248 // 249 // If you only need to test whether the distance is above or below a given 250 // threshold (e.g., 10 km), you can use the IsDistanceLess() method. This is 251 // much faster than actually calculating the distance with FindEdge, 252 // since the implementation can stop as soon as it can prove that the minimum 253 // distance is either above or below the threshold. 254 func NewClosestEdgeQuery(index *ShapeIndex, opts *EdgeQueryOptions) *EdgeQuery { 255 if opts == nil { 256 opts = NewClosestEdgeQueryOptions() 257 } 258 e := &EdgeQuery{ 259 testedEdges: make(map[ShapeEdgeID]uint32), 260 index: index, 261 opts: opts.common, 262 queue: newQueryQueue(), 263 } 264 265 return e 266 } 267 268 // NewFurthestEdgeQuery returns an EdgeQuery that is used for finding the 269 // furthest edge(s) to a given Point, Edge, Cell, or geometry collection. 270 // 271 // The furthest edge is defined as the one which maximizes the 272 // distance from any point on that edge to any point on the target geometry. 273 // 274 // Similar to the example in NewClosestEdgeQuery, to find the 5 furthest edges 275 // from a given Point: 276 func NewFurthestEdgeQuery(index *ShapeIndex, opts *EdgeQueryOptions) *EdgeQuery { 277 if opts == nil { 278 opts = NewFurthestEdgeQueryOptions() 279 } 280 e := &EdgeQuery{ 281 testedEdges: make(map[ShapeEdgeID]uint32), 282 index: index, 283 opts: opts.common, 284 queue: newQueryQueue(), 285 } 286 287 return e 288 } 289 290 // Reset resets the state of this EdgeQuery. 291 func (e *EdgeQuery) Reset() { 292 e.indexNumEdges = 0 293 e.indexNumEdgesLimit = 0 294 e.indexCovering = nil 295 e.indexCells = nil 296 } 297 298 // FindEdges returns the edges for the given target that satisfy the current options. 299 // 300 // Note that if opts.IncludeInteriors is true, the results may include some 301 // entries with edge_id == -1. This indicates that the target intersects 302 // the indexed polygon with the given ShapeID. 303 func (e *EdgeQuery) FindEdges(target distanceTarget) []EdgeQueryResult { 304 return e.findEdges(target, e.opts) 305 } 306 307 // Distance reports the distance to the target. If the index or target is empty, 308 // returns the EdgeQuery's maximal sentinel. 309 // 310 // Use IsDistanceLess()/IsDistanceGreater() if you only want to compare the 311 // distance against a threshold value, since it is often much faster. 312 func (e *EdgeQuery) Distance(target distanceTarget) s1.ChordAngle { 313 return e.findEdge(target, e.opts).Distance() 314 } 315 316 // IsDistanceLess reports if the distance to target is less than the given limit. 317 // 318 // This method is usually much faster than Distance(), since it is much 319 // less work to determine whether the minimum distance is above or below a 320 // threshold than it is to calculate the actual minimum distance. 321 // 322 // If you wish to check if the distance is less than or equal to the limit, use: 323 // 324 // query.IsDistanceLess(target, limit.Successor()) 325 func (e *EdgeQuery) IsDistanceLess(target distanceTarget, limit s1.ChordAngle) bool { 326 opts := e.opts 327 opts = opts.MaxResults(1). 328 DistanceLimit(limit). 329 MaxError(s1.StraightChordAngle) 330 return !e.findEdge(target, opts).IsEmpty() 331 } 332 333 // IsDistanceGreater reports if the distance to target is greater than limit. 334 // 335 // This method is usually much faster than Distance, since it is much 336 // less work to determine whether the maximum distance is above or below a 337 // threshold than it is to calculate the actual maximum distance. 338 // If you wish to check if the distance is less than or equal to the limit, use: 339 // 340 // query.IsDistanceGreater(target, limit.Predecessor()) 341 func (e *EdgeQuery) IsDistanceGreater(target distanceTarget, limit s1.ChordAngle) bool { 342 return e.IsDistanceLess(target, limit) 343 } 344 345 // IsConservativeDistanceLessOrEqual reports if the distance to target is less 346 // or equal to the limit, where the limit has been expanded by the maximum error 347 // for the distance calculation. 348 // 349 // For example, suppose that we want to test whether two geometries might 350 // intersect each other after they are snapped together using Builder 351 // (using the IdentitySnapFunction with a given "snap radius"). Since 352 // Builder uses exact distance predicates (s2predicates), we need to 353 // measure the distance between the two geometries conservatively. If the 354 // distance is definitely greater than "snap radius", then the geometries 355 // are guaranteed to not intersect after snapping. 356 func (e *EdgeQuery) IsConservativeDistanceLessOrEqual(target distanceTarget, limit s1.ChordAngle) bool { 357 return e.IsDistanceLess(target, limit.Expanded(minUpdateDistanceMaxError(limit))) 358 } 359 360 // IsConservativeDistanceGreaterOrEqual reports if the distance to the target is greater 361 // than or equal to the given limit with some small tolerance. 362 func (e *EdgeQuery) IsConservativeDistanceGreaterOrEqual(target distanceTarget, limit s1.ChordAngle) bool { 363 return e.IsDistanceGreater(target, limit.Expanded(-minUpdateDistanceMaxError(limit))) 364 } 365 366 // findEdges returns the closest edges to the given target that satisfy the given options. 367 // 368 // Note that if opts.includeInteriors is true, the results may include some 369 // entries with edgeID == -1. This indicates that the target intersects the 370 // indexed polygon with the given shapeID. 371 func (e *EdgeQuery) findEdges(target distanceTarget, opts *queryOptions) []EdgeQueryResult { 372 e.findEdgesInternal(target, opts) 373 // TODO(roberts): Revisit this if there is a heap or other sorted and 374 // uniquing datastructure we can use instead of just a slice. 375 e.results = sortAndUniqueResults(e.results) 376 if len(e.results) > e.opts.maxResults { 377 e.results = e.results[:e.opts.maxResults] 378 } 379 return e.results 380 } 381 382 func sortAndUniqueResults(results []EdgeQueryResult) []EdgeQueryResult { 383 if len(results) <= 1 { 384 return results 385 } 386 sort.Slice(results, func(i, j int) bool { return results[i].Less(results[j]) }) 387 j := 0 388 for i := 1; i < len(results); i++ { 389 if results[j] == results[i] { 390 continue 391 } 392 j++ 393 results[j] = results[i] 394 } 395 return results[:j+1] 396 } 397 398 // findEdge is a convenience method that returns exactly one edge, and if no 399 // edges satisfy the given search criteria, then a default Result is returned. 400 // 401 // This is primarily to ease the usage of a number of the methods in the DistanceTargets 402 // and in EdgeQuery. 403 func (e *EdgeQuery) findEdge(target distanceTarget, opts *queryOptions) EdgeQueryResult { 404 opts.MaxResults(1) 405 e.findEdges(target, opts) 406 if len(e.results) > 0 { 407 return e.results[0] 408 } 409 410 return newEdgeQueryResult(target) 411 } 412 413 // findEdgesInternal does the actual work for find edges that match the given options. 414 func (e *EdgeQuery) findEdgesInternal(target distanceTarget, opts *queryOptions) { 415 e.target = target 416 e.opts = opts 417 418 e.testedEdges = make(map[ShapeEdgeID]uint32) 419 e.distanceLimit = target.distance().fromChordAngle(opts.distanceLimit) 420 e.results = make([]EdgeQueryResult, 0) 421 422 if e.distanceLimit == target.distance().zero() { 423 return 424 } 425 426 if opts.includeInteriors { 427 shapeIDs := map[int32]struct{}{} 428 e.target.visitContainingShapes(e.index, func(containingShape Shape, targetPoint Point) bool { 429 shapeIDs[e.index.idForShape(containingShape)] = struct{}{} 430 return len(shapeIDs) < opts.maxResults 431 }) 432 for shapeID := range shapeIDs { 433 e.addResult(EdgeQueryResult{target.distance().zero(), shapeID, -1}) 434 } 435 436 if e.distanceLimit == target.distance().zero() { 437 return 438 } 439 } 440 441 // If maxError > 0 and the target takes advantage of this, then we may 442 // need to adjust the distance estimates to ShapeIndex cells to ensure 443 // that they are always a lower bound on the true distance. For example, 444 // suppose max_distance == 100, maxError == 30, and we compute the distance 445 // to the target from some cell C0 as d(C0) == 80. Then because the target 446 // takes advantage of maxError, the true distance could be as low as 50. 447 // In order not to miss edges contained by such cells, we need to subtract 448 // maxError from the distance estimates. This behavior is controlled by 449 // the useConservativeCellDistance flag. 450 // 451 // However there is one important case where this adjustment is not 452 // necessary, namely when distanceLimit < maxError, This is because 453 // maxError only affects the algorithm once at least maxEdges edges 454 // have been found that satisfy the given distance limit. At that point, 455 // maxError is subtracted from distanceLimit in order to ensure that 456 // any further matches are closer by at least that amount. But when 457 // distanceLimit < maxError, this reduces the distance limit to 0, 458 // i.e. all remaining candidate cells and edges can safely be discarded. 459 // (This is how IsDistanceLess() and friends are implemented.) 460 targetUsesMaxError := opts.maxError != target.distance().zero().chordAngle() && 461 e.target.setMaxError(opts.maxError) 462 463 // Note that we can't compare maxError and distanceLimit directly 464 // because one is a Delta and one is a Distance. Instead we subtract them. 465 e.useConservativeCellDistance = targetUsesMaxError && 466 (e.distanceLimit == target.distance().infinity() || 467 target.distance().zero().less(e.distanceLimit.sub(target.distance().fromChordAngle(opts.maxError)))) 468 469 // Use the brute force algorithm if the index is small enough. To avoid 470 // spending too much time counting edges when there are many shapes, we stop 471 // counting once there are too many edges. We may need to recount the edges 472 // if we later see a target with a larger brute force edge threshold. 473 minOptimizedEdges := e.target.maxBruteForceIndexSize() + 1 474 if minOptimizedEdges > e.indexNumEdgesLimit && e.indexNumEdges >= e.indexNumEdgesLimit { 475 e.indexNumEdges = e.index.NumEdgesUpTo(minOptimizedEdges) 476 e.indexNumEdgesLimit = minOptimizedEdges 477 } 478 479 if opts.useBruteForce || e.indexNumEdges < minOptimizedEdges { 480 // The brute force algorithm already considers each edge exactly once. 481 e.avoidDuplicates = false 482 e.findEdgesBruteForce() 483 } else { 484 // If the target takes advantage of maxError then we need to avoid 485 // duplicate edges explicitly. (Otherwise it happens automatically.) 486 e.avoidDuplicates = targetUsesMaxError && opts.maxResults > 1 487 e.findEdgesOptimized() 488 } 489 } 490 491 func (e *EdgeQuery) addResult(r EdgeQueryResult) { 492 e.results = append(e.results, r) 493 if e.opts.maxResults == 1 { 494 // Optimization for the common case where only the closest edge is wanted. 495 e.distanceLimit = r.distance.sub(e.target.distance().fromChordAngle(e.opts.maxError)) 496 } 497 // TODO(roberts): Add the other if/else cases when a different data structure 498 // is used for the results. 499 } 500 501 func (e *EdgeQuery) maybeAddResult(shape Shape, edgeID int32) { 502 if _, ok := e.testedEdges[ShapeEdgeID{e.index.idForShape(shape), edgeID}]; e.avoidDuplicates && !ok { 503 return 504 } 505 edge := shape.Edge(int(edgeID)) 506 dist := e.distanceLimit 507 508 if dist, ok := e.target.updateDistanceToEdge(edge, dist); ok { 509 e.addResult(EdgeQueryResult{dist, e.index.idForShape(shape), edgeID}) 510 } 511 } 512 513 func (e *EdgeQuery) findEdgesBruteForce() { 514 // Range over all shapes in the index. Does order matter here? if so 515 // switch to for i = 0 .. n? 516 for _, shape := range e.index.shapes { 517 // TODO(roberts): can this happen if we are only ranging over current entries? 518 if shape == nil { 519 continue 520 } 521 for edgeID := int32(0); edgeID < int32(shape.NumEdges()); edgeID++ { 522 e.maybeAddResult(shape, edgeID) 523 } 524 } 525 } 526 527 func (e *EdgeQuery) findEdgesOptimized() { 528 e.initQueue() 529 // Repeatedly find the closest Cell to "target" and either split it into 530 // its four children or process all of its edges. 531 for e.queue.size() > 0 { 532 // We need to copy the top entry before removing it, and we need to 533 // remove it before adding any new entries to the queue. 534 entry := e.queue.pop() 535 536 if !entry.distance.less(e.distanceLimit) { 537 e.queue.reset() // Clear any remaining entries. 538 break 539 } 540 // If this is already known to be an index cell, just process it. 541 if entry.indexCell != nil { 542 e.processEdges(entry) 543 continue 544 } 545 // Otherwise split the cell into its four children. Before adding a 546 // child back to the queue, we first check whether it is empty. We do 547 // this in two seek operations rather than four by seeking to the key 548 // between children 0 and 1 and to the key between children 2 and 3. 549 id := entry.id 550 ch := id.Children() 551 e.iter.seek(ch[1].RangeMin()) 552 553 if !e.iter.Done() && e.iter.CellID() <= ch[1].RangeMax() { 554 e.processOrEnqueueCell(ch[1]) 555 } 556 if e.iter.Prev() && e.iter.CellID() >= id.RangeMin() { 557 e.processOrEnqueueCell(ch[0]) 558 } 559 560 e.iter.seek(ch[3].RangeMin()) 561 if !e.iter.Done() && e.iter.CellID() <= id.RangeMax() { 562 e.processOrEnqueueCell(ch[3]) 563 } 564 if e.iter.Prev() && e.iter.CellID() >= ch[2].RangeMin() { 565 e.processOrEnqueueCell(ch[2]) 566 } 567 } 568 } 569 570 func (e *EdgeQuery) processOrEnqueueCell(id CellID) { 571 if e.iter.CellID() == id { 572 e.processOrEnqueue(id, e.iter.IndexCell()) 573 } else { 574 e.processOrEnqueue(id, nil) 575 } 576 } 577 578 func (e *EdgeQuery) initQueue() { 579 if len(e.indexCovering) == 0 { 580 // We delay iterator initialization until now to make queries on very 581 // small indexes a bit faster (i.e., where brute force is used). 582 e.iter = NewShapeIndexIterator(e.index) 583 } 584 585 // Optimization: if the user is searching for just the closest edge, and the 586 // center of the target's bounding cap happens to intersect an index cell, 587 // then we try to limit the search region to a small disc by first 588 // processing the edges in that cell. This sets distance_limit_ based on 589 // the closest edge in that cell, which we can then use to limit the search 590 // area. This means that the cell containing "target" will be processed 591 // twice, but in general this is still faster. 592 // 593 // TODO(roberts): Even if the cap center is not contained, we could still 594 // process one or both of the adjacent index cells in CellID order, 595 // provided that those cells are closer than distanceLimit. 596 cb := e.target.capBound() 597 if cb.IsEmpty() { 598 return // Empty target. 599 } 600 601 if e.opts.maxResults == 1 && e.iter.LocatePoint(cb.Center()) { 602 e.processEdges(&queryQueueEntry{ 603 distance: e.target.distance().zero(), 604 id: e.iter.CellID(), 605 indexCell: e.iter.IndexCell(), 606 }) 607 // Skip the rest of the algorithm if we found an intersecting edge. 608 if e.distanceLimit == e.target.distance().zero() { 609 return 610 } 611 } 612 if len(e.indexCovering) == 0 { 613 e.initCovering() 614 } 615 if e.distanceLimit == e.target.distance().infinity() { 616 // Start with the precomputed index covering. 617 for i := range e.indexCovering { 618 e.processOrEnqueue(e.indexCovering[i], e.indexCells[i]) 619 } 620 } else { 621 // Compute a covering of the search disc and intersect it with the 622 // precomputed index covering. 623 coverer := &RegionCoverer{MaxCells: 4, LevelMod: 1, MaxLevel: MaxLevel} 624 625 radius := cb.Radius() + e.distanceLimit.chordAngleBound().Angle() 626 searchCB := CapFromCenterAngle(cb.Center(), radius) 627 maxDistCover := coverer.FastCovering(searchCB) 628 e.initialCells = CellUnionFromIntersection(e.indexCovering, maxDistCover) 629 630 // Now we need to clean up the initial cells to ensure that they all 631 // contain at least one cell of the ShapeIndex. (Some may not intersect 632 // the index at all, while other may be descendants of an index cell.) 633 i, j := 0, 0 634 for i < len(e.initialCells) { 635 idI := e.initialCells[i] 636 // Find the top-level cell that contains this initial cell. 637 for e.indexCovering[j].RangeMax() < idI { 638 j++ 639 } 640 641 idJ := e.indexCovering[j] 642 if idI == idJ { 643 // This initial cell is one of the top-level cells. Use the 644 // precomputed ShapeIndexCell pointer to avoid an index seek. 645 e.processOrEnqueue(idJ, e.indexCells[j]) 646 i++ 647 j++ 648 } else { 649 // This initial cell is a proper descendant of a top-level cell. 650 // Check how it is related to the cells of the ShapeIndex. 651 r := e.iter.LocateCellID(idI) 652 if r == Indexed { 653 // This cell is a descendant of an index cell. 654 // Enqueue it and skip any other initial cells 655 // that are also descendants of this cell. 656 e.processOrEnqueue(e.iter.CellID(), e.iter.IndexCell()) 657 lastID := e.iter.CellID().RangeMax() 658 for i < len(e.initialCells) && e.initialCells[i] <= lastID { 659 i++ 660 } 661 } else { 662 // Enqueue the cell only if it contains at least one index cell. 663 if r == Subdivided { 664 e.processOrEnqueue(idI, nil) 665 } 666 i++ 667 } 668 } 669 } 670 } 671 } 672 673 func (e *EdgeQuery) initCovering() { 674 // Find the range of Cells spanned by the index and choose a level such 675 // that the entire index can be covered with just a few cells. These are 676 // the "top-level" cells. There are two cases: 677 // 678 // - If the index spans more than one face, then there is one top-level cell 679 // per spanned face, just big enough to cover the index cells on that face. 680 // 681 // - If the index spans only one face, then we find the smallest cell "C" 682 // that covers the index cells on that face (just like the case above). 683 // Then for each of the 4 children of "C", if the child contains any index 684 // cells then we create a top-level cell that is big enough to just fit 685 // those index cells (i.e., shrinking the child as much as possible to fit 686 // its contents). This essentially replicates what would happen if we 687 // started with "C" as the top-level cell, since "C" would immediately be 688 // split, except that we take the time to prune the children further since 689 // this will save work on every subsequent query. 690 e.indexCovering = make([]CellID, 0, 6) 691 692 // TODO(roberts): Use a single iterator below and save position 693 // information using pair {CellID, ShapeIndexCell}. 694 next := NewShapeIndexIterator(e.index, IteratorBegin) 695 last := NewShapeIndexIterator(e.index, IteratorEnd) 696 last.Prev() 697 if next.CellID() != last.CellID() { 698 // The index has at least two cells. Choose a level such that the entire 699 // index can be spanned with at most 6 cells (if the index spans multiple 700 // faces) or 4 cells (it the index spans a single face). 701 level, ok := next.CellID().CommonAncestorLevel(last.CellID()) 702 if !ok { 703 level = 0 704 } else { 705 level++ 706 } 707 708 // Visit each potential top-level cell except the last (handled below). 709 lastID := last.CellID().Parent(level) 710 for id := next.CellID().Parent(level); id != lastID; id = id.Next() { 711 // Skip any top-level cells that don't contain any index cells. 712 if id.RangeMax() < next.CellID() { 713 continue 714 } 715 716 // Find the range of index cells contained by this top-level cell and 717 // then shrink the cell if necessary so that it just covers them. 718 cellFirst := next.clone() 719 next.seek(id.RangeMax().Next()) 720 cellLast := next.clone() 721 cellLast.Prev() 722 e.addInitialRange(cellFirst, cellLast) 723 break 724 } 725 726 } 727 e.addInitialRange(next, last) 728 } 729 730 // addInitialRange adds an entry to the indexCovering and indexCells that covers the given 731 // inclusive range of cells. 732 // 733 // This requires that first and last cells have a common ancestor. 734 func (e *EdgeQuery) addInitialRange(first, last *ShapeIndexIterator) { 735 if first.CellID() == last.CellID() { 736 // The range consists of a single index cell. 737 e.indexCovering = append(e.indexCovering, first.CellID()) 738 e.indexCells = append(e.indexCells, first.IndexCell()) 739 } else { 740 // Add the lowest common ancestor of the given range. 741 level, _ := first.CellID().CommonAncestorLevel(last.CellID()) 742 e.indexCovering = append(e.indexCovering, first.CellID().Parent(level)) 743 e.indexCells = append(e.indexCells, nil) 744 } 745 } 746 747 // processEdges processes all the edges of the given index cell. 748 func (e *EdgeQuery) processEdges(entry *queryQueueEntry) { 749 for _, clipped := range entry.indexCell.shapes { 750 shape := e.index.Shape(clipped.shapeID) 751 for j := 0; j < clipped.numEdges(); j++ { 752 e.maybeAddResult(shape, int32(clipped.edges[j])) 753 } 754 } 755 } 756 757 // processOrEnqueue the given cell id and indexCell. 758 func (e *EdgeQuery) processOrEnqueue(id CellID, indexCell *ShapeIndexCell) { 759 if indexCell != nil { 760 // If this index cell has only a few edges, then it is faster to check 761 // them directly rather than computing the minimum distance to the Cell 762 // and inserting it into the queue. 763 const minEdgesToEnqueue = 10 764 numEdges := indexCell.numEdges() 765 if numEdges == 0 { 766 return 767 } 768 if numEdges < minEdgesToEnqueue { 769 // Set "distance" to zero to avoid the expense of computing it. 770 e.processEdges(&queryQueueEntry{ 771 distance: e.target.distance().zero(), 772 id: id, 773 indexCell: indexCell, 774 }) 775 return 776 } 777 } 778 779 // Otherwise compute the minimum distance to any point in the cell and add 780 // it to the priority queue. 781 cell := CellFromCellID(id) 782 dist := e.distanceLimit 783 var ok bool 784 if dist, ok = e.target.updateDistanceToCell(cell, dist); !ok { 785 return 786 } 787 if e.useConservativeCellDistance { 788 // Ensure that "distance" is a lower bound on the true distance to the cell. 789 dist = dist.sub(e.target.distance().fromChordAngle(e.opts.maxError)) 790 } 791 792 e.queue.push(&queryQueueEntry{ 793 distance: dist, 794 id: id, 795 indexCell: indexCell, 796 }) 797 } 798 799 // TODO(roberts): Remaining pieces 800 // GetEdge 801 // Project 802