LocateBetween and LocateAlong: all stretches and all points for M
SubstringByM and InterpolateByM (ADR 0017) follow the first hit of an M value. Real M is not monotonic: a road loops, M resets, a route returns along itself. The questions a web GIS asks are then different: "which stretches of this route lie between kilometre 12 and 15?" and "where is kilometre 12.5, everywhere it occurs?". LocateBetween answers the first with every stretch whose M lies in an interval, LocateAlong the second with every point where M has a value. They are the OGC operations ST_LocateBetween and ST_LocateAlong for lines.
German version: 0032-locatebetween-und-locatealong.de.md
Consequences
Placement:
LocateBetweenandLocateAlonginLinearReferencing(ADR 0017), inSpatialNET.Extensions, namespaceSpatialNET. For the package validation and the API tracking this is an addition only (ADR 0028).API (extension methods on
IPolyline2D; parameter order as in ADR 0012):Method Returns Meaning LocateBetween(double fromM, double toM, factory)IPolyline2Dall stretches where M lies in [fromM, toM]LocateAlong(double m, factory)IMultiPoint2Dall points where M equals m, in the order along the lineBoth results are geometries and come from the factory. A hit list that was a value in ADR 0017 ("a list of all hits is not part of this step") is a geometry here because the OGC operations return one, and because the results are things a host draws.
Same rules as the other M methods (ADR 0017): only segments whose both ends carry M take part; a stretch without M is neither bridged nor an error but a gap. M is interpolated linearly on a segment. Nothing throws on data: no hit gives an empty polyline or multipoint. Z is interpolated at new points, original vertices keep their own values (ADR 0015).
LocateBetween:- The interval is closed; if
fromMis greater thantoMthe bounds are swapped, as a search has no direction. The result keeps the direction of the line: a stretch where M falls runs from the higher to the lower M. - The stretches of consecutive segments form one path; a gap (a segment outside the interval or without M) or the end of an input path starts the next path. Cut ends get exactly the bound as M (no rounding error from the interpolation).
- A stretch without length is not part of the result: if M touches the interval only at one point (the top of a hill, a bound equal to M at a single vertex), nothing is returned for it, as a piece of length 0 is nothing (ADR 0017,
Substring).LocateAlongfinds such points. Segments of length 0 are skipped. - A segment with constant M is entirely inside or entirely outside.
- The interval is closed; if
LocateAlong: every segment whose M range contains the value gives one point; a hit at a vertex shared by two segments counts once; a segment with constant M equal to the value answers with its start, asInterpolateByMdoes (so the first point ofLocateAlongequalsInterpolateByM). It does not return the whole constant segment: that is whatLocateBetween(m, m)does.Exceptions (ADR 0012):
ArgumentNullExceptionfornull,ArgumentOutOfRangeExceptionfor aNaNor infinitefromM,toMorm,InvalidOperationExceptionwithout a factory.Cost: O(n), one scan, no state.
Tests (ADR 0008): NTS has no M-based counterpart, so the cases are hand-written (
[Covers]) and compared with a brute-force scan (the length inside the interval over many random lines with random M). Also: non-monotonic M with several stretches and their direction, joined segments, boundaries and swapped bounds, gaps without M and several paths, constant M, touching at a point, Z at the cut ends, the shared-vertex rule, agreement withInterpolateByM, invalid input, empty lines.Playground and documentation: both have a descriptor (ADR 0011) on the examples with M of the length variants, as the other
...ByMmethods; the concept page "linear referencing" has a section.Out of scope for now: M intervals for several lines at once, an offset to the side, event tables (point and line events with overlay of intervals).
Considered Options
- Only
LocateBetween, rejected:LocateAlongis the same scan for points, and without it a repeated M value can only be found by the first hit - A list or an array of results instead of geometries, rejected: the OGC operations return geometries, and a host draws or stores the result like any other line or multipoint
- Returning one path per segment, rejected: it would split a stretch that continues over many vertices and burden the caller with joining it
- Returning zero-length stretches as one-point paths, rejected: a polyline path needs a length; the points are what
LocateAlongis for - Throwing if
fromMis greater thantoM, rejected: for a search the order of the bounds carries no meaning, swapping loses nothing - Letting
LocateAlongreturn a constant segment completely, rejected: a point result stays a point; the segment isLocateBetween(m, m) - Interpolating across a gap without M, rejected as in ADR 0017: it would invent measures