Table of Contents

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 Klasse LineEvents in SpatialNET.Extensions, Namespace SpatialNET, 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). T wählt der Host (ein int, ein Text, ein Record mit mehreren Feldern). Es ist ein einfacher Wert ohne Prüfung im Konstruktor, wie Circle (ADR 0026); die Operationen prüfen, was sie lesen. Eine Tabelle ist jedes IEnumerable<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<…>>, nach From, dann To sortiert):

    Methode Bedeutung
    Intersect(a, b, combine) ein Stück je überlappendem Paar aus einem Ereignis von a und einem von b, mit dem Wert combine(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, onlyA oder onlyB
    Difference(a, b) die Teile der Ereignisse von a, die kein Ereignis von b bedeckt, mit den Werten von a; von b zählen nur die Bereiche
    Dissolve(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 m enthält

    Es sind statische Methoden und keine Erweiterungsmethoden, weil Union, Intersect und ähnliche Namen bei jedem Aufrufer mit using System.Linq mit Enumerable kollidieren würden und eine Überladung für IEnumerable<LineEvent<T>> in jeder Liste neben den LINQ-Methoden angeboten würde.

  • Union nimmt drei Funktionen statt eines „fehlt“-Wertes. Für ein TA, das ein int oder ein Struct ist, gibt es kein ehrliches null: Ein Stück, das nur a bedeckt, bräuchte für b einen Wert, den es nicht gibt. both, onlyA und onlyB lassen den Aufrufer sagen, was jeder Fall bedeutet, ohne dass default für „keiner“ steht. Ein Paartyp mit HasA/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 == To wird 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, wie Substring und LocateBetween kein Stück der Länge 0 liefern (ADR 0017, ADR 0032). At ist 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 From größer als To wird mit vertauschten Grenzen gelesen (M kann abwärts laufen); das ist die Regel von LocateBetween (ADR 0032). NaN oder ein unendliches From oder To ist eine ArgumentOutOfRangeException, die Tabelle und Position des Ereignisses nennt; eine null-Tabelle oder -Funktion ist eine ArgumentNullException. Eine leere Tabelle ist eine normale Eingabe und ergibt ein leeres bzw. durchgereichtes Ergebnis.

  • Überlappungen innerhalb einer Tabelle. Intersect nimmt sie an: Jedes überlappende Paar ergibt ein Stück, wie bei einem Join zweier Tabellen. Union nicht: Ein Stück hätte zwei Werte aus derselben Tabelle, und both müsste eine Liste nehmen, also ist es eine ArgumentException, die die Tabelle nennt (sich berührende Ereignisse sind in Ordnung). Difference sieht von b nur die Bereiche, sie dürfen sich also überlappen. Dissolve, Clip und At nehmen alles an.

  • Dissolve verbindet gleiche Werte über andere Ereignisse hinweg. Es hält je Wert einen offenen Lauf, so ergeben A [0,5], B [2,3], A [4,8] zusammen A [0,8] und B [2,3]: Ereignisse anderer Werte verhindern nicht, dass zwei A sich verbinden, und sie werden nicht verändert, auch wo sie überlappen. Gleichheit ist die des comparer, standardmäßig die Standard-Gleichheit von T (bei einem Record alle Felder). Ein null-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 mit Dissolve.

  • Kosten: Intersect und Difference sortieren und suchen dann per Binärsuche das erste Ereignis, das heranreicht, also etwa O((n + m) log(n + m) + Ergebnisse); Union ist ein Durchlauf über die sortierten Grenzen; Dissolve ist 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ür Intersect, Union, Difference und Dissolve (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 ist LocateAlong), die Gegenrichtung von einer Geometrie zu einem Ereignis (erledigt in ADR 0034, LocateFeature), ein Fenster von M-Werten in den Operationen über Clip hinaus, 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; schlichte LineEvent<T>-Werte halten sie frei von Datenzugriff (ADR 0001)
  • Erweiterungsmethoden auf IEnumerable<LineEvent<T>>, verworfen: Sie würden mit Enumerable.Union, Intersect und Except kollidieren und jede Liste füllen
  • Union mit 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 Union und Intersect automatisch verbinden, verworfen: Der Schnitt an jeder Grenze ist ihr Zweck, und wer ein Stück je gleichem Wert will, ist ein Dissolve entfernt; sie müssten auch entscheiden, was gleich heißt
  • Halboffene Bereiche [From, To) für At, verworfen: Bereiche sind in LinearReferencing ü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 Union stillschweigend 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