min_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  // 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  	c := m.index.Region().CapBound()
   272  	return CapFromCenterAngle(Point{c.Center().Mul(-1)}, c.Radius())
   273  }
   274  
   275  func (m *MinDistanceToShapeIndexTarget) updateDistanceToPoint(p Point, dist distance) (distance, bool) {
   276  	m.query.opts.distanceLimit = dist.chordAngle()
   277  	target := NewMinDistanceToPointTarget(p)
   278  	r := m.query.findEdge(target, m.query.opts)
   279  	if r.shapeID < 0 {
   280  		return dist, false
   281  	}
   282  	return r.distance, true
   283  }
   284  
   285  func (m *MinDistanceToShapeIndexTarget) updateDistanceToEdge(edge Edge, dist distance) (distance, bool) {
   286  	m.query.opts.distanceLimit = dist.chordAngle()
   287  	target := NewMinDistanceToEdgeTarget(edge)
   288  	r := m.query.findEdge(target, m.query.opts)
   289  	if r.shapeID < 0 {
   290  		return dist, false
   291  	}
   292  	return r.distance, true
   293  }
   294  
   295  func (m *MinDistanceToShapeIndexTarget) updateDistanceToCell(cell Cell, dist distance) (distance, bool) {
   296  	m.query.opts.distanceLimit = dist.chordAngle()
   297  	target := NewMinDistanceToCellTarget(cell)
   298  	r := m.query.findEdge(target, m.query.opts)
   299  	if r.shapeID < 0 {
   300  		return dist, false
   301  	}
   302  	return r.distance, true
   303  }
   304  
   305  // For target types consisting of multiple connected components (such as this one),
   306  // this method should return the polygons containing the antipodal reflection of
   307  // *any* connected component. (It is sufficient to test containment of one vertex per
   308  // connected component, since this allows us to also return any polygon whose
   309  // boundary has distance.zero() to the target.)
   310  func (m *MinDistanceToShapeIndexTarget) visitContainingShapes(index *ShapeIndex, v shapePointVisitorFunc) bool {
   311  	// It is sufficient to find the set of chain starts in the target index
   312  	// (i.e., one vertex per connected component of edges) that are contained by
   313  	// the query index, except for one special case to handle full polygons.
   314  	//
   315  	// TODO(roberts): Do this by merge-joining the two ShapeIndexes.
   316  	for _, shape := range m.index.shapes {
   317  		numChains := shape.NumChains()
   318  		// Shapes that don't have any edges require a special case (below).
   319  		testedPoint := false
   320  		for c := 0; c < numChains; c++ {
   321  			chain := shape.Chain(c)
   322  			if chain.Length == 0 {
   323  				continue
   324  			}
   325  			testedPoint = true
   326  			target := NewMinDistanceToPointTarget(shape.ChainEdge(c, 0).V0)
   327  			if !target.visitContainingShapes(index, v) {
   328  				return false
   329  			}
   330  		}
   331  		if !testedPoint {
   332  			// Special case to handle full polygons.
   333  			ref := shape.ReferencePoint()
   334  			if !ref.Contained {
   335  				continue
   336  			}
   337  			target := NewMinDistanceToPointTarget(ref.Point)
   338  			if !target.visitContainingShapes(index, v) {
   339  				return false
   340  			}
   341  		}
   342  	}
   343  	return true
   344  }
   345  
   346  func (m *MinDistanceToShapeIndexTarget) setMaxError(maxErr s1.ChordAngle) bool {
   347  	m.query.opts.maxError = maxErr
   348  	return true
   349  }
   350  func (m *MinDistanceToShapeIndexTarget) maxBruteForceIndexSize() int { return 25 }
   351  func (m *MinDistanceToShapeIndexTarget) distance() distance          { return m.dist }
   352  func (m *MinDistanceToShapeIndexTarget) setIncludeInteriors(b bool) {
   353  	m.query.opts.includeInteriors = b
   354  }
   355  func (m *MinDistanceToShapeIndexTarget) setUseBruteForce(b bool) { m.query.opts.useBruteForce = b }
   356  
   357  // TODO(roberts): Remaining methods
   358  //
   359  // CellUnionTarget
   360
View as plain text