s2/distance_target.go

// Copyright 2019 Google Inc. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package s2

import (
	"github.com/golang/geo/s1"
)

// The distance interface represents a set of common methods used by algorithms
// that compute distances between various S2 types.
type distance interface {
	// chordAngle returns this type as a ChordAngle.
	chordAngle() s1.ChordAngle

	// fromChordAngle is used to type convert a ChordAngle to this type.
	// This is to work around needing to be clever in parts of the code
	// where a distanceTarget interface method expects distances, but the
	// user only supplies a ChordAngle, and we need to dynamically cast it
	// to an appropriate distance interface types.
	fromChordAngle(o s1.ChordAngle) distance

	// zero returns a zero distance.
	zero() distance
	// negative returns a value smaller than any valid value.
	negative() distance
	// infinity returns a value larger than any valid value.
	infinity() distance

	// less is similar to the Less method in Sort. To get minimum values,
	// this would be a less than type operation. For maximum, this would
	// be a greater than type operation.
	less(other distance) bool

	// sub subtracts the other value from this one and returns the new value.
	// This is done as a method and not simple mathematical operation to
	// allow closest and furthest to implement this in opposite ways.
	sub(other distance) distance

	// chordAngleBound reports the upper bound on a ChordAngle corresponding
	// to this distance. For example, if distance measures WGS84 ellipsoid
	// distance then the corresponding angle needs to be 0.56% larger.
	chordAngleBound() s1.ChordAngle

	// updateDistance may update the value this distance represents
	// based on the given input. The updated value and a boolean reporting
	// if the value was changed are returned.
	updateDistance(other distance) (distance, bool)
}

// distanceTarget is an interface that represents a geometric type to which distances
// are measured.
//
// For example, there are implementations that measure distances to a Point,
// an Edge, a Cell, a CellUnion, and even to an arbitrary collection of geometry
// stored in ShapeIndex.
//
// The distanceTarget types are provided for the benefit of types that measure
// distances and/or find nearby geometry, such as ClosestEdgeQuery, FurthestEdgeQuery,
// ClosestPointQuery, and ClosestCellQuery, etc.
type distanceTarget interface {
	// capBound returns a Cap that bounds the set of points whose distance to the
	// target is distance.zero().
	capBound() Cap

	// updateDistanceToPoint updates the distance if the distance to
	// the point P is within than the given dist.
	// The boolean reports if the value was updated.
	updateDistanceToPoint(p Point, dist distance) (distance, bool)

	// updateDistanceToEdge updates the distance if the distance to
	// the edge E is within than the given dist.
	// The boolean reports if the value was updated.
	updateDistanceToEdge(e Edge, dist distance) (distance, bool)

	// updateDistanceToCell updates the distance if the distance to the cell C
	// (including its interior) is within than the given dist.
	// The boolean reports if the value was updated.
	updateDistanceToCell(c Cell, dist distance) (distance, bool)

	// setMaxError potentially updates the value of MaxError, and reports if
	// the specific type supports altering it. Whenever one of the
	// updateDistanceTo... methods above returns true, the returned distance
	// is allowed to be up to maxError larger than the true minimum distance.
	// In other words, it gives this target object permission to terminate its
	// distance calculation as soon as it has determined that (1) the minimum
	// distance is less than minDist and (2) the best possible further
	// improvement is less than maxError.
	//
	// If the target takes advantage of maxError to optimize its distance
	// calculation, this method must return true. (Most target types will
	// default to return false.)
	setMaxError(maxErr s1.ChordAngle) bool

	// maxBruteForceIndexSize reports the maximum number of indexed objects for
	// which it is faster to compute the distance by brute force (e.g., by testing
	// every edge) rather than by using an index.
	//
	// The following method is provided as a convenience for types that compute
	// distances to a collection of indexed geometry, such as ClosestEdgeQuery
	// and ClosestPointQuery.
	//
	// Types that do not support this should return a -1.
	maxBruteForceIndexSize() int

	// distance returns an instance of the underlying distance type this
	// target uses. This is to work around the use of Templates in the C++.
	distance() distance

	// visitContainingShapes finds all polygons in the given index that
	// completely contain a connected component of the target geometry. (For
	// example, if the target consists of 10 points, this method finds
	// polygons that contain any of those 10 points.) For each such polygon,
	// the visit function is called with the Shape of the polygon along with
	// a point of the target geometry that is contained by that polygon.
	//
	// Optionally, any polygon that intersects the target geometry may also be
	// returned.  In other words, this method returns all polygons that
	// contain any connected component of the target, along with an arbitrary
	// subset of the polygons that intersect the target.
	//
	// For example, suppose that the index contains two abutting polygons
	// A and B. If the target consists of two points "a" contained by A and
	// "b" contained by B, then both A and B are returned. But if the target
	// consists of the edge "ab", then any subset of {A, B} could be returned
	// (because both polygons intersect the target but neither one contains
	// the edge "ab").
	//
	// If the visit function returns false, this method terminates early and
	// returns false as well. Otherwise returns true.
	//
	// NOTE(roberts): This method exists only for the purpose of implementing
	// edgeQuery IncludeInteriors efficiently.
	visitContainingShapes(index *ShapeIndex, v shapePointVisitorFunc) bool
}

// shapePointVisitorFunc defines a type of function the visitContainingShapes can call.
type shapePointVisitorFunc func(containingShape Shape, targetPoint Point) bool