Bei einer gegebenen Menge von Punkten in der Ebene wird ein Begriff der Alpha-Form für eine gegebene positive Zahl Alpha definiert, indem die Delaunay-Triangulation ermittelt und alle Dreiecke gelöscht werden, bei denen mindestens eine Kante länger als Alpha ist. Hier ist ein Beispiel mit d3:

http://bl.ocks.org/gka/1552725

Das Problem ist, dass bei Tausenden von Punkten das einfache Zeichnen aller inneren Dreiecke für eine interaktive Visualisierung zu langsam ist. Daher möchte ich nur die umgebenden Polygone finden. Das ist nicht so einfach, denn wie Sie an diesem Beispiel sehen können, gibt es manchmal zwei solcher Polygone.

Nehmen wir zur Vereinfachung an, es wurde ein Clustering durchgeführt, so dass für jede Triangulation ein eindeutiges Begrenzungspolygon garantiert ist. Was ist der beste Weg, um dieses begrenzende Polygon zu finden? Insbesondere müssen die Kanten konsistent geordnet werden und es muss die Möglichkeit von "Löchern" bestehen (denken Sie an eine Torus- oder Donutform - dies ist in GeoJSON ausdrückbar).