S2PointIndex

S2PointIndex maintains an index of points sorted by leaf S2CellId. Each point has some associated client-supplied data, such as an integer or pointer. This can be used to map results back to client data structures.

The class supports adding or removing points dynamically, and provides a seekable iterator interface for navigating the index.

You can use this class in conjuction with S2ClosestPointQuery to find the closest index points to a given query point. For example:

void Test(const vector<S2Point>& points, const S2Point& target) { // The template argument allows auxiliary data to be attached to each // point (in this case, the array index). S2PointIndex<int> index; for (int i = 0; i < points.size(); ++i) { index.Add(pointsi, i); } S2ClosestPointQuery<int> query(&index); query.FindClosestPoint(target); if (query.num_points() > 0) { // query.point(0) is the closest point (result 0). // query.distance(0) is the distance to the target. // query.data(0) is the auxiliary data (the array index set above). DoSomething(query.point(0), query.data(0), query.distance(0)); } }

Alternatively, you can access the index directly using the iterator interface. For example, here is how to iterate through all the points in a given S2CellId "target_id":

S2PointIndex<int>::Iterator it(&index); it.Seek(target_id.range_min()); for (; !it.done() && it.id() <= target_id.range_max(); it.Next()) { DoSomething(it.id(), it.point(), it.data()); }

Points can be added or removed from the index at any time by calling Add() or Remove(). However when the index is modified, you must call Init() on each iterator before using it again (or simply create a new iterator).

index.Add(new_point, 123456); it.Init(&index); it.Seek(target.range_min());

TODO(ericv): Make this a subtype of S2Region, so that it can also be used to efficiently compute coverings of a collection of S2Points.

REQUIRES: "Data" has default and copy constructors. REQUIRES: "Data" has operator== and operator<.