Algorithmus zum Finden von Polygonen, die Punkte einschließen

8

Ich versuche einen Algorithmus zu finden, der die kleinstmöglichen Polygone bestimmen kann, um eine Reihe von Punkten abzudecken.

Ich weiß, wie man die konvexe Hülle um alle Punkte herum bringt, aber sagen wir, dass sich die Punkte auf verschiedenen Inseln befinden. Ist es möglich festzustellen, dass zwischen verschiedenen Gruppen eine Lücke besteht, und für jede Gruppe separate Polygone zu erhalten?

algorithm polygon convex-hull clustering concave-hull jjrdk
quelle
Die Antwort ist, dass nur ein Polygon benötigt wird; seine Fläche kann beliebig nahe Null sein; und es ist niemals einzigartig. (Ein Weg, um eine Lösung zu finden: Es gibt Punkte in der Ebene, von denen aus jeder Punkt in der ursprünglichen Menge sichtbar ist. Verfolgen Sie eine nicht sich selbst schneidende Route von diesem Punkt nach außen zu jedem der angegebenen Punkte und bilden Sie einen Stern mit extrem enge Strahlen.) Dies zeigt, dass das Problem unvollständig angegeben ist: Es bedarf einer klareren und gründlicheren Darstellung des analytischen Ziels.
whuber

Antworten:

9

Es hört sich so an, als ob Sie zuerst einen Clustering-Algorithmus benötigen (z. B. K-bedeutet Clustering), gefolgt von einem Rumpf (konvexer Rumpf, aber ein konkaver Rumpf hat möglicherweise eine kleinere Fläche, ist jedoch schwieriger zu implementieren).


quelle
Siehe auch: en.wikipedia.org/wiki/Hierarchical_clustering
Juli
3

Das "Clustr" -Tool, das wir (d) bei Flickr verwenden, um die aus Fotos mit Geotags abgeleiteten Shapefiles zu generieren, kann von Nutzen sein:

https://github.com/straup/Clustr

(Stackexchange verhindert, dass ich mehr als 2 Links in diesen Beitrag einfügen kann. Wenn Sie nach "der Form von Alpha" suchen, finden Sie den Blog-Beitrag code.flickr, den wir bei der Ankündigung der Shapefiles erstellt haben.)

Es wurde entwickelt, um die Kontur aus einer sich ständig ändernden Punktetasche (auch Fotos genannt) zu erzeugen. Die eigentlichen mathematischen Bits sind hier:

http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Alpha_shapes_3/Chapter_main.html

Clustr hat einige bekannte Fehler, funktioniert aber meistens ...

user2016
quelle
2

Aus Datenbanksicht klingt es so, als ob Sie die Punkte auf den Ilands gruppieren und für jede Gruppe eine konvexe Hülle erstellen möchten.

in postgis würde es ungefähr so ​​aussehen:

SELECT ST_Convexhull(ST_Collect(p.the_geom))
FROM pointtable p INNER JOIN islands i ON ST_Intersects(p.the_geom,i.the_geom)
GROUP BY i.id;

/ Nicklas

Nicklas Avén
quelle
Ich glaube nicht, dass ich in meiner ersten Frage klar war. Der Punkt war, dass ich nicht weiß, wo sich die Punkte befinden, aber die befinden sich an unterschiedlichen Orten. Daher brauchte ich einen Algorithmus, um Cluster dynamisch zu erstellen, in denen sich die Punkte befinden, und sie nicht in definierte Bereiche zu verschieben. Ich habe den k-means-Clustering-Algorithmus geändert, um den Datensatz nach Cluster-Schwerpunkten und dann nach Cluster zu durchsuchen.
jjrdk
Sie meinen, Sie wissen nicht, wo die Inseln sind? Sie haben keine Vektordarstellung der Inseln, ok. Aber was meinst du mit "nicht bewegen". Ich habe nicht vorgeschlagen, etwas zu bewegen? ..
Nicklas Avén
Ich weiß nicht, wo sich die Gruppen (Inseln) befinden werden, es hängt von der Position der Punkte ab. Ich versuche also, das kleinste Polygon zu finden, das die Punktpositionen einschließt. Mit Verschieben meinte ich Clustering-Punkte in einer definierten Anzahl von Clustern wie beim k-means-Clustering.
JJrdk
1

arcpy.AggregatePoints_cartography (pntGeometryList, outAppendFeatureClass, buffer_radius)

Wenn pntGeometryList Ihre Liste von Punkten ist, outAppendFeatureClass die Feature-Klasse, die die Aggregation erstellt, und buffer_radius, die die Verknüpfungen zwischen jedem nach außen gerichteten Punkt bestimmt.

Behaart
quelle
Entschuldigung, ich habe gerade den Rest Ihrer Frage erhalten, die ich nicht gelesen habe.
Haarige
Wie sammeln Sie Ihre Punkte?
Haarige
1

Zuerst dachte ich, dass Dans Vorschlag für k-means Sinn macht, aber nachdem ich mir die Ergebnisse der Mausdatensätze auf der Wikipedia-Seite für k-means angesehen habe , sieht es so aus, als ob das Clustering von Expectation-Maximization näher an dem liegt, was Sie wollen.

Geben Sie hier die Bildbeschreibung ein

Kirk Kuykendall
quelle
1
Vielen Dank für Ihre Antwort. Ich habe tatsächlich eine modifizierte Version des k-means-Algorithmus erstellt, der sich nach maximaler Entfernung gruppiert. Ich habe hier darüber gebloggt
reimers.dk/blogs/jacob_reimers_weblog/archive/2011/03/08/…
Sieht großartig aus. Ich denke, EM wäre sicher schwieriger zu implementieren. Es wäre interessant zu sehen, ob Ihr Code in Silverlight funktioniert, möglicherweise unter Verwendung dieser TPL .
Kirk Kuykendall