Linear referencing: by length and by M, first hit along the line, values instead of geometries
SpatialNET gets linear referencing on polylines: a position on a line is addressed either by its length along the line or by its M value (ADR 0015). The operations are Interpolate (the point at a position), Project (the position of the point nearest to a given point) and Substring (the piece between two positions), each in a length variant and a ...ByM variant. They are extension methods in SpatialNET.Extensions. As elsewhere (ADR 0012), point-like and scalar results are values (Coordinate?, double) that need no factory; only the pieces of Substring are geometries and come from the factory. M addresses a position only where the line carries M and never changes the geometry; for non-monotonic M, which real data has, the rule is first hit along the line, and nothing throws.
German version: 0017-lineare-referenzierung-laenge-und-m-erster-treffer.de.md
Consequences
Placement: static class
LinearReferencinginSpatialNET.Extensions, namespaceSpatialNET. No new package,SpatialNET.Corestays contracts only. For the package validation this is an addition only.API (extension methods on
IPolyline2D; parameter order as in ADR 0012: required parameters, thenfactory):Method Returns Meaning Interpolate(double distance)Coordinate?the point at a length; nullfor a line without pointsProject(Coordinate point)doublethe length of the point on the line nearest to point;NaNfor a line without pointsSubstring(double from, double to, factory)IPolyline2Dthe piece between two lengths InterpolateByM(double m)Coordinate?the point where the line first reaches m;nullif there is noneProjectToM(Coordinate point)doublethe M value at the nearest point; NaNif the line has no M thereSubstringByM(double fromM, double toM, factory)IPolyline2Dthe piece between the first hits of two M values ProjectandProjectToMalso exist forIPoint2D, which only converts. There are noIGeometry2Doverloads: the operations are defined on lines, and the boundary of a polygon is not a line here.Position along the line: the planar length, the same as
Length(). Z does not take part. The paths of a polyline are laid end to end in their order (cumulative length), with no connection assumed between the end of one path and the start of the next. Segments of length 0 contribute nothing. A length that falls exactly on the boundary of two paths belongs to the end of the earlier path (soInterpolatereturns that end, not the start of the next path).Interpolate:distanceis clamped to[0, length]: negative gives the start, too large gives the end. There is no "negative counts from the end" as in JTS (a caller computeslength - d).- A line whose points are all equal has length 0 and returns that point.
- The result carries Z and M interpolated on the segment, under the rules of ADR 0015: only if both ends have it, and at an original vertex exactly that vertex's own values.
Project: nearest point in the plane, planar distance. Among equally near points (a line that crosses or touches itself) the smallest length is returned, so that the answer is deterministic. The projection onto a segment is clamped to the segment.Substring:- Both lengths are clamped.
from < toruns forward,from > toreturns the piece reversed (the direction follows from → to), as in JTS. If the lengths are equal after clamping, the result is an empty polyline: a piece of length 0 is nothing, in line with the collapse rules of ADR 0006 and ADR 0007. - The piece is a polyline of one path per touched path; the gap between two paths is not bridged.
- New end vertices carry interpolated Z and M, original vertices inside keep theirs. The result is restricted to
SupportsZ/SupportsMof the factory (ADR 0015).
- Both lengths are clamped.
The
...ByMvariants:- Only segments whose both ends carry M take part. A stretch without M is neither interpolated across nor an error: it simply cannot answer.
- First hit: the line is scanned in its order (paths in order, segments in order). The first segment whose M range contains the value (closed interval) answers; the position inside it is linear in M. A segment with constant M equal to the value answers with its start. Non-monotonic M and values that occur several times (a loop) are therefore allowed, and the first occurrence wins.
InterpolateByMreturnsnullif no segment answers.SubstringByMfinds the length of both first hits and then behaves likeSubstring; if one value has no hit, the result is an empty polyline.ProjectToMreturns the M at the nearest point (the same nearest point asProject): interpolated if both ends of its segment carry M, the vertex's own M if the point is a vertex, otherwiseNaN.- A list of all hits is not part of this step (see Considered Options).
Exceptions (ADR 0012):
ArgumentNullExceptionfornull,ArgumentOutOfRangeExceptionfor aNaNor infinitedistance,from,to,m,fromM,toMor a non-finite point,InvalidOperationExceptionwithout a factory (onlySubstringandSubstringByM). Empty or degenerate lines never throw; they answernull,NaNor an empty polyline as above.No state, no snapshot: each call computes from the geometry in O(n). A reusable index of cumulative lengths for many queries on one long line can be added later without a break if a benchmark asks for it.
Tests (ADR 0008):
- Oracle for the length variants is the NTS
LengthIndexedLine(ExtractPoint,IndexOf,ExtractLine), with the documented differences (negative indices, clamping, the tie rule ofProject) asdivergence. Fixtures undersamples/interpolate/,samples/project/andsamples/substring/for the cases NTS can judge; the tag catalog is satisfied or its exceptions are justified in_catalog.json(hole, nesting and similar tags do not apply to lines). - NTS has no M-based counterpart, so
...ByMis covered by hand-written cases ([Covers]) and property tests: the first-hit rule against a brute-force scan, loops, gaps without M, constant M, M of zero. - Property tests (CsCheck) for the length variants:
Project(Interpolate(d))isdon simple lines; the length ofSubstring(a, b)is|b − a|after clamping;Substring(0, length)has the same X/Y as the line; for monotone M,InterpolateByM(M of Interpolate(d))returns the same point; M never changes any X/Y.
- Oracle for the length variants is the NTS
Playground and documentation: every public method needs a descriptor (ADR 0011) or a justified exemption.
Interpolate,ProjectandSubstringfollow the pattern ofCentroid,AreaandCut. The three...ByMmethods are exempt: the playground reads GeoJSON, which has no M (ADR 0015), so they would never answer there. A new concept page "linear referencing" in English and German, and a glossary entry.Out of scope for now: polygon boundaries, the list of all hits for a value, 3D lengths, M-based measures such as a length along M, and a precomputed length index.
Considered Options
- Length variants only (rejected: the main reason for M in the model is to address a line by it)
- Negative lengths count from the end as in JTS (rejected: clamping is simpler and avoids silent surprises; the end is
length - d) - Throw if a length lies outside the line (rejected: ADR 0012 keeps algorithms from throwing on data; clamping is predictable)
- Require monotonic M for the M variants and throw otherwise (rejected: real networks have loops and resets; the first-hit rule answers without an exception)
- Bridge gaps without M by interpolating across them (rejected: it would invent measures)
- A list of all hits as the only M API (rejected for now: most callers want one point; a list variant can be added without a break)
Interpolatecreating a point through the factory (rejected: a point-like result is a value, asCentroidin ADR 0012)Projectreturning a structure with length, point and distance (rejected:Interpolate(Project(p))andDistancegive the rest)IGeometry2Doverloads that accept polygon boundaries (rejected: the position along a polygon's rings has no natural start)- A
LengthIndexobject from the first step (rejected: no benchmark asks for it; it can follow without a break)