Ereignistabellen: Intervallrechnung auf M-Bereichen
Ein Routensystem hält seine Fakten als Ereignisse: ein Bereich von M-Werten auf einer Route und einige Attribute (ein Tempolimit von Kilometer 3,0 bis 5,5, ein Belag, eine Straßenklasse). Die Fragen eines WebGIS sind Intervallfragen: Wo gelten zwei Tabellen gleichzeitig? (Tempolimit und Belag), wo hat eine Tabelle etwas, das einer anderen fehlt? (eine Straße ohne Radweg), welche benachbarten Stücke mit gleichem Wert lassen sich zusammenfassen? Das bietet ArcGIS als „Overlay Route Events“, und NTS hat nichts Vergleichbares. LineEvents macht diese Rechnung auf den Zahlen einer Route; die Geometrie kommt danach mit LocateBetween (ADR 0032).
English version: 0033-ereignistabellen-intervallrechnung.md
Consequences
Ort: der Werttyp
LineEvent<T>und die statische KlasseLineEventsinSpatialNET.Extensions, NamespaceSpatialNET, in einer eigenen Datei. Kein neues Paket. Für die Paketvalidierung und die API-Verfolgung ist das eine reine Ergänzung (ADR 0028).Kein Datenbankzugriff, keine Datenbankbegriffe. Die Bibliothek liest nie eine Tabelle und kennt weder Routen-Id noch Spalte noch Verbindung: Der Host übergibt die Zeilen als
LineEvent<T>-Werte und gruppiert selbst nach Route (eine Zeile LINQ, in der Dokumentation gezeigt). Das hält die Bibliothek so frei von Datenzugriff wie den Rest (ADR 0001, ADR 0004) und vermeidet ein zweites, datenbankförmiges Modell einer Tabelle, das jeder Host auf sein eigenes abbilden müsste.Der Datentyp:
readonly record struct LineEvent<T>(double From, double To, T Value).Twählt der Host (einint, ein Text, ein Record mit mehreren Feldern). Es ist ein einfacher Wert ohne Prüfung im Konstruktor, wieCircle(ADR 0026); die Operationen prüfen, was sie lesen. Eine Tabelle ist jedesIEnumerable<LineEvent<T>>.Ereignisse sind in M-Werten, nicht in Längen. Eine Tabelle, die als Meter ab Routenanfang gespeichert ist, rechnet der Host zuerst um, oder die Route wird so kalibriert, dass M diese Länge ist (ADR 0030). Die Operationen sehen nie eine Route; sie haben keine Geometrie.
Operationen (alle statisch, Ergebnisse sind
IReadOnlyList<LineEvent<…>>, nachFrom, dannTosortiert):Methode Bedeutung Intersect(a, b, combine)ein Stück je überlappendem Paar aus einem Ereignis von aund einem vonb, mit dem Wertcombine(valueA, valueB)Union(a, b, both, onlyA, onlyB)die Route an jeder Grenze beider Tabellen zerlegt, ein Stück überall, wo mindestens eine Tabelle ein Ereignis hat, mit dem Wert von both,onlyAoderonlyBDifference(a, b)die Teile der Ereignisse von a, die kein Ereignis vonbbedeckt, mit den Werten vona; vonbzählen nur die BereicheDissolve(events, comparer?)Ereignisse, die sich berühren oder überlappen und gleiche Werte haben, werden eins Clip(events, from, to)die Ereignisse auf einen Bereich zugeschnitten At(events, m)die Ereignisse, deren Bereich menthältEs sind statische Methoden und keine Erweiterungsmethoden, weil
Union,Intersectund ähnliche Namen bei jedem Aufrufer mitusing System.LinqmitEnumerablekollidieren würden und eine Überladung fürIEnumerable<LineEvent<T>>in jeder Liste neben den LINQ-Methoden angeboten würde.Unionnimmt drei Funktionen statt eines „fehlt“-Wertes. Für einTA, das einintoder ein Struct ist, gibt es kein ehrlichesnull: Ein Stück, das nurabedeckt, bräuchte fürbeinen Wert, den es nicht gibt.both,onlyAundonlyBlassen den Aufrufer sagen, was jeder Fall bedeutet, ohne dassdefaultfür „keiner“ steht. Ein Paartyp mitHasA/HasB-Flags wurde erwogen und als schwerer lesbar verworfen.Bereiche sind geschlossen, aber nur ein Bereich mit Länge zählt. Ein Ereignis mit
From == Towird ignoriert. Keine Operation liefert ein Stück ohne Länge: Zwei Nachbarn[0, 5]und[5, 9]berühren sich bei 5, und dazwischen liegt nichts, wieSubstringundLocateBetweenkein Stück der Länge 0 liefern (ADR 0017, ADR 0032).Atist die Ausnahme, die die Grenze zeigt: Beide Nachbarn enthalten 5, also kommen beide zurück, und der Aufrufer entscheidet, welches er braucht.Eingaberegeln. Die Eingabe darf unsortiert sein. Ein Ereignis mit
Fromgrößer alsTowird mit vertauschten Grenzen gelesen (M kann abwärts laufen); das ist die Regel vonLocateBetween(ADR 0032).NaNoder ein unendlichesFromoderToist eineArgumentOutOfRangeException, die Tabelle und Position des Ereignisses nennt; einenull-Tabelle oder -Funktion ist eineArgumentNullException. Eine leere Tabelle ist eine normale Eingabe und ergibt ein leeres bzw. durchgereichtes Ergebnis.Überlappungen innerhalb einer Tabelle.
Intersectnimmt sie an: Jedes überlappende Paar ergibt ein Stück, wie bei einem Join zweier Tabellen.Unionnicht: Ein Stück hätte zwei Werte aus derselben Tabelle, undbothmüsste eine Liste nehmen, also ist es eineArgumentException, die die Tabelle nennt (sich berührende Ereignisse sind in Ordnung).Differencesieht vonbnur die Bereiche, sie dürfen sich also überlappen.Dissolve,ClipundAtnehmen alles an.Dissolveverbindet gleiche Werte über andere Ereignisse hinweg. Es hält je Wert einen offenen Lauf, so ergebenA [0,5],B [2,3],A [4,8]zusammenA [0,8]undB [2,3]: Ereignisse anderer Werte verhindern nicht, dass zweiAsich verbinden, und sie werden nicht verändert, auch wo sie überlappen. Gleichheit ist die descomparer, standardmäßig die Standard-Gleichheit vonT(bei einem Record alle Felder). Einnull-Wert ist erlaubt. Union und Intersect verbinden ihre Ergebnisse nicht selbst, denn das Schneiden an jeder Grenze ist ihr Zweck; wo der Aufrufer es will, folgt er mitDissolve.Kosten:
IntersectundDifferencesortieren und suchen dann per Binärsuche das erste Ereignis, das heranreicht, also etwa O((n + m) log(n + m) + Ergebnisse);Unionist ein Durchlauf über die sortierten Grenzen;Dissolveist eine Sortierung und ein Dictionary. Es wird kein Zustand gehalten.Tests (ADR 0008): NTS hat kein Gegenstück. Die Fälle sind von Hand geschrieben (
[Covers]) mit dem Beispiel der Dokumentation (Tempolimit, Belag, Brücke, Radweg), den Grenzen und den Überlappungsregeln, dazu ein Modelltest: Zufällige Tabellen mit ganzzahligen Enden werden mit einer Zelle-für-Zelle-Auswertung an jedem halbzahligen M verglichen, fürIntersect,Union,DifferenceundDissolve(jeder Wert bleibt dort, wo er galt, keine gleichen Werte berühren sich). Außerdem wird geprüft, dass das Ergebnis sortiert und frei von Stücken ohne Länge ist.Playground und Dokumentation: kein Deskriptor (ADR 0011): Die Operationen nehmen Tabellen, keine Geometrien, die die Oberfläche nicht bietet; sie sind mit dieser Begründung ausgenommen, wie
UnionAll. Die neue Konzeptseite „Ereignistabellen“ auf Englisch und Deutsch erklärt Tabellen hinein und heraus mit dem Beispiel, die obigen Regeln und den Weg zur Karte; das Cookbook hat ein Rezept von den Tabellen bis zu den Längen der Stücke auf der Straße; das Glossar hat „event“.Vorerst nicht dabei: Punktereignisse als eigener Typ (ein Punkt in einem Linienereignis ist
At, ein Punkt auf der Karte istLocateAlong), die Gegenrichtung von einer Geometrie zu einem Ereignis (erledigt in ADR 0034,LocateFeature), ein Fenster von M-Werten in den Operationen überCliphinaus, und mehrere Routen in einem Aufruf.
Considered Options
- Ein Tabellenobjekt (
EventTable<T>) mit Routen-Id, Spalten und Verbindung, verworfen: Die Bibliothek würde Datenbankbegriffe und ein zweites Modell einer Tabelle übernehmen, das jeder Host abbilden muss; schlichteLineEvent<T>-Werte halten sie frei von Datenzugriff (ADR 0001) - Erweiterungsmethoden auf
IEnumerable<LineEvent<T>>, verworfen: Sie würden mitEnumerable.Union,IntersectundExceptkollidieren und jede Liste füllen Unionmit einem „fehlt“-Wert (TA?/TB?oder ein Paar mit Flags), verworfen: Für Werttypen nicht ohne Mehrdeutigkeit brauchbar und schwerer lesbar als drei Funktionen- Die Ergebnisse von
UnionundIntersectautomatisch verbinden, verworfen: Der Schnitt an jeder Grenze ist ihr Zweck, und wer ein Stück je gleichem Wert will, ist einDissolveentfernt; sie müssten auch entscheiden, was gleich heißt - Halboffene Bereiche
[From, To)fürAt, verworfen: Bereiche sind inLinearReferencingüberall geschlossen (ADR 0032), und eine halboffene Regel würde dem Aufrufer eine Seite aussuchen; es kommen stattdessen beide zurück - In jeder Operation bei Überlappungen werfen, verworfen: Ein Join zweier Tabellen (
Intersect) ist mit Überlappungen wohldefiniert, und unsaubere Daten sollen eine Anfrage nicht stoppen, wo das Ergebnis klar ist - In
Unionstillschweigend eines von zwei überlappenden Ereignissen nehmen, verworfen: Es würde ein Datenproblem verbergen und ein von der Reihenfolge abhängiges Ergebnis liefern - Längen statt M-Werte nehmen, verworfen: Die Ereignisse eines Routensystems sind in M gespeichert; eine Umrechnung ist ein Aufruf für den Host, und Routen, deren M eine Länge ist, brauchen keine
- Mehrere Routen in einem Aufruf, mit einer Schlüsselfunktion, vorerst verworfen: Gruppieren ist für den Host eine Zeile, und die Operationen bleiben frei von Schlüsseln