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 "math" 19 20 "github.com/golang/geo/s1" 21 ) 22 23 const maxQueryResults = math.MaxInt32 24 25 // queryOptions represents the set of all configurable parameters used by all of 26 // the Query types. Most of these fields have non-zero defaults, so initialization 27 // is handled within each Query type. All of the exported methods accept user 28 // supplied sets of options to set or adjust as necessary. 29 // 30 // Several of the defaults depend on the distance interface type being used 31 // (e.g. minDistance, maxDistance, etc.) 32 // 33 // If a user sets an option value that a given query type doesn't use, it is ignored. 34 type queryOptions struct { 35 // maxResults specifies that at most MaxResults edges should be returned. 36 // This must be at least 1. 37 // 38 // The default value is to return all results. 39 maxResults int 40 41 // distanceLimit specifies that only edges whose distance to the target is 42 // within this distance should be returned. 43 // 44 // Note that edges whose distance is exactly equal to this are 45 // not returned. In most cases this doesn't matter (since distances are 46 // not computed exactly in the first place), but if such edges are needed 47 // then you can retrieve them by specifying the distance as the next 48 // largest representable distance. i.e. distanceLimit.Successor(). 49 // 50 // The default value is the infinity value, such that all results will be 51 // returned. 52 distanceLimit s1.ChordAngle 53 54 // maxError specifies that edges up to MaxError further away than the true 55 // closest edges may be substituted in the result set, as long as such 56 // edges satisfy all the remaining search criteria (such as DistanceLimit). 57 // This option only has an effect if MaxResults is also specified; 58 // otherwise all edges closer than MaxDistance will always be returned. 59 // 60 // Note that this does not affect how the distance between edges is 61 // computed; it simply gives the algorithm permission to stop the search 62 // early as soon as the best possible improvement drops below MaxError. 63 // 64 // This can be used to implement distance predicates efficiently. For 65 // example, to determine whether the minimum distance is less than D, set 66 // MaxResults == 1 and MaxDistance == MaxError == D. This causes 67 // the algorithm to terminate as soon as it finds any edge whose distance 68 // is less than D, rather than continuing to search for an edge that is 69 // even closer. 70 // 71 // The default value is zero. 72 maxError s1.ChordAngle 73 74 // includeInteriors specifies that polygon interiors should be included 75 // when measuring distances. In other words, polygons that contain the target 76 // should have a distance of zero. (For targets consisting of multiple connected 77 // components, the distance is zero if any component is contained.) This 78 // is indicated in the results by returning a (ShapeID, EdgeID) pair 79 // with EdgeID == -1, i.e. this value denotes the polygons's interior. 80 // 81 // Note that for efficiency, any polygon that intersects the target may or 82 // may not have an EdgeID == -1 result. Such results are optional 83 // because in that case the distance to the polygon is already zero. 84 // 85 // The default value is true. 86 includeInteriors bool 87 88 // specifies that distances should be computed by examining every edge 89 // rather than using the ShapeIndex. 90 // 91 // TODO(roberts): When optimized is implemented, update the default to false. 92 // The default value is true. 93 useBruteForce bool 94 95 // region specifies that results must intersect the given Region. 96 // 97 // Note that if you want to set the region to a disc around a target 98 // point, it is faster to use a PointTarget with distanceLimit set 99 // instead. You can also set a distance limit and also require that results 100 // lie within a given rectangle. 101 // 102 // The default is nil (no region limits). 103 region Region 104 } 105 106 // UseBruteForce sets or disables the use of brute force in a query. 107 func (q *queryOptions) UseBruteForce(x bool) *queryOptions { 108 q.useBruteForce = x 109 return q 110 } 111 112 // IncludeInteriors specifies whether polygon interiors should be 113 // included when measuring distances. 114 func (q *queryOptions) IncludeInteriors(x bool) *queryOptions { 115 q.includeInteriors = x 116 return q 117 } 118 119 // MaxError specifies that edges up to dist away than the true 120 // matching edges may be substituted in the result set, as long as such 121 // edges satisfy all the remaining search criteria (such as DistanceLimit). 122 // This option only has an effect if MaxResults is also specified; 123 // otherwise all edges closer than MaxDistance will always be returned. 124 func (q *queryOptions) MaxError(x s1.ChordAngle) *queryOptions { 125 q.maxError = x 126 return q 127 } 128 129 // MaxResults specifies that at most MaxResults edges should be returned. 130 // This must be at least 1. 131 func (q *queryOptions) MaxResults(x int) *queryOptions { 132 // TODO(roberts): What should be done if the value is <= 0? 133 q.maxResults = int(x) 134 return q 135 } 136 137 // DistanceLimit specifies that only edges whose distance to the target is 138 // within, this distance should be returned. Edges whose distance is equal 139 // are not returned. 140 // 141 // To include values that are equal, specify the limit with the next largest 142 // representable distance such as limit.Successor(), or set the option with 143 // Furthest/ClosestInclusiveDistanceLimit. 144 func (q *queryOptions) DistanceLimit(x s1.ChordAngle) *queryOptions { 145 q.distanceLimit = x 146 return q 147 } 148 149 // ClosestInclusiveDistanceLimit sets the distance limit such that results whose 150 // distance is exactly equal to the limit are also returned. 151 func (q *queryOptions) ClosestInclusiveDistanceLimit(limit s1.ChordAngle) *queryOptions { 152 q.distanceLimit = limit.Successor() 153 return q 154 } 155 156 // FurthestInclusiveDistanceLimit sets the distance limit such that results whose 157 // distance is exactly equal to the limit are also returned. 158 func (q *queryOptions) FurthestInclusiveDistanceLimit(limit s1.ChordAngle) *queryOptions { 159 q.distanceLimit = limit.Predecessor() 160 return q 161 } 162 163 // ClosestConservativeDistanceLimit sets the distance limit such that results 164 // also incorporates the error in distance calculations. This ensures that all 165 // edges whose true distance is less than or equal to limit will be returned 166 // (along with some edges whose true distance is slightly greater). 167 // 168 // Algorithms that need to do exact distance comparisons can use this 169 // option to find a set of candidate edges that can then be filtered 170 // further (e.g., using CompareDistance). 171 func (q *queryOptions) ClosestConservativeDistanceLimit(limit s1.ChordAngle) *queryOptions { 172 q.distanceLimit = limit.Expanded(minUpdateDistanceMaxError(limit)) 173 return q 174 } 175 176 // FurthestConservativeDistanceLimit sets the distance limit such that results 177 // also incorporates the error in distance calculations. This ensures that all 178 // edges whose true distance is greater than or equal to limit will be returned 179 // (along with some edges whose true distance is slightly less). 180 func (q *queryOptions) FurthestConservativeDistanceLimit(limit s1.ChordAngle) *queryOptions { 181 q.distanceLimit = limit.Expanded(-minUpdateDistanceMaxError(limit)) 182 return q 183 } 184 185 // newQueryOptions returns a set of options using the given distance type 186 // with the proper default values. 187 func newQueryOptions(d distance) *queryOptions { 188 return &queryOptions{ 189 maxResults: maxQueryResults, 190 distanceLimit: d.infinity().chordAngle(), 191 maxError: 0, 192 includeInteriors: true, 193 useBruteForce: false, 194 region: nil, 195 } 196 } 197