max_distance_targets.go (12015B)
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 // maxDistance implements distance as the supplementary distance (Pi - x) to find 24 // results that are the furthest using the distance related algorithms. 25 type maxDistance s1.ChordAngle 26 27 func (m maxDistance) chordAngle() s1.ChordAngle { return s1.ChordAngle(m) } 28 func (m maxDistance) zero() distance { return maxDistance(s1.StraightChordAngle) } 29 func (m maxDistance) negative() distance { return maxDistance(s1.InfChordAngle()) } 30 func (m maxDistance) infinity() distance { return maxDistance(s1.NegativeChordAngle) } 31 func (m maxDistance) less(other distance) bool { return m.chordAngle() > other.chordAngle() } 32 func (m maxDistance) sub(other distance) distance { 33 return maxDistance(m.chordAngle() + other.chordAngle()) 34 } 35 func (m maxDistance) chordAngleBound() s1.ChordAngle { 36 return s1.StraightChordAngle - m.chordAngle() 37 } 38 func (m maxDistance) updateDistance(dist distance) (distance, bool) { 39 if dist.less(m) { 40 m = maxDistance(dist.chordAngle()) 41 return m, true 42 } 43 return m, false 44 } 45 46 func (m maxDistance) fromChordAngle(o s1.ChordAngle) distance { 47 return maxDistance(o) 48 } 49 50 // MaxDistanceToPointTarget is used for computing the maximum distance to a Point. 51 type MaxDistanceToPointTarget struct { 52 point Point 53 dist distance 54 } 55 56 // NewMaxDistanceToPointTarget returns a new target for the given Point. 57 func NewMaxDistanceToPointTarget(point Point) *MaxDistanceToPointTarget { 58 m := maxDistance(0) 59 return &MaxDistanceToPointTarget{point: point, dist: &m} 60 } 61 62 func (m *MaxDistanceToPointTarget) capBound() Cap { 63 return CapFromCenterChordAngle(Point{m.point.Mul(-1)}, (s1.ChordAngle(0))) 64 } 65 66 func (m *MaxDistanceToPointTarget) updateDistanceToPoint(p Point, dist distance) (distance, bool) { 67 return dist.updateDistance(maxDistance(ChordAngleBetweenPoints(p, m.point))) 68 } 69 70 func (m *MaxDistanceToPointTarget) updateDistanceToEdge(edge Edge, dist distance) (distance, bool) { 71 if d, ok := UpdateMaxDistance(m.point, edge.V0, edge.V1, dist.chordAngle()); ok { 72 dist, _ = dist.updateDistance(maxDistance(d)) 73 return dist, true 74 } 75 return dist, false 76 } 77 78 func (m *MaxDistanceToPointTarget) updateDistanceToCell(cell Cell, dist distance) (distance, bool) { 79 return dist.updateDistance(maxDistance(cell.MaxDistance(m.point))) 80 } 81 82 func (m *MaxDistanceToPointTarget) visitContainingShapes(index *ShapeIndex, v shapePointVisitorFunc) bool { 83 // For furthest points, we visit the polygons whose interior contains 84 // the antipode of the target point. These are the polygons whose 85 // distance to the target is maxDistance.zero() 86 q := NewContainsPointQuery(index, VertexModelSemiOpen) 87 return q.visitContainingShapes(Point{m.point.Mul(-1)}, func(shape Shape) bool { 88 return v(shape, m.point) 89 }) 90 } 91 92 func (m *MaxDistanceToPointTarget) setMaxError(maxErr s1.ChordAngle) bool { return false } 93 func (m *MaxDistanceToPointTarget) maxBruteForceIndexSize() int { return 30 } 94 func (m *MaxDistanceToPointTarget) distance() distance { return m.dist } 95 96 // MaxDistanceToEdgeTarget is used for computing the maximum distance to an Edge. 97 type MaxDistanceToEdgeTarget struct { 98 e Edge 99 dist distance 100 } 101 102 // NewMaxDistanceToEdgeTarget returns a new target for the given Edge. 103 func NewMaxDistanceToEdgeTarget(e Edge) *MaxDistanceToEdgeTarget { 104 m := maxDistance(0) 105 return &MaxDistanceToEdgeTarget{e: e, dist: m} 106 } 107 108 // capBound returns a Cap that bounds the antipode of the target. (This 109 // is the set of points whose maxDistance to the target is maxDistance.zero) 110 func (m *MaxDistanceToEdgeTarget) capBound() Cap { 111 // The following computes a radius equal to half the edge length in an 112 // efficient and numerically stable way. 113 d2 := float64(ChordAngleBetweenPoints(m.e.V0, m.e.V1)) 114 r2 := (0.5 * d2) / (1 + math.Sqrt(1-0.25*d2)) 115 return CapFromCenterChordAngle(Point{m.e.V0.Add(m.e.V1.Vector).Mul(-1).Normalize()}, s1.ChordAngleFromSquaredLength(r2)) 116 } 117 118 func (m *MaxDistanceToEdgeTarget) updateDistanceToPoint(p Point, dist distance) (distance, bool) { 119 if d, ok := UpdateMaxDistance(p, m.e.V0, m.e.V1, dist.chordAngle()); ok { 120 dist, _ = dist.updateDistance(maxDistance(d)) 121 return dist, true 122 } 123 return dist, false 124 } 125 126 func (m *MaxDistanceToEdgeTarget) updateDistanceToEdge(edge Edge, dist distance) (distance, bool) { 127 if d, ok := updateEdgePairMaxDistance(m.e.V0, m.e.V1, edge.V0, edge.V1, dist.chordAngle()); ok { 128 dist, _ = dist.updateDistance(maxDistance(d)) 129 return dist, true 130 } 131 return dist, false 132 } 133 134 func (m *MaxDistanceToEdgeTarget) updateDistanceToCell(cell Cell, dist distance) (distance, bool) { 135 return dist.updateDistance(maxDistance(cell.MaxDistanceToEdge(m.e.V0, m.e.V1))) 136 } 137 138 func (m *MaxDistanceToEdgeTarget) visitContainingShapes(index *ShapeIndex, v shapePointVisitorFunc) bool { 139 // We only need to test one edge point. That is because the method *must* 140 // visit a polygon if it fully contains the target, and *is allowed* to 141 // visit a polygon if it intersects the target. If the tested vertex is not 142 // contained, we know the full edge is not contained; if the tested vertex is 143 // contained, then the edge either is fully contained (must be visited) or it 144 // intersects (is allowed to be visited). We visit the center of the edge so 145 // that edge AB gives identical results to BA. 146 target := NewMaxDistanceToPointTarget(Point{m.e.V0.Add(m.e.V1.Vector).Normalize()}) 147 return target.visitContainingShapes(index, v) 148 } 149 150 func (m *MaxDistanceToEdgeTarget) setMaxError(maxErr s1.ChordAngle) bool { return false } 151 func (m *MaxDistanceToEdgeTarget) maxBruteForceIndexSize() int { return 30 } 152 func (m *MaxDistanceToEdgeTarget) distance() distance { return m.dist } 153 154 // MaxDistanceToCellTarget is used for computing the maximum distance to a Cell. 155 type MaxDistanceToCellTarget struct { 156 cell Cell 157 dist distance 158 } 159 160 // NewMaxDistanceToCellTarget returns a new target for the given Cell. 161 func NewMaxDistanceToCellTarget(cell Cell) *MaxDistanceToCellTarget { 162 m := maxDistance(0) 163 return &MaxDistanceToCellTarget{cell: cell, dist: m} 164 } 165 166 func (m *MaxDistanceToCellTarget) capBound() Cap { 167 c := m.cell.CapBound() 168 return CapFromCenterAngle(Point{c.Center().Mul(-1)}, c.Radius()) 169 } 170 171 func (m *MaxDistanceToCellTarget) updateDistanceToPoint(p Point, dist distance) (distance, bool) { 172 return dist.updateDistance(maxDistance(m.cell.MaxDistance(p))) 173 } 174 175 func (m *MaxDistanceToCellTarget) updateDistanceToEdge(edge Edge, dist distance) (distance, bool) { 176 return dist.updateDistance(maxDistance(m.cell.MaxDistanceToEdge(edge.V0, edge.V1))) 177 } 178 179 func (m *MaxDistanceToCellTarget) updateDistanceToCell(cell Cell, dist distance) (distance, bool) { 180 return dist.updateDistance(maxDistance(m.cell.MaxDistanceToCell(cell))) 181 } 182 183 func (m *MaxDistanceToCellTarget) visitContainingShapes(index *ShapeIndex, v shapePointVisitorFunc) bool { 184 // We only need to check one point here - cell center is simplest. 185 // See comment at MaxDistanceToEdgeTarget's visitContainingShapes. 186 target := NewMaxDistanceToPointTarget(m.cell.Center()) 187 return target.visitContainingShapes(index, v) 188 } 189 190 func (m *MaxDistanceToCellTarget) setMaxError(maxErr s1.ChordAngle) bool { return false } 191 func (m *MaxDistanceToCellTarget) maxBruteForceIndexSize() int { return 30 } 192 func (m *MaxDistanceToCellTarget) distance() distance { return m.dist } 193 194 // MaxDistanceToShapeIndexTarget is used for computing the maximum distance to a ShapeIndex. 195 type MaxDistanceToShapeIndexTarget struct { 196 index *ShapeIndex 197 query *EdgeQuery 198 dist distance 199 } 200 201 // NewMaxDistanceToShapeIndexTarget returns a new target for the given ShapeIndex. 202 func NewMaxDistanceToShapeIndexTarget(index *ShapeIndex) *MaxDistanceToShapeIndexTarget { 203 m := maxDistance(0) 204 return &MaxDistanceToShapeIndexTarget{ 205 index: index, 206 dist: m, 207 query: NewFurthestEdgeQuery(index, NewFurthestEdgeQueryOptions()), 208 } 209 } 210 211 // capBound returns a Cap that bounds the antipode of the target. This 212 // is the set of points whose maxDistance to the target is maxDistance.zero() 213 func (m *MaxDistanceToShapeIndexTarget) capBound() Cap { 214 // TODO(roberts): Depends on ShapeIndexRegion 215 // c := makeShapeIndexRegion(m.index).CapBound() 216 // return CapFromCenterRadius(Point{c.Center.Mul(-1)}, c.Radius()) 217 panic("not implemented yet") 218 } 219 220 func (m *MaxDistanceToShapeIndexTarget) updateDistanceToPoint(p Point, dist distance) (distance, bool) { 221 m.query.opts.distanceLimit = dist.chordAngle() 222 target := NewMaxDistanceToPointTarget(p) 223 r := m.query.findEdge(target, m.query.opts) 224 if r.shapeID < 0 { 225 return dist, false 226 } 227 return r.distance, true 228 } 229 230 func (m *MaxDistanceToShapeIndexTarget) updateDistanceToEdge(edge Edge, dist distance) (distance, bool) { 231 m.query.opts.distanceLimit = dist.chordAngle() 232 target := NewMaxDistanceToEdgeTarget(edge) 233 r := m.query.findEdge(target, m.query.opts) 234 if r.shapeID < 0 { 235 return dist, false 236 } 237 return r.distance, true 238 } 239 240 func (m *MaxDistanceToShapeIndexTarget) updateDistanceToCell(cell Cell, dist distance) (distance, bool) { 241 m.query.opts.distanceLimit = dist.chordAngle() 242 target := NewMaxDistanceToCellTarget(cell) 243 r := m.query.findEdge(target, m.query.opts) 244 if r.shapeID < 0 { 245 return dist, false 246 } 247 return r.distance, true 248 } 249 250 // visitContainingShapes returns the polygons containing the antipodal 251 // reflection of *any* connected component for target types consisting of 252 // multiple connected components. It is sufficient to test containment of 253 // one vertex per connected component, since this allows us to also return 254 // any polygon whose boundary has distance.zero() to the target. 255 func (m *MaxDistanceToShapeIndexTarget) visitContainingShapes(index *ShapeIndex, v shapePointVisitorFunc) bool { 256 // It is sufficient to find the set of chain starts in the target index 257 // (i.e., one vertex per connected component of edges) that are contained by 258 // the query index, except for one special case to handle full polygons. 259 // 260 // TODO(roberts): Do this by merge-joining the two ShapeIndexes and share 261 // the code with BooleanOperation. 262 for _, shape := range m.index.shapes { 263 numChains := shape.NumChains() 264 // Shapes that don't have any edges require a special case (below). 265 testedPoint := false 266 for c := 0; c < numChains; c++ { 267 chain := shape.Chain(c) 268 if chain.Length == 0 { 269 continue 270 } 271 testedPoint = true 272 target := NewMaxDistanceToPointTarget(shape.ChainEdge(c, 0).V0) 273 if !target.visitContainingShapes(index, v) { 274 return false 275 } 276 } 277 if !testedPoint { 278 // Special case to handle full polygons. 279 ref := shape.ReferencePoint() 280 if !ref.Contained { 281 continue 282 } 283 target := NewMaxDistanceToPointTarget(ref.Point) 284 if !target.visitContainingShapes(index, v) { 285 return false 286 } 287 } 288 } 289 return true 290 } 291 292 func (m *MaxDistanceToShapeIndexTarget) setMaxError(maxErr s1.ChordAngle) bool { 293 m.query.opts.maxError = maxErr 294 return true 295 } 296 func (m *MaxDistanceToShapeIndexTarget) maxBruteForceIndexSize() int { return 30 } 297 func (m *MaxDistanceToShapeIndexTarget) distance() distance { return m.dist } 298 func (m *MaxDistanceToShapeIndexTarget) setIncludeInteriors(b bool) { 299 m.query.opts.includeInteriors = b 300 } 301 func (m *MaxDistanceToShapeIndexTarget) setUseBruteForce(b bool) { m.query.opts.useBruteForce = b } 302 303 // TODO(roberts): Remaining methods 304 // 305 // func (m *MaxDistanceToShapeIndexTarget) capBound() Cap { 306 // CellUnionTarget