max_distance_targets.go

Documentation: github.com/golang/geo/s2

     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  	c := m.index.Region().CapBound()
   215  	return CapFromCenterAngle(Point{c.Center().Mul(-1)}, c.Radius())
   216  }
   217  
   218  func (m *MaxDistanceToShapeIndexTarget) updateDistanceToPoint(p Point, dist distance) (distance, bool) {
   219  	m.query.opts.distanceLimit = dist.chordAngle()
   220  	target := NewMaxDistanceToPointTarget(p)
   221  	r := m.query.findEdge(target, m.query.opts)
   222  	if r.shapeID < 0 {
   223  		return dist, false
   224  	}
   225  	return r.distance, true
   226  }
   227  
   228  func (m *MaxDistanceToShapeIndexTarget) updateDistanceToEdge(edge Edge, dist distance) (distance, bool) {
   229  	m.query.opts.distanceLimit = dist.chordAngle()
   230  	target := NewMaxDistanceToEdgeTarget(edge)
   231  	r := m.query.findEdge(target, m.query.opts)
   232  	if r.shapeID < 0 {
   233  		return dist, false
   234  	}
   235  	return r.distance, true
   236  }
   237  
   238  func (m *MaxDistanceToShapeIndexTarget) updateDistanceToCell(cell Cell, dist distance) (distance, bool) {
   239  	m.query.opts.distanceLimit = dist.chordAngle()
   240  	target := NewMaxDistanceToCellTarget(cell)
   241  	r := m.query.findEdge(target, m.query.opts)
   242  	if r.shapeID < 0 {
   243  		return dist, false
   244  	}
   245  	return r.distance, true
   246  }
   247  
   248  // visitContainingShapes returns the polygons containing the antipodal
   249  // reflection of *any* connected component for target types consisting of
   250  // multiple connected components. It is sufficient to test containment of
   251  // one vertex per connected component, since this allows us to also return
   252  // any polygon whose boundary has distance.zero() to the target.
   253  func (m *MaxDistanceToShapeIndexTarget) visitContainingShapes(index *ShapeIndex, v shapePointVisitorFunc) bool {
   254  	// It is sufficient to find the set of chain starts in the target index
   255  	// (i.e., one vertex per connected component of edges) that are contained by
   256  	// the query index, except for one special case to handle full polygons.
   257  	//
   258  	// TODO(roberts): Do this by merge-joining the two ShapeIndexes and share
   259  	// the code with BooleanOperation.
   260  	for _, shape := range m.index.shapes {
   261  		numChains := shape.NumChains()
   262  		// Shapes that don't have any edges require a special case (below).
   263  		testedPoint := false
   264  		for c := 0; c < numChains; c++ {
   265  			chain := shape.Chain(c)
   266  			if chain.Length == 0 {
   267  				continue
   268  			}
   269  			testedPoint = true
   270  			target := NewMaxDistanceToPointTarget(shape.ChainEdge(c, 0).V0)
   271  			if !target.visitContainingShapes(index, v) {
   272  				return false
   273  			}
   274  		}
   275  		if !testedPoint {
   276  			// Special case to handle full polygons.
   277  			ref := shape.ReferencePoint()
   278  			if !ref.Contained {
   279  				continue
   280  			}
   281  			target := NewMaxDistanceToPointTarget(ref.Point)
   282  			if !target.visitContainingShapes(index, v) {
   283  				return false
   284  			}
   285  		}
   286  	}
   287  	return true
   288  }
   289  
   290  func (m *MaxDistanceToShapeIndexTarget) setMaxError(maxErr s1.ChordAngle) bool {
   291  	m.query.opts.maxError = maxErr
   292  	return true
   293  }
   294  func (m *MaxDistanceToShapeIndexTarget) maxBruteForceIndexSize() int { return 30 }
   295  func (m *MaxDistanceToShapeIndexTarget) distance() distance          { return m.dist }
   296  func (m *MaxDistanceToShapeIndexTarget) setIncludeInteriors(b bool) {
   297  	m.query.opts.includeInteriors = b
   298  }
   299  func (m *MaxDistanceToShapeIndexTarget) setUseBruteForce(b bool) { m.query.opts.useBruteForce = b }
   300  
   301  // TODO(roberts): Remaining methods
   302  //
   303  // CellUnionTarget
   304
View as plain text