Class 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.

    • 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.
      • intersectionWithRegion

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

        private final java.util.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 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().

      • initIndexCovering

        private void initIndexCovering()
        Computes the "index covering", which is a small number of S2CellIds that cover the indexed points.
      • 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.