Event tables: interval arithmetic on M ranges
A route system holds its facts as events: a range of M values on a route and some attributes (a speed limit from kilometre 3.0 to 5.5, a surface, a road class). The questions a web GIS asks are interval questions: where do two tables hold at the same time? (speed limit and surface), where does one table have something that another lacks? (a road without a bicycle path), which neighbouring pieces with the same value can be joined? This is what ArcGIS offers as "overlay route events", and NTS has nothing like it. LineEvents does this arithmetic on the numbers of one route; the geometry comes afterwards with LocateBetween (ADR 0032).
German version: 0033-ereignistabellen-intervallrechnung.de.md
Consequences
Placement: the value type
LineEvent<T>and the static classLineEventsinSpatialNET.Extensions, namespaceSpatialNET, in their own file. No new package. For the package validation and the API tracking this is an addition only (ADR 0028).No database access, no database terms. The library never reads a table and has no notion of a route id, a column or a connection: the host hands over the rows as
LineEvent<T>values and groups by route itself (one line of LINQ, shown in the documentation). This keeps the library as free of data-access code as the rest of it (ADR 0001, ADR 0004), and it avoids a second, DB-shaped model of a table that every host would have to map onto its own.The data type:
readonly record struct LineEvent<T>(double From, double To, T Value).Tis the host's choice (anint, a string, a record with several fields). It is a plain value without validation in the constructor, likeCircle(ADR 0026); the operations check what they read. A table is anyIEnumerable<LineEvent<T>>.Events are in M values, not in lengths. A table that is stored as metres from the start of the route is converted by the host first, or the route is calibrated so that M is that length (ADR 0030). The operations never look at a route; they have no geometry.
Operations (all static, results are
IReadOnlyList<LineEvent<…>>sorted byFrom, thenTo):Method Meaning Intersect(a, b, combine)one piece per overlapping pair of an event of aand one ofb, with the valuecombine(valueA, valueB)Union(a, b, both, onlyA, onlyB)the route cut at every boundary of either table, one piece wherever at least one table has an event, with the value of both,onlyAoronlyBDifference(a, b)the parts of the events of athat no event ofbcovers, with the values ofa; only the ranges ofbcountDissolve(events, comparer?)events that touch or overlap and have equal values become one Clip(events, from, to)the events cut to a range At(events, m)the events whose range contains mThey are static methods and not extension methods, because
Union,IntersectandExcept-like names would collide withEnumerablefor every caller that hasusing System.Linq, and an overload that takesIEnumerable<LineEvent<T>>would be offered next to the LINQ ones in every list.Uniontakes three functions instead of a "missing" value. For aTAthat is anintor a struct there is no honestnull: a piece that onlyacovers would need a value forbthat does not exist.both,onlyAandonlyBmake the caller say what each case means, withoutdefaultstanding for "none". A pair type withHasA/HasBflags was considered and rejected as heavier to read.Ranges are closed, but only a range with length counts. An event with
From == Tois ignored. No operation returns a piece without length: two neighbours[0, 5]and[5, 9]touch at 5 and nothing lies between them, asSubstringandLocateBetweendo not return a piece of length 0 (ADR 0017, ADR 0032).Atis the exception that shows the boundary: both neighbours contain 5, so both are returned, and the caller decides which one it needs.Input rules. The input may be unsorted. An event with
Fromgreater thanTois read with the two swapped (M may run downwards); this is the rule ofLocateBetween(ADR 0032).NaNor an infiniteFromorTois anArgumentOutOfRangeExceptionthat names the table and the position of the event; anulltable or function is anArgumentNullException. An empty table is a normal input and gives an empty or pass-through result.Overlaps within one table.
Intersectaccepts them: every overlapping pair gives a piece, which is what a join of two tables does.Uniondoes not: a piece would have two values from the same table andbothwould need to take a list, so it is anArgumentExceptionthat names the table (touching events are fine).Differencelooks only at the ranges ofb, so they may overlap.Dissolve,ClipandAtaccept anything.Dissolvejoins equal values through other events. It keeps one open run per value, soA [0,5],B [2,3],A [4,8]givesA [0,8]andB [2,3]: events of other values do not stop twoAs from joining, and they are not changed, also where they overlap. Equality is that of thecomparer, by default the default equality ofT(for a record, all fields). Anullvalue is allowed. Union and Intersect do not join their results themselves, since cutting at every boundary is what they are for; the caller follows withDissolvewhere it wants it.Cost:
IntersectandDifferencesort and then use a binary search for the first event that can reach, so about O((n + m) log(n + m) + results);Unionis a sweep over the sorted boundaries;Dissolveis one sort and a dictionary. No state is kept.Tests (ADR 0008): NTS has no counterpart. The cases are hand-written (
[Covers]) with the example of the documentation (speed limit, surface, bridge, bicycle path), the boundaries and the overlap rules, and a model test: random tables with integer ends are compared with a cell-by-cell evaluation at every half-integer M, forIntersect,Union,DifferenceandDissolve(every value is kept where it held, no equal values touch). The result is also checked to be sorted and free of pieces without length.Playground and documentation: no descriptor (ADR 0011): the operations take tables, not geometries, which the surface does not offer; they are listed as exempt with this reason, as
UnionAll. The new concept page "event tables" in English and German explains tables in and out with the example, the rules above and the way to the map; the cookbook has a recipe from the tables to the lengths of the pieces on the road; the glossary has "event".Out of scope for now: point events as a type of their own (a point in a line event is
At, a point on the map isLocateAlong), the reverse direction from a geometry to an event (done in ADR 0034,LocateFeature), a window of M values in the operations beyondClip, and several routes in one call.
Considered Options
- A table object (
EventTable<T>) with route id, columns and a connection, rejected: the library would take on database terms and a second model of a table that every host has to map; plainLineEvent<T>values keep it free of data access (ADR 0001) - Extension methods on
IEnumerable<LineEvent<T>>, rejected: they would collide withEnumerable.Union,IntersectandExceptand clutter every list Unionwith a "missing" value (TA?/TB?, or a pair with flags), rejected: unusable for value types without ambiguity, and heavier to read than three functions- Joining the results of
UnionandIntersectautomatically, rejected: the cut at every boundary is the point of them, and a caller who wants one piece per equal value is oneDissolveaway; it would also have to decide what equal means - Half-open ranges
[From, To)forAt, rejected: ranges are closed everywhere else inLinearReferencing(ADR 0032), and a half-open rule would pick a side for the caller; both are returned instead - Throwing for overlaps in every operation, rejected: a join of two tables (
Intersect) is well defined with overlaps, and dirty data should not stop a request where the result is clear - Silently using one of two overlapping events in
Union, rejected: it would hide a data problem and give a result that depends on the order - Taking lengths instead of M values, rejected: the events of a route system are stored in M; a conversion is one call for the host, and routes whose M is a length need none
- Several routes in one call, with a key function, rejected for now: grouping is one line for the host and the operations stay free of keys