S2ClosestEdgeQuery

S2ClosestEdgeQuery is a helper class for finding the closest edge(s) to a given point, edge, S2Cell, or geometry collection. For example, given a set of polylines, the following code efficiently finds the closest 5 edges to a query point:

void Test(const vector<S2Polyline*>& polylines, const S2Point& point) { MutableS2ShapeIndex index; for (S2Polyline* polyline : polylines) { index.Add(new S2Polyline::Shape(polyline)); } S2ClosestEdgeQuery query(&index); query.mutable_options()->set_max_edges(5); S2ClosestEdgeQuery::PointTarget target(point); for (const auto& result : query.FindClosestEdges(&target)) { // The Result struct contains the following fields: // "distance" is the distance to the edge. // "shape_id" identifies the S2Shape containing the edge. // "edge_id" identifies the edge with the given shape. // The following convenience methods may also be useful: // query.GetEdge(result) returns the endpoints of the edge. // query.Project(point, result) computes the closest point on the // result edge to the given target point. int polyline_index = result.shape_id; int edge_index = result.edge_id; S1ChordAngle distance = result.distance; // Use ToAngle() for S1Angle. S2Shape::Edge edge = query.GetEdge(result); S2Point closest_point = query.Project(point, result); } }

You can find either the k closest edges, or all edges within a given radius, or both (i.e., the k closest edges up to a given maximum radius). E.g. to find all the edges within 5 kilometers, call

query.mutable_options()->set_max_distance( S2Earth::ToAngle(util::units::Kilometers(5)));

By default *all* edges are returned, so you should always specify either max_edges() or max_distance() or both. There is also a FindClosestEdge() convenience method that returns only the closest edge.

Note that by default, distances are measured to the boundary and interior of polygons. For example, if a point is inside a polygon then its distance is zero. To change this behavior, call set_include_interiors(false).

If you only need to test whether the distance is above or below a given threshold (e.g., 10 km), you can use the IsDistanceLess() method. This is much faster than actually calculating the distance with FindClosestEdge(), since the implementation can stop as soon as it can prove that the minimum distance is either above or below the threshold.

To find the closest edges to a query edge rather than a point, use:

S2ClosestEdgeQuery::EdgeTarget target(v0, v1); query.FindClosestEdges(&target);

Similarly you can find the closest edges to an S2Cell by using an S2ClosestEdgeQuery::CellTarget, and you can find the closest edges to an arbitrary collection of points, polylines, and polygons by using an S2ClosestEdgeQuery::ShapeIndexTarget.

The implementation is designed to be fast for both simple and complex geometric objects.