diff options
Diffstat (limited to 'vendor/github.com/golang/geo/s2/distance_target.go')
-rw-r--r-- | vendor/github.com/golang/geo/s2/distance_target.go | 149 |
1 files changed, 149 insertions, 0 deletions
diff --git a/vendor/github.com/golang/geo/s2/distance_target.go b/vendor/github.com/golang/geo/s2/distance_target.go new file mode 100644 index 000000000..066bbacfa --- /dev/null +++ b/vendor/github.com/golang/geo/s2/distance_target.go @@ -0,0 +1,149 @@ +// 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 ( + "github.com/golang/geo/s1" +) + +// The distance interface represents a set of common methods used by algorithms +// that compute distances between various S2 types. +type distance interface { + // chordAngle returns this type as a ChordAngle. + chordAngle() s1.ChordAngle + + // fromChordAngle is used to type convert a ChordAngle to this type. + // This is to work around needing to be clever in parts of the code + // where a distanceTarget interface method expects distances, but the + // user only supplies a ChordAngle, and we need to dynamically cast it + // to an appropriate distance interface types. + fromChordAngle(o s1.ChordAngle) distance + + // zero returns a zero distance. + zero() distance + // negative returns a value smaller than any valid value. + negative() distance + // infinity returns a value larger than any valid value. + infinity() distance + + // less is similar to the Less method in Sort. To get minimum values, + // this would be a less than type operation. For maximum, this would + // be a greater than type operation. + less(other distance) bool + + // sub subtracts the other value from this one and returns the new value. + // This is done as a method and not simple mathematical operation to + // allow closest and furthest to implement this in opposite ways. + sub(other distance) distance + + // chordAngleBound reports the upper bound on a ChordAngle corresponding + // to this distance. For example, if distance measures WGS84 ellipsoid + // distance then the corresponding angle needs to be 0.56% larger. + chordAngleBound() s1.ChordAngle + + // updateDistance may update the value this distance represents + // based on the given input. The updated value and a boolean reporting + // if the value was changed are returned. + updateDistance(other distance) (distance, bool) +} + +// distanceTarget is an interface that represents a geometric type to which distances +// are measured. +// +// For example, there are implementations that measure distances to a Point, +// an Edge, a Cell, a CellUnion, and even to an arbitrary collection of geometry +// stored in ShapeIndex. +// +// The distanceTarget types are provided for the benefit of types that measure +// distances and/or find nearby geometry, such as ClosestEdgeQuery, FurthestEdgeQuery, +// ClosestPointQuery, and ClosestCellQuery, etc. +type distanceTarget interface { + // capBound returns a Cap that bounds the set of points whose distance to the + // target is distance.zero(). + capBound() Cap + + // updateDistanceToPoint updates the distance if the distance to + // the point P is within than the given dist. + // The boolean reports if the value was updated. + updateDistanceToPoint(p Point, dist distance) (distance, bool) + + // updateDistanceToEdge updates the distance if the distance to + // the edge E is within than the given dist. + // The boolean reports if the value was updated. + updateDistanceToEdge(e Edge, dist distance) (distance, bool) + + // updateDistanceToCell updates the distance if the distance to the cell C + // (including its interior) is within than the given dist. + // The boolean reports if the value was updated. + updateDistanceToCell(c Cell, dist distance) (distance, bool) + + // setMaxError potentially updates the value of MaxError, and reports if + // the specific type supports altering it. Whenever one of the + // updateDistanceTo... methods above returns true, the returned distance + // is allowed to be up to maxError larger than the true minimum distance. + // In other words, it gives this target object permission to terminate its + // distance calculation as soon as it has determined that (1) the minimum + // distance is less than minDist and (2) the best possible further + // improvement is less than maxError. + // + // If the target takes advantage of maxError to optimize its distance + // calculation, this method must return true. (Most target types will + // default to return false.) + setMaxError(maxErr s1.ChordAngle) bool + + // maxBruteForceIndexSize reports the maximum number of indexed objects for + // which it is faster to compute the distance by brute force (e.g., by testing + // every edge) rather than by using an index. + // + // The following method is provided as a convenience for types that compute + // distances to a collection of indexed geometry, such as ClosestEdgeQuery + // and ClosestPointQuery. + // + // Types that do not support this should return a -1. + maxBruteForceIndexSize() int + + // distance returns an instance of the underlying distance type this + // target uses. This is to work around the use of Templates in the C++. + distance() distance + + // visitContainingShapes finds all polygons in the given index that + // completely contain a connected component of the target geometry. (For + // example, if the target consists of 10 points, this method finds + // polygons that contain any of those 10 points.) For each such polygon, + // the visit function is called with the Shape of the polygon along with + // a point of the target geometry that is contained by that polygon. + // + // Optionally, any polygon that intersects the target geometry may also be + // returned. In other words, this method returns all polygons that + // contain any connected component of the target, along with an arbitrary + // subset of the polygons that intersect the target. + // + // For example, suppose that the index contains two abutting polygons + // A and B. If the target consists of two points "a" contained by A and + // "b" contained by B, then both A and B are returned. But if the target + // consists of the edge "ab", then any subset of {A, B} could be returned + // (because both polygons intersect the target but neither one contains + // the edge "ab"). + // + // If the visit function returns false, this method terminates early and + // returns false as well. Otherwise returns true. + // + // NOTE(roberts): This method exists only for the purpose of implementing + // edgeQuery IncludeInteriors efficiently. + visitContainingShapes(index *ShapeIndex, v shapePointVisitorFunc) bool +} + +// shapePointVisitorFunc defines a type of function the visitContainingShapes can call. +type shapePointVisitorFunc func(containingShape Shape, targetPoint Point) bool |