min_distance_targets.go (13996B)
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 // minDistance implements distance interface to find closest distance types. 24 type minDistance s1.ChordAngle 25 26 func (m minDistance) chordAngle() s1.ChordAngle { return s1.ChordAngle(m) } 27 func (m minDistance) zero() distance { return minDistance(0) } 28 func (m minDistance) negative() distance { return minDistance(s1.NegativeChordAngle) } 29 func (m minDistance) infinity() distance { return minDistance(s1.InfChordAngle()) } 30 func (m minDistance) less(other distance) bool { return m.chordAngle() < other.chordAngle() } 31 func (m minDistance) sub(other distance) distance { 32 return minDistance(m.chordAngle() - other.chordAngle()) 33 } 34 func (m minDistance) chordAngleBound() s1.ChordAngle { 35 return m.chordAngle().Expanded(m.chordAngle().MaxAngleError()) 36 } 37 38 // updateDistance updates its own value if the other value is less() than it is, 39 // and reports if it updated. 40 func (m minDistance) updateDistance(dist distance) (distance, bool) { 41 if dist.less(m) { 42 m = minDistance(dist.chordAngle()) 43 return m, true 44 } 45 return m, false 46 } 47 48 func (m minDistance) fromChordAngle(o s1.ChordAngle) distance { 49 return minDistance(o) 50 } 51 52 // MinDistanceToPointTarget is a type for computing the minimum distance to a Point. 53 type MinDistanceToPointTarget struct { 54 point Point 55 dist distance 56 } 57 58 // NewMinDistanceToPointTarget returns a new target for the given Point. 59 func NewMinDistanceToPointTarget(point Point) *MinDistanceToPointTarget { 60 m := minDistance(0) 61 return &MinDistanceToPointTarget{point: point, dist: &m} 62 } 63 64 func (m *MinDistanceToPointTarget) capBound() Cap { 65 return CapFromCenterChordAngle(m.point, s1.ChordAngle(0)) 66 } 67 68 func (m *MinDistanceToPointTarget) updateDistanceToPoint(p Point, dist distance) (distance, bool) { 69 var ok bool 70 dist, ok = dist.updateDistance(minDistance(ChordAngleBetweenPoints(p, m.point))) 71 return dist, ok 72 } 73 74 func (m *MinDistanceToPointTarget) updateDistanceToEdge(edge Edge, dist distance) (distance, bool) { 75 if d, ok := UpdateMinDistance(m.point, edge.V0, edge.V1, dist.chordAngle()); ok { 76 dist, _ = dist.updateDistance(minDistance(d)) 77 return dist, true 78 } 79 return dist, false 80 } 81 82 func (m *MinDistanceToPointTarget) updateDistanceToCell(cell Cell, dist distance) (distance, bool) { 83 var ok bool 84 dist, ok = dist.updateDistance(minDistance(cell.Distance(m.point))) 85 return dist, ok 86 } 87 88 func (m *MinDistanceToPointTarget) visitContainingShapes(index *ShapeIndex, v shapePointVisitorFunc) bool { 89 // For furthest points, we visit the polygons whose interior contains 90 // the antipode of the target point. These are the polygons whose 91 // distance to the target is maxDistance.zero() 92 q := NewContainsPointQuery(index, VertexModelSemiOpen) 93 return q.visitContainingShapes(m.point, func(shape Shape) bool { 94 return v(shape, m.point) 95 }) 96 } 97 98 func (m *MinDistanceToPointTarget) setMaxError(maxErr s1.ChordAngle) bool { return false } 99 func (m *MinDistanceToPointTarget) maxBruteForceIndexSize() int { return 30 } 100 func (m *MinDistanceToPointTarget) distance() distance { return m.dist } 101 102 // ---------------------------------------------------------- 103 104 // MinDistanceToEdgeTarget is a type for computing the minimum distance to an Edge. 105 type MinDistanceToEdgeTarget struct { 106 e Edge 107 dist distance 108 } 109 110 // NewMinDistanceToEdgeTarget returns a new target for the given Edge. 111 func NewMinDistanceToEdgeTarget(e Edge) *MinDistanceToEdgeTarget { 112 m := minDistance(0) 113 return &MinDistanceToEdgeTarget{e: e, dist: m} 114 } 115 116 // capBound returns a Cap that bounds the antipode of the target. (This 117 // is the set of points whose maxDistance to the target is maxDistance.zero) 118 func (m *MinDistanceToEdgeTarget) capBound() Cap { 119 // The following computes a radius equal to half the edge length in an 120 // efficient and numerically stable way. 121 d2 := float64(ChordAngleBetweenPoints(m.e.V0, m.e.V1)) 122 r2 := (0.5 * d2) / (1 + math.Sqrt(1-0.25*d2)) 123 return CapFromCenterChordAngle(Point{m.e.V0.Add(m.e.V1.Vector).Normalize()}, s1.ChordAngleFromSquaredLength(r2)) 124 } 125 126 func (m *MinDistanceToEdgeTarget) updateDistanceToPoint(p Point, dist distance) (distance, bool) { 127 if d, ok := UpdateMinDistance(p, m.e.V0, m.e.V1, dist.chordAngle()); ok { 128 dist, _ = dist.updateDistance(minDistance(d)) 129 return dist, true 130 } 131 return dist, false 132 } 133 134 func (m *MinDistanceToEdgeTarget) updateDistanceToEdge(edge Edge, dist distance) (distance, bool) { 135 if d, ok := updateEdgePairMinDistance(m.e.V0, m.e.V1, edge.V0, edge.V1, dist.chordAngle()); ok { 136 dist, _ = dist.updateDistance(minDistance(d)) 137 return dist, true 138 } 139 return dist, false 140 } 141 142 func (m *MinDistanceToEdgeTarget) updateDistanceToCell(cell Cell, dist distance) (distance, bool) { 143 return dist.updateDistance(minDistance(cell.DistanceToEdge(m.e.V0, m.e.V1))) 144 } 145 146 func (m *MinDistanceToEdgeTarget) visitContainingShapes(index *ShapeIndex, v shapePointVisitorFunc) bool { 147 // We test the center of the edge in order to ensure that edge targets AB 148 // and BA yield identical results (which is not guaranteed by the API but 149 // users might expect). Other options would be to test both endpoints, or 150 // return different results for AB and BA in some cases. 151 target := NewMinDistanceToPointTarget(Point{m.e.V0.Add(m.e.V1.Vector).Normalize()}) 152 return target.visitContainingShapes(index, v) 153 } 154 155 func (m *MinDistanceToEdgeTarget) setMaxError(maxErr s1.ChordAngle) bool { return false } 156 func (m *MinDistanceToEdgeTarget) maxBruteForceIndexSize() int { return 30 } 157 func (m *MinDistanceToEdgeTarget) distance() distance { return m.dist } 158 159 // ---------------------------------------------------------- 160 161 // MinDistanceToCellTarget is a type for computing the minimum distance to a Cell. 162 type MinDistanceToCellTarget struct { 163 cell Cell 164 dist distance 165 } 166 167 // NewMinDistanceToCellTarget returns a new target for the given Cell. 168 func NewMinDistanceToCellTarget(cell Cell) *MinDistanceToCellTarget { 169 m := minDistance(0) 170 return &MinDistanceToCellTarget{cell: cell, dist: m} 171 } 172 173 func (m *MinDistanceToCellTarget) capBound() Cap { 174 return m.cell.CapBound() 175 } 176 177 func (m *MinDistanceToCellTarget) updateDistanceToPoint(p Point, dist distance) (distance, bool) { 178 return dist.updateDistance(minDistance(m.cell.Distance(p))) 179 } 180 181 func (m *MinDistanceToCellTarget) updateDistanceToEdge(edge Edge, dist distance) (distance, bool) { 182 return dist.updateDistance(minDistance(m.cell.DistanceToEdge(edge.V0, edge.V1))) 183 } 184 185 func (m *MinDistanceToCellTarget) updateDistanceToCell(cell Cell, dist distance) (distance, bool) { 186 return dist.updateDistance(minDistance(m.cell.DistanceToCell(cell))) 187 } 188 189 func (m *MinDistanceToCellTarget) visitContainingShapes(index *ShapeIndex, v shapePointVisitorFunc) bool { 190 // The simplest approach is simply to return the polygons that contain the 191 // cell center. Alternatively, if the index cell is smaller than the target 192 // cell then we could return all polygons that are present in the 193 // shapeIndexCell, but since the index is built conservatively this may 194 // include some polygons that don't quite intersect the cell. So we would 195 // either need to recheck for intersection more accurately, or weaken the 196 // VisitContainingShapes contract so that it only guarantees approximate 197 // intersection, neither of which seems like a good tradeoff. 198 target := NewMinDistanceToPointTarget(m.cell.Center()) 199 return target.visitContainingShapes(index, v) 200 } 201 func (m *MinDistanceToCellTarget) setMaxError(maxErr s1.ChordAngle) bool { return false } 202 func (m *MinDistanceToCellTarget) maxBruteForceIndexSize() int { return 30 } 203 func (m *MinDistanceToCellTarget) distance() distance { return m.dist } 204 205 // ---------------------------------------------------------- 206 207 /* 208 // MinDistanceToCellUnionTarget is a type for computing the minimum distance to a CellUnion. 209 type MinDistanceToCellUnionTarget struct { 210 cu CellUnion 211 query *ClosestCellQuery 212 dist distance 213 } 214 215 // NewMinDistanceToCellUnionTarget returns a new target for the given CellUnion. 216 func NewMinDistanceToCellUnionTarget(cu CellUnion) *MinDistanceToCellUnionTarget { 217 m := minDistance(0) 218 return &MinDistanceToCellUnionTarget{cu: cu, dist: m} 219 } 220 221 func (m *MinDistanceToCellUnionTarget) capBound() Cap { 222 return m.cu.CapBound() 223 } 224 225 func (m *MinDistanceToCellUnionTarget) updateDistanceToCell(cell Cell, dist distance) (distance, bool) { 226 m.query.opts.DistanceLimit = dist.chordAngle() 227 target := NewMinDistanceToPointTarget(p) 228 r := m.query.findEdge(target) 229 if r.ShapeID < 0 { 230 return dist, false 231 } 232 return minDistance(r.Distance), true 233 } 234 235 func (m *MinDistanceToCellUnionTarget) visitContainingShapes(index *ShapeIndex, v shapePointVisitorFunc) bool { 236 // We test the center of the edge in order to ensure that edge targets AB 237 // and BA yield identical results (which is not guaranteed by the API but 238 // users might expect). Other options would be to test both endpoints, or 239 // return different results for AB and BA in some cases. 240 target := NewMinDistanceToPointTarget(Point{m.e.V0.Add(m.e.V1.Vector).Normalize()}) 241 return target.visitContainingShapes(index, v) 242 } 243 func (m *MinDistanceToCellUnionTarget) setMaxError(maxErr s1.ChordAngle) bool { 244 m.query.opts.MaxError = maxErr 245 return true 246 } 247 func (m *MinDistanceToCellUnionTarget) maxBruteForceIndexSize() int { return 30 } 248 func (m *MinDistanceToCellUnionTarget) distance() distance { return m.dist } 249 */ 250 251 // ---------------------------------------------------------- 252 253 // MinDistanceToShapeIndexTarget is a type for computing the minimum distance to a ShapeIndex. 254 type MinDistanceToShapeIndexTarget struct { 255 index *ShapeIndex 256 query *EdgeQuery 257 dist distance 258 } 259 260 // NewMinDistanceToShapeIndexTarget returns a new target for the given ShapeIndex. 261 func NewMinDistanceToShapeIndexTarget(index *ShapeIndex) *MinDistanceToShapeIndexTarget { 262 m := minDistance(0) 263 return &MinDistanceToShapeIndexTarget{ 264 index: index, 265 dist: m, 266 query: NewClosestEdgeQuery(index, NewClosestEdgeQueryOptions()), 267 } 268 } 269 270 func (m *MinDistanceToShapeIndexTarget) capBound() Cap { 271 // TODO(roberts): Depends on ShapeIndexRegion existing. 272 // c := makeS2ShapeIndexRegion(m.index).CapBound() 273 // return CapFromCenterRadius(Point{c.Center.Mul(-1)}, c.Radius()) 274 panic("not implemented yet") 275 } 276 277 func (m *MinDistanceToShapeIndexTarget) updateDistanceToPoint(p Point, dist distance) (distance, bool) { 278 m.query.opts.distanceLimit = dist.chordAngle() 279 target := NewMinDistanceToPointTarget(p) 280 r := m.query.findEdge(target, m.query.opts) 281 if r.shapeID < 0 { 282 return dist, false 283 } 284 return r.distance, true 285 } 286 287 func (m *MinDistanceToShapeIndexTarget) updateDistanceToEdge(edge Edge, dist distance) (distance, bool) { 288 m.query.opts.distanceLimit = dist.chordAngle() 289 target := NewMinDistanceToEdgeTarget(edge) 290 r := m.query.findEdge(target, m.query.opts) 291 if r.shapeID < 0 { 292 return dist, false 293 } 294 return r.distance, true 295 } 296 297 func (m *MinDistanceToShapeIndexTarget) updateDistanceToCell(cell Cell, dist distance) (distance, bool) { 298 m.query.opts.distanceLimit = dist.chordAngle() 299 target := NewMinDistanceToCellTarget(cell) 300 r := m.query.findEdge(target, m.query.opts) 301 if r.shapeID < 0 { 302 return dist, false 303 } 304 return r.distance, true 305 } 306 307 // For target types consisting of multiple connected components (such as this one), 308 // this method should return the polygons containing the antipodal reflection of 309 // *any* connected component. (It is sufficient to test containment of one vertex per 310 // connected component, since this allows us to also return any polygon whose 311 // boundary has distance.zero() to the target.) 312 func (m *MinDistanceToShapeIndexTarget) visitContainingShapes(index *ShapeIndex, v shapePointVisitorFunc) bool { 313 // It is sufficient to find the set of chain starts in the target index 314 // (i.e., one vertex per connected component of edges) that are contained by 315 // the query index, except for one special case to handle full polygons. 316 // 317 // TODO(roberts): Do this by merge-joining the two ShapeIndexes. 318 for _, shape := range m.index.shapes { 319 numChains := shape.NumChains() 320 // Shapes that don't have any edges require a special case (below). 321 testedPoint := false 322 for c := 0; c < numChains; c++ { 323 chain := shape.Chain(c) 324 if chain.Length == 0 { 325 continue 326 } 327 testedPoint = true 328 target := NewMinDistanceToPointTarget(shape.ChainEdge(c, 0).V0) 329 if !target.visitContainingShapes(index, v) { 330 return false 331 } 332 } 333 if !testedPoint { 334 // Special case to handle full polygons. 335 ref := shape.ReferencePoint() 336 if !ref.Contained { 337 continue 338 } 339 target := NewMinDistanceToPointTarget(ref.Point) 340 if !target.visitContainingShapes(index, v) { 341 return false 342 } 343 } 344 } 345 return true 346 } 347 348 func (m *MinDistanceToShapeIndexTarget) setMaxError(maxErr s1.ChordAngle) bool { 349 m.query.opts.maxError = maxErr 350 return true 351 } 352 func (m *MinDistanceToShapeIndexTarget) maxBruteForceIndexSize() int { return 25 } 353 func (m *MinDistanceToShapeIndexTarget) distance() distance { return m.dist } 354 func (m *MinDistanceToShapeIndexTarget) setIncludeInteriors(b bool) { 355 m.query.opts.includeInteriors = b 356 } 357 func (m *MinDistanceToShapeIndexTarget) setUseBruteForce(b bool) { m.query.opts.useBruteForce = b } 358 359 // TODO(roberts): Remaining methods 360 // 361 // func (m *MinDistanceToShapeIndexTarget) capBound() Cap { 362 // CellUnionTarget