Ich versuche, die durchschnittliche Zellengröße auf die folgende Menge von Punkten zu berechnen, wie auf dem Bild zu sehen: 
. Das Bild wurde mit gnuplot erzeugt:Computing durchschnittliche Rastergröße
Die Punkte sind fast auf einem rechteckigen Raster ausgerichtet, aber nicht ganz. Es scheint eine Verzerrung (Jitter?) Von etwa 10-15% entlang von X oder Y zu geben. Wie würde man effizient eine richtige Partition in Kacheln berechnen, so dass nur ein Punkt pro Kachel ausgedrückt würde (Fliese, Fliesen). Ich verwende das Wort virtuell, da die 10-15% -Bias einen Punkt in einer anderen benachbarten Kachel verschoben haben kann.
nur als Referenz, habe ich manuell sortiert (hoffentlich korrekt) und extrahiert die ersten 10 Punkte:
-133920,33480
-132480,33476
-131044,33472
-129602,33467
-128162,33463
-139679,34576
-138239,34572
-136799,34568
-135359,34564
-133925,34562
Nur zur Klarstellung, eine gültige Fliese gemäß der obigen Beschreibung würde (1435,1060), aber ich bin wirklich auf der Suche nach einem schnellen automatisierten Weg.
'1. Finden Sie die Delaunay-Triangulation. 2. Entferne die diagonalen Linien. "Was bleibt, ist im Wesentlichen das, was du willst oder zumindest ziemlich helfend sein wirst. Nimmt O (N log N). – Nuclearman
Welche diagonalen Linien? – NaCl
Die Triangulation eines ungefähren Gitters erzeugt Linien, die ungefähr horizontal, vertikal und diagonal sind. Die horizontalen und vertikalen sind in diesem Fall eindeutig nützlich, aber die diagonalen sind wahrscheinlich nicht und werden daher am besten entfernt. Das Ergebnis ist ein Gitterdiagramm, mit dem Sie den nächstliegenden Punkt direkt nach links, rechts, oben oder unten an einem bestimmten Punkt finden können. Diese Datenstruktur sollte ausreichen, um alles zu tun, was in O (N) benötigt wird. Zum Beispiel können Sie alle Punkte in einer Spalte finden, indem Sie von einem Punkt oder einer Reihe aus nach links oder rechts gehen. – Nuclearman