Wenn Geometriealgorithmen einander widersprechen: Präzisionsgrenzen in Komp-Geom

Inhaltsverzeichnis

Dieser deutschsprachige Beitrag ist eine KI-unterstützte Übersetzung des englischen Originals.

Zwei Strecken schneiden sich entweder oder sie tun es nicht. Zumindest dachte ich, dass ich diese Frage stelle.

Dieselbe Schnittstelle nahe einem Endpunkt ist in beiden Bildern zu sehen. Ein paarweiser Test meldet sie, während ein Sweep-Line-Algorithmus das Streckenpaar auslässt. Die Darstellung veranschaulicht das Prinzip.

In Komp-Geom, meiner Kotlin-Multiplatform-Bibliothek für Geometrie, kann ein paarweiser Streckentest einen Kontakt melden, den ein Bentley-Ottmann-Sweep über dieselbe endliche Eingabe übersieht. Das geschieht nahe einer Präzisionsgrenze, wenn Koordinaten um winzige Beträge verändert wurden. Zuerst fiel mir das Problem beim Sweep auf, aber inzwischen sehe ich es nicht mehr als reines Sweep-Line-Problem. Der Sweep macht lediglich die Folgen sichtbar: Wenn zwei numerische Entscheidungen einander widersprechen, kann eine ganze Kette späterer Entscheidungen schiefgehen.

Die Frage, die ich beantworten möchte, ist allgemeiner. Was bedeutet es für eine Geometriebibliothek, konsistente Entscheidungen über ihre Eingabe zu treffen, und was sollte sie versprechen, wenn ein Ergebnis nahe einer Präzisionsgrenze liegt?

Eine Präzisionsgrenze ist eine Entscheidungsgrenze #

Ein Double speichert eine Zahl mit endlicher Genauigkeit. Bei der Rechnung mit solchen Zahlen werden Zwischenergebnisse gerundet. Ein Epsilon ist etwas anderes: eine Regel, nach der eine Anwendung zwei Werte als hinreichend nah beieinander betrachtet. Ein Epsilon misst nicht den Rundungsfehler jedes Ausdrucks. Es kann auch bewusst den Unterschied zwischen verschiedenen Eingabekoordinaten verwischen.

Komp-Geoms EpsilonDoubleEquivalence betrachtet endliche Werte a und b als näherungsweise gleich, wenn

|a − b| ≤ ε · max(1, |a|, |b|)

Das voreingestellte geometrische Epsilon ist 10⁻¹⁰. Nahe null hat die Schwelle einen absoluten Anteil, bei größeren Beträgen skaliert sie mit den Operanden. Operationen können eine andere DoubleEquivalence erhalten. Das ist nützlich, wenn ein lokaler Vergleich die Vorstellung des Aufrufers von Nähe berücksichtigen soll.

Aber Nähe ist keine Identität. Setzen wir ε = 10⁻⁸, a = 0, b = 0,75 × 10⁻⁸ und c = 1,5 × 10⁻⁸. Die ersten beiden Werte liegen nah beieinander, ebenso die letzten beiden, aber der erste und der letzte nicht. Näherungsweise Gleichheit ist nicht transitiv. Sie darf nicht als Identität oder Vergleichsordnung einer sortierten Sammlung dienen. Auch Apache Commons Geometry unterscheidet zwischen näherungsweisem eq() und strengem equals() samt Hashing. Sein Präzisionskontext ist für lokale Operationen mit Toleranzen nützlich. eq() aus der Objektidentität herauszuhalten garantiert allein jedoch noch nicht, dass die Prädikate und konstruierten Koordinaten aller Algorithmen nahe einer Grenze miteinander übereinstimmen.

Drei Punkte auf einem Zahlenstrahl zeigen, warum näherungsweise Gleichheit nicht transitiv ist: a liegt nahe bei b und b nahe bei c, aber a nicht nahe bei c.

Noch wichtiger ist, dass ein Vergleich von Zahlen nicht dasselbe ist wie eine Entscheidung über Geometrie. Ein Orientierungstest fragt, auf welcher Seite einer gerichteten Geraden ein Punkt liegt. Ein Inzidenztest fragt, ob ein Punkt zu einer Kante gehört. Ein Schnitttest fragt, ob zwei Kanten einander treffen. Eine Konstruktion berechnet einen neuen Punkt. Wenn diese Operationen einander widersprechen, kann sich die Zusammenhangsstruktur des Ergebnisses ändern, nicht nur seine letzte Nachkommastelle.

Das betrifft weit mehr als einen Sweep #

Betrachten wir einen Algorithmus zur Berechnung der konvexen Hülle, der drei beinahe kollineare Punkte untersucht. Wechselt das Vorzeichen seines Orientierungstests, kann er einen Punkt behalten, der entfernt werden müsste, oder einen Punkt entfernen, der ein Eckpunkt der Hülle sein müsste. Ein Polygonalgorithmus, der entscheidet, ob ein Punkt innen, auf dem Rand oder außen liegt, muss bei Randfällen miteinander vereinbare Antworten liefern. Bei einer Triangulierung kann ein falsches Vorzeichen im Orientierungs- oder Umkreistest die kombinatorische Struktur verändern. Eine Überlagerung oder ein Arrangement von Polygonen muss übereinstimmend entscheiden, ob zwei Kanten sich an einem Eckpunkt treffen, bevor Flächen zusammengesetzt werden können. Das sind Beispiele für dieselbe allgemeine Abhängigkeit, keine Behauptung, dass all diese Algorithmen in Komp-Geom derzeit fehlschlagen.

Orientierung kann eine konvexe Hülle verändern, Inzidenz ein Polygonarrangement und die Reihenfolge der Ereignisse einen Streckensweep. Alle drei hängen von einem konsistenten Präzisionsvertrag ab.

In anderer Form begegnete mir das bei der Arbeit an meiner Bachelorarbeit über Minkowski-Summen. Wenn nahezu identische berechnete Koordinaten in einer DCEL zu getrennten Eckpunkten wurden, konnten Kanten unverbunden bleiben und Flächen sich nicht schließen. Der daraus entstehende Fehler war topologisch. Koordinaten stärker zu runden half dieser Implementierung in manchen Fällen. Es war aber eine Strategie zur Fehlerbehebung und keine allgemeine Definition geometrischer Korrektheit.

Nicht jede numerische Operation braucht eine exakte Topologie. Für die Anzeige kann ein näherungsweiser Abstand genügen. Strengere Anforderungen entstehen, wenn eine Zahl darüber entscheidet, welche Objekte existieren oder verbunden sind.

Warum der Sweep die Lücke sichtbar machte #

Ein paarweiser Test klassifiziert einen Kontakt mit der konfigurierten Toleranz und berechnet seinen Punkt mit Double-Arithmetik. Der Sweep muss diesen Punkt anschließend in eine Ereigniswarteschlange einordnen. Komp-Geom schert die Koordinaten für die Ereignisreihenfolge und prüft die Inzidenz im ursprünglichen Koordinatensystem. Sein Statusbaum verwendet inzwischen eine stabile, positionsbasierte Ordnung statt einer epsilonabhängigen Vergleichsfunktion. Ereigniskoordinaten und Streckenhöhen werden aber weiterhin mit gerundeten Doubles berechnet, während die Inzidenzprüfungen Toleranzen berücksichtigen.

Der differenzielle Test zeigt einen Widerspruch entlang dieses Wegs. Ein konstruierter Ereignispunkt könnte eine spätere Prüfung nicht mehr bestehen, die der paarweise Test bestanden hat. Die Abbildung zeigt einen möglichen Mechanismus, keine nachgewiesene Diagnose des beobachteten Falls.

Schematische Darstellung einer Schnittstelle nahe einem Endpunkt: Die paarweise Klassifikation akzeptiert einen Kontakt, aber ein verschobener konstruierter Ereignispunkt könnte eine spätere Inzidenzprüfung nicht bestehen. Die Verschiebung ist zur Veranschaulichung übertrieben.

Die Ansätze definieren unterschiedliche Arten von Geometrie #

Es gibt keinen einzelnen Schalter für „mehr Präzision“. Die ersten beiden Ansätze befassen sich mit unterschiedlichen Teilen einer Berechnung und können zusammenwirken. Der dritte verändert die Geometrie bewusst auf eine gewählte Auflösung.

Gefilterte robuste Prädikate: zuverlässig entscheiden #

Ein Prädikat beantwortet eine kleine Frage wie „Liegt dieser Punkt links oder rechts von dieser Geraden?“. Wenn drei Punkte fast auf einer Geraden liegen, ist die Antwort schwierig, weil eine Rundung verändern könnte, auf welcher Seite der dritte Punkt zu liegen scheint. Ein gefiltertes Prädikat versucht zuerst die schnelle Berechnung. Ist der mögliche Rundungsfehler zu klein, um die Antwort zu verändern, übernimmt es das Ergebnis. Andernfalls rechnet es genauer, bevor es entscheidet.

Shewchuks adaptive Prädikate nutzen diesen Ansatz unter anderem für Orientierungsfragen. Sie ermitteln die richtige Antwort für die als Eingabe übergebenen Gleitkommazahlen. Sie können uns nicht sagen, ob diese Zahlen ein vermessenes Objekt in der realen Welt vollkommen korrekt beschreiben, und sie berechnen für sich genommen auch keinen exakten Schnittpunkt. Anders als ein Epsilonvergleich erklärt der Filter ein kleines Ergebnis nicht einfach zu null.

Ein gefiltertes Prädikat übernimmt ein Vorzeichen, wenn die Fehlerschranke null nicht erreichen kann. Andernfalls verfeinert es die Berechnung vor der Entscheidung. Diese Schranke ist kein Anwendungs-Epsilon.

Prädikate und Konstruktionen: erst entscheiden, dann lokalisieren #

Zu wissen, dass zwei Strecken sich schneiden, ist das eine. Zu berechnen, wo sie sich schneiden, ist etwas anderes. Das Erste ist eine Entscheidung, also ein Prädikat. Das Zweite ist eine Konstruktion: Sie erzeugt eine neue Koordinate. Die Hinweise von CGAL zur Robustheit behandeln beides als getrennte Aufgaben. Sein Kernel-Design fragt danach, welche Operationen ein Algorithmus benötigt.

Auch wenn die Eingabeendpunkte Double-Werte sind, kann ihr Schnittpunkt zwischen den Zahlen liegen, die ein Double darstellen kann. Ein näherungsweiser Vec2 reicht oft aus, um einen Punkt auf dem Bildschirm zu zeichnen. Als Identität eines gemeinsamen Eckpunkts oder als Schlüssel für die Reihenfolge späterer Ereignisse ist er nicht unbedingt sicher. Wenn ein Algorithmus weitere Entscheidungen über diesen Punkt trifft, muss er eine Darstellung oder Vergleichsmöglichkeit beibehalten, die mit der früheren Entscheidung konsistent ist.

Ein robustes Prädikat entscheidet, ob Strecken sich schneiden. Eine intern konsistente Konstruktion kann spätere Entscheidungen leiten. Ein näherungsweise ausgegebener Punkt ist für die Ausgabe nützlich, aber nicht automatisch ein exakter Schlüssel.

Geometrie auf einem festen Raster: eine Auflösung wählen #

Nehmen wir an, eine Karte erfasst Orte auf einem Raster mit einem Meter Abstand. Zwei verschiedene Punkte könnten beide auf dieselbe Rasterposition verschoben werden. In der reduzierten Geometrie sind sie nun ein Punkt. Eine schmale Lücke kann sich schließen und eine kurze Linie zusammenfallen. Das ist kein Rundungsfehler, den man verstecken sollte. Es ist eine bewusste Regel dafür, welche Details die Karte bewahrt.

Korrektes Snap Rounding braucht auch Regeln für die Linien und Formen, die mit diesen Punkten verbunden sind. Der Präzisionsreduzierer von JTS dokumentiert einen Modus, der eine gültige reduzierte Topologie erhält, warnt aber auch davor, dass nahe Polygone verschmelzen können. Ein Raster ist nützlich, wenn eine Anwendung eine sinnvolle Auflösung hat. Es ist jedoch kein direkter Ersatz dafür, zwei Werte als näherungsweise gleich zu betrachten.

Zwei getrennte Punkte werden nach dem Einrasten auf einen Rastereckpunkt abgebildet. Im Unterschied zu einem näherungsweisen Vergleich verändert das Einrasten die Geometrie bewusst.

Die Entscheidung für Komp-Geom #

Für Komp-Geom würde ich zuerst eine Topologie prüfen, die die endlichen Double-Eingabekoordinaten als exakt betrachtet. Dabei kämen für gewöhnliche Fälle gefilterte Prädikate und bei ungewissem Ergebnis genauere Berechnungen zum Einsatz. Das würde die geometrische Semantik der API verändern, nicht nur ihre numerische Genauigkeit: Ein Beinahe-Treffer, der derzeit aufgrund der Toleranz als Kontakt akzeptiert wird, würde nicht mehr als Schnitt gelten. Ein als Vec2 zurückgegebener Schnittpunkt könnte weiterhin näherungsweise sein. Dieser gerundete Punkt dürfte aber nicht stillschweigend die Ereignisreihenfolge oder Eckpunktidentität bestimmen.

Ich würde mit dem Streckenschnitt und dem Sweep beginnen, um den gesamten Vertrag zu testen. Danach würde ich dieselben Regeln für Prädikate und Konstruktionen auf andere Algorithmen anwenden, bei denen die Topologie wichtig ist. EpsilonDoubleEquivalence würde ich für lokale näherungsweise Vergleiche beibehalten und eine Geometrie auf festem Raster als separates Modell betrachten.

Der Sweep hat die Lücke sichtbar gemacht, aber das Ziel ist größer: Jede Entscheidung, die die geometrische Topologie verändert, muss einem konsistenten Modell folgen.