Class S2ClosestPointQuery<T>

java.lang.Object
com.google.common.geometry.S2ClosestPointQuery<T>

@GwtCompatible public final class S2ClosestPointQuery<T> extends 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 S2PointIndexinvalid input: '<'>();
   for (int i = 0; i invalid input: '<' points.size(); i++) {
     index.add(points.get(i), i);
   }
   S2ClosestPointQuery query = new S2ClosestPointQueryinvalid input: '<'>(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.

  • Field Details

    • MAX_BRUTE_FORCE_POINTS

      private static final int MAX_BRUTE_FORCE_POINTS
      The maximum number of points to process by brute force.
      See Also:
    • MAX_LEAF_POINTS

      private static final int MAX_LEAF_POINTS
      The maximum number of points to process without subdividing further.
      See Also:
    • 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 List<S2CellId> indexCovering
      A small (invalid input: '<'6) cell covering of the indexed points.
    • queue

      Unprocessed cells for the current query being processed.
    • iter

      The iterator for the last-known state of the index. New instance built by reset().
    • regionCovering

      private ArrayList<S2CellId> regionCovering
      The covering of indexCovering. Type is ArrayList due to S2RegionCoverer.
    • maxDistanceCovering

      private final ArrayList<S2CellId> maxDistanceCovering
      The covering of maxDistance. Type is ArrayList due to S2RegionCoverer.
    • intersectionWithRegion

      private final List<S2CellId> intersectionWithRegion
      The intersection between the index and regionCovering.
    • intersectionWithMaxDistance

      private final List<S2CellId> intersectionWithMaxDistance
      The intersection between the index and maxDistance.
    • tmpPoints

      private final S2PointIndex.Entry<T>[] tmpPoints
      Temporary storage for index entries that are of interest during query processing.
    • results

      private final 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 Details

    • 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 Details

    • 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

      Creates an empty list if 'list' is null, and then polls all results out of results into the given list in reverse order, and returns it.
    • findClosestPoints

      public List<S2ClosestPointQuery.Result<T>> findClosestPoints(S2Point target)
      Returns the closest points to target that satisfy the getMaxDistance(), getMaxPoints(), and getRegion() criteria, ordered by increasing distance. If there are no criteria set, then all points are returned.
    • findClosestPoints

      public void findClosestPoints(List<S2ClosestPointQuery.Result<T>> results, S2Point target)
      As findClosestPoints(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 the getMaxDistance() and getRegion() criteria.
    • findClosestPointsToEdge

      public List<S2ClosestPointQuery.Result<T>> findClosestPointsToEdge(S2Point a, S2Point b)
      Returns the closest points to the given edge AB. Otherwise similar to findClosestPoints(S2Point).
    • findClosestPointsToEdge

      public void findClosestPointsToEdge(List<S2ClosestPointQuery.Result<T>> results, S2Point a, S2Point b)
      As findClosestPointsToEdge(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 with S2CellId.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 at id, adding the contents of the cell immediately, or if there are too many points, adding it to the queue to be subdivided. If seek is false, then iter 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.