Class S2ClosestPointQuery<T>
- java.lang.Object
-
- com.google.common.geometry.S2ClosestPointQuery<T>
-
@GwtCompatible public final class S2ClosestPointQuery<T> extends java.lang.Object
Given a set of points stored in an S2PointIndex, S2ClosestPointQuery provides methods that find the closest point(s) to a given query point.Example usage:
void test(List
points, List targets) { // The template argument allows auxiliary data to be attached to each point (in this case, the // array index). S2PointIndex index = new S2PointIndex<>(); for (int i = 0; i < points.size(); i++) { index.add(points.get(i), i); } S2ClosestPointQuery query = new S2ClosestPointQuery<>(index); query.setMaxPoints(15); for (S2Point target : targets) { for (Result result : query.findClosestPoints(target)) { // result.entry().point() is one of the found closest points. // result.entry().data() is the auxiliary data (the "points" array index). // result.distance() is the distance to the target point. doSomething(target, result.entry().point(), result.entry().data(), result.distance()); } } } You can find either the k closest points, or all points within a given radius, or both (i.e., the k closest points up to a given maximum radius). E.g. to find all the points within 5 kilometers, call
query.setMaxDistance(S1Angle.fromEarthDistance(5000));
.You can also restrict the results to an arbitrary S2Region via
setRegion(S2Region)
.The implementation is designed to be very fast for both small and large point sets.
This class is not thread-safe. In particular, setters must not be called during queries.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
S2ClosestPointQuery.ChordComparable
A type that is comparable on distance only.private static class
S2ClosestPointQuery.EdgeTarget
An edge query, used to find the closest points to a query edge.private static class
S2ClosestPointQuery.PointTarget
A point query, used to find the closest points to a query point.private static class
S2ClosestPointQuery.QueueEntry
A queued cell waiting to be processed by the current query, ordered by distance to any point in the cell in ascending order.static class
S2ClosestPointQuery.Result<T>
A query result paired with the distance to the query target.private static interface
S2ClosestPointQuery.Target
A kind of query target.
-
Field Summary
Fields Modifier and Type Field Description private S2PointIndex<T>
index
The index being queried.private java.util.List<S2CellId>
indexCovering
A small (<6) cell covering of the indexed points.private java.util.List<S2CellId>
intersectionWithMaxDistance
The intersection between the index andmaxDistance
.private java.util.List<S2CellId>
intersectionWithRegion
The intersection between the index andregionCovering
.private S2Iterator<S2PointIndex.Entry<T>>
iter
The iterator for the last-known state of the index.private static int
MAX_BRUTE_FORCE_POINTS
The maximum number of points to process by brute force.private static int
MAX_LEAF_POINTS
The maximum number of points to process without subdividing further.private S1Angle
maxDistance
The max distance to search for points.private java.util.ArrayList<S2CellId>
maxDistanceCovering
The covering ofmaxDistance
.private S1ChordAngle
maxDistanceLimit
Temporary distance to continue searching during a query, generally the distance of the furthest point in the results found so far.private int
maxPoints
The max number of closest points to find.private java.util.PriorityQueue<S2ClosestPointQuery.QueueEntry>
queue
Unprocessed cells for the current query being processed.private S2Region
region
The region to restrict closest point search to.private java.util.ArrayList<S2CellId>
regionCovering
The covering ofindexCovering
.private java.util.PriorityQueue<S2ClosestPointQuery.Result<T>>
results
Temporary queue of results sorted in descending order.private S2PointIndex.Entry<T>[]
tmpPoints
Temporary storage for index entries that are of interest during query processing.private boolean
useBruteForce
Whether to use brute force, which is cheaper when the index has few edges.
-
Constructor Summary
Constructors Constructor Description S2ClosestPointQuery(S2PointIndex<T> index)
Construct a new query for the given index.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private boolean
addCell(S2CellId id, S2Iterator<S2PointIndex.Entry<T>> iter, boolean seek, S2ClosestPointQuery.Target target)
Processes the cell atid
, adding the contents of the cell immediately, or if there are too many points, adding it to the queue to be subdivided.private void
coverRange(S2CellId firstId, S2CellId lastId)
Adds a cell to indexCovering that covers the given inclusive range.S2ClosestPointQuery.Result<T>
findClosestPoint(S2Point target)
Convenience method that returns the closest point to the given target point, or null if no points satisfy thegetMaxDistance()
andgetRegion()
criteria.java.util.List<S2ClosestPointQuery.Result<T>>
findClosestPoints(S2Point target)
Returns the closest points totarget
that satisfy thegetMaxDistance()
,getMaxPoints()
, andgetRegion()
criteria, ordered by increasing distance.void
findClosestPoints(java.util.List<S2ClosestPointQuery.Result<T>> results, S2Point target)
AsfindClosestPoints(S2Point)
, but sorts the results and adds them at the end of the given list.private void
findClosestPointsBruteForce(S2ClosestPointQuery.Target target)
private void
findClosestPointsOptimized(S2ClosestPointQuery.Target target)
java.util.List<S2ClosestPointQuery.Result<T>>
findClosestPointsToEdge(S2Point a, S2Point b)
Returns the closest points to the given edge AB.void
findClosestPointsToEdge(java.util.List<S2ClosestPointQuery.Result<T>> results, S2Point a, S2Point b)
AsfindClosestPointsToEdge(S2Point, S2Point)
, but adds results to the given list.private void
findClosestPointsToTarget(S2ClosestPointQuery.Target target)
S1Angle
getMaxDistance()
Returns the max distance between returned points and the given target.int
getMaxPoints()
Returns the max number of closest points to find.S2Region
getRegion()
Returns the region in which point searches will be done.S2PointIndex<T>
index()
Returns the underlying S2PointIndex.private void
initIndexCovering()
Computes the "index covering", which is a small number of S2CellIds that cover the indexed points.private void
initQueue(S2ClosestPointQuery.Target target)
private void
maybeAddResult(S2PointIndex.Entry<T> entry, S2ClosestPointQuery.Target target)
void
reset()
Resets the query state.void
setMaxDistance(S1Angle maxDistance)
Sets a new max distance to search for points.void
setMaxPoints(int maxPoints)
Sets a new max number of closest points to find.void
setRegion(S2Region region)
private java.util.List<S2ClosestPointQuery.Result<T>>
toList(java.util.List<S2ClosestPointQuery.Result<T>> list)
Creates an empty list if 'list' is null, and then polls all results out ofresults
into the given list in reverse order, and returns it.(package private) void
useBruteForce(boolean useBruteForce)
Sets whether distances are computed using "brute force" (i.e., by examining every point) rather than using the S2PointIndex.
-
-
-
Field Detail
-
MAX_BRUTE_FORCE_POINTS
private static final int MAX_BRUTE_FORCE_POINTS
The maximum number of points to process by brute force.- See Also:
- Constant Field Values
-
MAX_LEAF_POINTS
private static final int MAX_LEAF_POINTS
The maximum number of points to process without subdividing further.- See Also:
- Constant Field Values
-
index
private final S2PointIndex<T> index
The index being queried.
-
maxPoints
private int maxPoints
The max number of closest points to find.
-
maxDistance
private S1Angle maxDistance
The max distance to search for points.
-
region
private S2Region region
The region to restrict closest point search to.
-
useBruteForce
private boolean useBruteForce
Whether to use brute force, which is cheaper when the index has few edges.
-
indexCovering
private java.util.List<S2CellId> indexCovering
A small (<6) cell covering of the indexed points.
-
queue
private final java.util.PriorityQueue<S2ClosestPointQuery.QueueEntry> queue
Unprocessed cells for the current query being processed.
-
iter
private S2Iterator<S2PointIndex.Entry<T>> iter
The iterator for the last-known state of the index. New instance built byreset()
.
-
regionCovering
private java.util.ArrayList<S2CellId> regionCovering
The covering ofindexCovering
. Type is ArrayList due toS2RegionCoverer
.
-
maxDistanceCovering
private final java.util.ArrayList<S2CellId> maxDistanceCovering
The covering ofmaxDistance
. Type is ArrayList due toS2RegionCoverer
.
-
intersectionWithRegion
private final java.util.List<S2CellId> intersectionWithRegion
The intersection between the index andregionCovering
.
-
intersectionWithMaxDistance
private final java.util.List<S2CellId> intersectionWithMaxDistance
The intersection between the index andmaxDistance
.
-
tmpPoints
private final S2PointIndex.Entry<T>[] tmpPoints
Temporary storage for index entries that are of interest during query processing.
-
results
private final java.util.PriorityQueue<S2ClosestPointQuery.Result<T>> results
Temporary queue of results sorted in descending order.
-
maxDistanceLimit
private S1ChordAngle maxDistanceLimit
Temporary distance to continue searching during a query, generally the distance of the furthest point in the results found so far. Beyond this distance, we can safely ignore further candidate points. Candidates that are exactly at the limit are ignored; this makes things easier in the case of S2ClosestEdgeQuery and should not affect clients since distance measurements have a small amount of error anyway.Initially this is the same as the maximum distance specified by the user, but it can also be updated by the algorithm (see maybeAddResult).
-
-
Constructor Detail
-
S2ClosestPointQuery
public S2ClosestPointQuery(S2PointIndex<T> index)
Construct a new query for the given index. Must call reset() before using the query, if the index has been modified since the query was constructed.
-
-
Method Detail
-
reset
public void reset()
Resets the query state. This method must be called after modifying the underlying index.
-
index
public S2PointIndex<T> index()
Returns the underlying S2PointIndex.
-
getMaxPoints
public int getMaxPoints()
Returns the max number of closest points to find.
-
setMaxPoints
public void setMaxPoints(int maxPoints)
Sets a new max number of closest points to find.
-
getMaxDistance
public S1Angle getMaxDistance()
Returns the max distance between returned points and the given target. Default is +inf.
-
setMaxDistance
public void setMaxDistance(S1Angle maxDistance)
Sets a new max distance to search for points.
-
getRegion
public S2Region getRegion()
Returns the region in which point searches will be done.
-
setRegion
public void setRegion(S2Region region)
-
useBruteForce
void useBruteForce(boolean useBruteForce)
Sets whether distances are computed using "brute force" (i.e., by examining every point) rather than using the S2PointIndex.This is package private, as it is intended only for testing, benchmarking, and debugging.
Do not call before init().
-
toList
private java.util.List<S2ClosestPointQuery.Result<T>> toList(java.util.List<S2ClosestPointQuery.Result<T>> list)
Creates an empty list if 'list' is null, and then polls all results out ofresults
into the given list in reverse order, and returns it.
-
findClosestPoints
public java.util.List<S2ClosestPointQuery.Result<T>> findClosestPoints(S2Point target)
Returns the closest points totarget
that satisfy thegetMaxDistance()
,getMaxPoints()
, andgetRegion()
criteria, ordered by increasing distance. If there are no criteria set, then all points are returned.
-
findClosestPoints
public void findClosestPoints(java.util.List<S2ClosestPointQuery.Result<T>> results, S2Point target)
AsfindClosestPoints(S2Point)
, but sorts the results and adds them at the end of the given list.
-
findClosestPoint
public S2ClosestPointQuery.Result<T> findClosestPoint(S2Point target)
Convenience method that returns the closest point to the given target point, or null if no points satisfy thegetMaxDistance()
andgetRegion()
criteria.
-
findClosestPointsToEdge
public java.util.List<S2ClosestPointQuery.Result<T>> findClosestPointsToEdge(S2Point a, S2Point b)
Returns the closest points to the given edge AB. Otherwise similar tofindClosestPoints(S2Point)
.
-
findClosestPointsToEdge
public void findClosestPointsToEdge(java.util.List<S2ClosestPointQuery.Result<T>> results, S2Point a, S2Point b)
AsfindClosestPointsToEdge(S2Point, S2Point)
, but adds results to the given list.
-
initIndexCovering
private void initIndexCovering()
Computes the "index covering", which is a small number of S2CellIds that cover the indexed points.
-
coverRange
private void coverRange(S2CellId firstId, S2CellId lastId)
Adds a cell to indexCovering that covers the given inclusive range. This is done withS2CellId.getCommonAncestorLevel(S2CellId)
, which requires the cells have a common ancestor.
-
findClosestPointsToTarget
private void findClosestPointsToTarget(S2ClosestPointQuery.Target target)
-
findClosestPointsBruteForce
private void findClosestPointsBruteForce(S2ClosestPointQuery.Target target)
-
findClosestPointsOptimized
private void findClosestPointsOptimized(S2ClosestPointQuery.Target target)
-
maybeAddResult
private void maybeAddResult(S2PointIndex.Entry<T> entry, S2ClosestPointQuery.Target target)
-
initQueue
private void initQueue(S2ClosestPointQuery.Target target)
-
addCell
private boolean addCell(S2CellId id, S2Iterator<S2PointIndex.Entry<T>> iter, boolean seek, S2ClosestPointQuery.Target target)
Processes the cell atid
, adding the contents of the cell immediately, or if there are too many points, adding it to the queue to be subdivided. Ifseek
is false, theniter
must already be positioned at the first indexed point within this cell.- Returns:
- true if the cell was added to the queue, and false if it was processed immediately (in
which case
iter
is left positioned at the next cell in S2CellId order.
-
-