Interpolation along Chains

The purpose of this document is to provide a description of S2ChainInterpolationQuery and to illustrate its usage with code snippets.

Overview

S2ChainInterpolationQuery is a tool for interpolating point locations along chains. For example, it can compute the position that is 50% along a polyline, or generate all the positions on a polygon boundary that are 1e-4 radians apart. The interpolation is based on spherical distance that is computed cumulatively along the edges of the chain. It works with geometry classes that are derived from S2Shape and represent polylines, polygons, or sets thereof.

An S2Shape is organized as a collection of edges, which are identified by a contiguous range of integer edge ids, starting at 0. The edges are grouped into chains, where each chain consists of a sequence of edges connected end-to-end and thus forming a polyline, or a closed polygon. For example, a shape representing a single open polyline with N vertices would consist of just one chain containing N - 1 edges. A shape representing an island with a lake in it would consist of two chains, one chain for the outer contour of the island and the other for the contour of the lake.

If the input shape contains multiple chains, the caller can specify the index of the chain to be used, or let the query use all chains contained in the shape. When multiple chains are used, they are assumed to be arranged end to end in the distance space, in the same order as they are stored in the S2Shape, see Working with Multiple Chains section for more details.

S2ChainInterpolationQuery can be used for:

• Finding the point that is located at a given distance from the first vertex along the chain
• Finding the point that is located at a given normalized distance, that is a fraction of the polyline’s total length.
• Obtaining the edge ids of the resulting points

Initializing an S2ChainInterpolationQuery

An instance of S2ChainInterpolationQuery can be initialized as follows:

const S2Shape* shape = ...;
int chain_id = ...;

S2ChainInterpolationQuery query(shape, chain_id);

where chain_id is the non-negative id of the shape’s chain on which the points are going to be queried (0 <= chain_id < shape->num_chains()).

If chain_id is negative (or altogether omitted) then all shape’s chains are going to be used in the order of their respective ids, as if there were a single polyline. Note that in this case the resulting point may not be a continuous function of distance, since the beginning of a chain may not coincide with the end of the previous chain.

When the input shape is known to contain only one chain, the chain_id parameter can be either set to 0 or omitted.

Using the Query Methods

Once an instance of S2ChainInterpolationQuery is initialized, the total length of a chain (or chains) can be accessed via its GetLength() method:

S1Angle total_length = query.GetLength();

Note that if the query is uninitialized, or initialized with an empty shape (i.e. a shape that contains no chains), the returned total length is zero (S1Angle::Zero().

To find the point at a given spherical distance d along the chain(s), use the AtDistance() method. This method also computes the id of the edge on which the resulting point is located, as well as the actual parametric distance of the point. The resulting point, edge id and distance can be obtained via the respective accessor methods of S2ChainInterpolationQuery::Result:

S1Angle d = ...;
S2ChainInterpolationQuery::Result result = query.AtDistance(d);

if (result.is_valid()) {}
  S2Point point_at_distance = result.point();
  int edge_id = result.edge_id();
  S1Angle actual_distance = result.distance();
}

If the input distance d is less than or equal to the chain’s total length, then the actual distance returned by result.distance() equals d. If, however, d is greater than the chain’s total length, then the resulting point is snapped to the last vertex of the chain(s) and result.distance() returns the total length of the chain.

For example, consider the polyline abc formed by three vertices A, B and C with the respective latitudes/longitudes of (0, 0), (0, 1) and (0, 2). It has two edges, AB and BC, each of them having the spherical length of 1 degree. For this polyline we have:

// Vertices A, B and C
auto vertices = s2textformat::ParsePointsOrDie("0:0, 0:1, 0:2"); 

S2LaxPolylineShape shape(vertices);

// The above shape is known to contain just one chain (A,B,C), therefore one can
// omit the chain_id parameter in the query initialization.
S2ChainInterpolationQuery query(&shape);

// The total length is 2 degrees = sum of lengths of edges (A,B) and (B,C).
S1Angle total_length = query.GetLength();

// Find the point at the spherical distance of 1.5 degrees.
S2ChainInterpolationQuery::Result result = query.AtDistance(S1Angle::Degrees(1.5)));
S2Point point = result.point();
S1Angle distance = result.distance();
int edge_id = result.edge_id();

The resulting point is located half-way between vertices B and C, the resulting distance is the same as the input distance of 1.5 degrees and the edge id is 1, corresponding to the second edge of the chain. Alternatively, calling query.AtDistance(2.5) yields the resulting point coinciding with C, a resulting distance equal to the chain’s total length (2 degrees), and an edge id of 1, since the results of queries with distances exceeding the chain’s length are snapped to the last vertex of the chain.

To find the point at a given normalized distance (i.e. at a fraction of the total length) f, where 0 <= f <= 1, use the AtFraction() method:

double f = ...;  

auto result = query.AtFraction(f);
S2Point point_at_distance = result.point();
int edge_id = result.edge_id();
S1Angle actual_distance = result.distance();

The actual distance returned by AtFraction() is always within the interval of [0, total_length]. If passed an input fraction value greater than 1, then the resulting point is snapped to the last vertex of the chain(s) and the distance returned by AtFraction() equals the total length of the chain.

Calling query.AtFraction(0.75) for the polyline shape in the above example would yield the resulting point half-way between B and C, resulting distance of 1.5 and the edge id = 1 (the last edge of the chain). And query.AtFraction(1.5) gives the resulting point coinciding with the last vertex C, resulting length = 2 (the total length) and the resulting edge id = 1 (the edge corresponding to the last vertex).

Both AtDistance() and AtFraction() return valid results for all input distance values if and only if the query has been initialized with a shape containing at least one valid edge.

Let us now consider an S2LaxPolygonShape containing two chains, each being 1 degree long and containing two edges.

If the query for this shape is initialized with a chain_id of 0:

S2ChainInterpolationQuery query(&shape, 0);

then only the first chain (chain_id = 0) is considered and the other chain is ignored. In this case query.GetLength() returns the value corresponding to the angle of 1 degree, which is the length of the single chain.

Now, if the query is initialized with a chain_id that is negative (or omitted), both chains are considered as if they were part of the same polyline, and query.GetLength() returns an angle of 2 degrees, which is the length of both chains combined:

S2ChainInterpolationQuery query(&shape);
S1Angle total_length = query.GetLength();  // total_length.degrees() == 2

In this case calling query.AtDistance(1.5) or query.AtFraction(0.75) would yield a point halfway down the second chain, and the resulting an edge id = 1 (the second edge of the shape corresponding to the first and the only edge of the second chain).

Working with Multiple Chains

An important caveat when considering multiple chain is that the resulting point is not a continuous function of the input distance, since the last vertex of a chain may not coincide with the first vertex of the next chain. In the above case, calling query.AtFraction( 0.5 ) yields the resulting point = last vertex of the first chain, while query.AtFraction( 0.5 + epsilon ) yields the first vertex of the second chain, which may be located far apart from the last vertex of the previous chain.

A typical use case for using queries with multiple chains is when one needs to generate an approximately uniform sampling of all chains contained in a shape. In these cases one can just call query.AtFraction(t) with t ranging from 0.0 to 1.0 with a certain step, depending on the desired sampling density. Note that such sampling is only approximately uniform, since the chain lengths won’t necessarily be multiples of the step size.

Computational Complexity

• S2ChainInterpolationQuery initialization has the computational complexity of O(N), where N is the total number of edges.
• AtDistance() and AtFraction() calls have the complexity of O( log(N) ).
• GetLength() call has the constant complexity O(1).
• The memory footprint of the query is O(N).

Numerical Accuracy

The S2Point returned by result.point() accessor is an approximation of the true position with the error bound by kGetPointOnLineError.

The computation error of the total length is bound by 3.25 * DBL_EPSILON * N, where N is the number of edges. An additional loss of precision may occur due to floating point multiplication of fraction * total_length during AtFraction() call.