Wer hier am nächsten ist. Streue Kerne in die Fläche und färbe jeden Punkt nach dem Kern, der ihm am nächsten liegt: Es entsteht eine Aufteilung in Zellen — und von selbst ein zweites Gebilde, das Netz der Kerne, deren Zellen aneinandergrenzen. Beide sind dieselbe Sache von zwei Seiten gesehen.
- Bis 400 Kerne, Zellen nach der Zahl ihrer Nachbarn eingefärbt, Netz darüber
- Klicken setzt, Ziehen verschiebt, Umschalt-Klick nimmt weg — das Netz wird bei jeder Bewegung neu gebaut
- Umkreise einblenden: die Bedingung, aus der das ganze Netz folgt, direkt sichtbar
- Entspannen rückt jeden Kern in den Schwerpunkt seiner Zelle (Lloyd)
- Knappheit messen zählt aus, wie eng die Entscheidungen ausfallen — und wo der Rundungsfehler anfängt
- Prüflauf — elf Zeilen, darunter zwei erschöpfende
Das ganze Verfahren steht und fällt mit einer einzigen Frage: liegt dieser Punkt im Umkreis jenes Dreiecks? Das ist das Vorzeichen einer 3×3-Determinante. Nahe null entscheidet nicht mehr die Geometrie, sondern die Rundung — und ein falsches Vorzeichen macht nicht nur ein Dreieck falsch, sondern kann das Netz zerreißen, weil jeder weitere Schritt darauf aufbaut.
Deshalb liegen hier alle Punkte auf einem ganzzahligen Raster von 2²⁰ × 2²⁰. Ein Rasterschritt ist auf dem Schirm weniger als ein Tausendstel Pixel — man sieht ihn nicht, aber er macht jede Entscheidung exakt nachrechenbar:
- schnell in Doppelgenauigkeit rechnen,
- abschätzen, wie weit die Rundung höchstens getragen haben kann,
- bei Zweifel an
BigIntabgeben.
Die Abschätzung ist mit 1e-13 rund hundertfach größer als der tatsächliche Fehler. Was das
kostet und was es bringt, steht unten in Zahlen.
| Behauptung | Ergebnis |
|---|---|
| kein fremder Punkt im Umkreis | 240 114 Paare aus Dreieck und Punkt — jedes Dreieck gegen jeden Punkt |
| Euler und die Dreiecksformel | 6 Mengen · V − E + F = 2 und 2n − 2 − h, h aus einer anders gebauten Hülle |
| Zellen gegen rohe Nachbarsuche | 160 000 Rasterpunkte, jeder gegen alle 50 Abstände · 0 Abweichungen |
| Netznachbarn genügen für die Zellen | gegen 5,4 Nachbarn statt gegen 39 Kerne geschnitten · Flächenunterschied 5·10⁻¹⁵ |
| die Zellen decken die Fläche genau | Summe der Zellflächen gegen die Kastenfläche: 6·10⁻¹⁶ |
| nächster Nachbar ist immer eine Kante | alle 4 005 Paare · 0 fehlende Kanten |
| kein anderes Netz ist weniger spitz | alle 161 möglichen Netze kleiner Mengen aufgezählt · 0 schlagen dieses |
| 240 Punkte auf einem Kreis | abgesichert 238 Dreiecke, 0 fehlerhaft · nur Fließkomma: 260 Dreiecke, 58 fehlerhaft |
| vier Punkte wirklich auf einem Kreis | 180 ganze Punkte auf einem Kreis · 38 940 Vierergruppen, Determinante genau null · der schnelle Weg behauptet in 51,8 % ein Innen oder Außen |
| die Schranke war nie zu klein | 20 000 Fälle · 3 290 Abgaben an BigInt · in den übrigen 0 falsche Vorzeichen |
| Entspannen gleicht die Zellen an | Flächenstreuung 0,601 → 0,275 in 10 Schritten, kein Anstieg |
Die siebte Zeile ist die unbequemste: Sie prüft nicht gegen eine Auswahl, sondern zählt über Kantentausch jedes Netz auf, das für diese Punkte überhaupt möglich ist, und vergleicht die Winkel der Größe nach. Keines ist weniger spitz als dieses.
Das Netz war zwei Dreiecke zu klein — und alles sah trotzdem grün aus. Der Bau setzt die Punkte
in ein großes Hilfsdreieck ein, das am Ende weggeworfen wird. Meins war zu klein: 4 × 2²⁰. Ergebnis
bei 80 Kernen: 145 statt 147 Dreiecke, der Rand des Netzes hatte 13 Ecken statt der 11 der
konvexen Hülle — zwei innere Punkte lagen plötzlich außen. Das Tückische daran ist, was dabei
nicht auffällt: Die Eulersche Formel stimmt weiter (V − E + F = 2), die Umkreisbedingung
stimmt für jedes einzelne Dreieck, das Bild sieht richtig aus. Ein Netz, das nur einen Teil der
Fläche abdeckt, ist eben immer noch ein gültiges Netz — nur nicht das gesuchte. Aufgefallen ist es
allein an der Dreiecksformel 2n − 2 − h, gegen eine unabhängig gebaute Hülle gehalten. Seitdem
liegen die Hilfspunkte bei 2⁵⁰ — auf diesem Raster kann ein Umkreis höchstens rund 2⁴⁰ groß
werden, das ist tausendfach Luft — und für sie wird immer exakt gerechnet.
BigInt(a.x - d.x) rundet, bevor BigInt etwas davon sieht. Genau der Fix von oben hätte den
nächsten Fehler eingebaut: Die Differenz wird erst in Doppelgenauigkeit ausgerechnet und dann
umgewandelt. Bei Koordinaten um 2⁵⁰ ist der Abstand zwischen zwei darstellbaren Zahlen bereits
512 — die Punktkoordinate verschwindet im Rundungsfehler, und die „exakte" Rechnung wäre exakt
falsch. Richtig ist BigInt(a.x) - BigInt(d.x): erst umwandeln, dann rechnen.
Der erste Graph hat nichts gemessen. Er trug die Fehlerquote des schnellen Weges über dem Abstand vom gemeinsamen Kreis auf, in Rasterschritten — und fiel zwischen dem ersten und zweiten Messpunkt von 46 % auf null. Der Grund ist interessanter als der Fehler: Auf ganzen Koordinaten ist die gefährliche Zone gar nicht stufenlos erreichbar. Ein einziger Rasterschritt neben dem Kreis liegt schon bei 10⁻⁷, der Rundungsfehler beginnt aber erst bei 10⁻¹⁶. Dazwischen liegt nichts. Erreicht wird die Zone nur durch echte Entartung — wenn die Punkte wirklich auf einem Kreis liegen. Der Graph zeigt jetzt genau das: die Verteilung der Knappheit für drei Arten von Eingaben, mit den beiden Grenzen daneben.
Eine Prüfung, die nichts fordert, ist keine. Die Zeile „die Schranke war nie zu klein" meldete zuerst stolz 0 Abgaben an BigInt — sie hatte also nie geprüft, was sie prüfen sollte. Erst mit Punkten, die exakt auf einem gemeinsamen Kreis liegen (Radius 519 350, ein Vielfaches von 5525 = 5²·13·17 — solche Zahlen haben viele Darstellungen als Summe zweier Quadrate), wird die Schranke wirklich gefordert: 3 290 Abgaben, und in keinem der übrigen Fälle ein falsches Vorzeichen.
Was das Blatt nicht kann: keine gewichteten Zellen (Laguerre/Power-Diagramme), keine drei Dimensionen, keine Zellen auf der Kugel, kein Kantenumbau bei Bewegung (jeder Zug baut das Netz neu — bei 400 Kernen sind das ein paar Millisekunden, bei 40 000 wäre es keine Lösung mehr), keine beschränkte Triangulierung mit vorgegebenen Kanten und keine Mesh-Verfeinerung nach Ruppert.
Eine einzelne HTML-Datei. Kein Build, keine Bibliothek, nichts verlässt den Browser.
Einfügeverfahren nach Bowyer-Watson, Zellen als Durchschnitt von Halbebenen (also unabhängig vom
Netz gebaut), konvexe Hülle nach Andrew als Gegenprobe, Aufzählung aller Netze über den
Tauschgraphen, exakte Prädikate über BigInt mit Fehlerschranke davor, Canvas 2D, hell und dunkel.
Alle Blätter nach Feld geordnet, jedes mit eigenem Repo: ssims437.github.io
MIT