Bei einer große Menge von Knoten in einem nicht-konvexen Polygon, wie kann ich die Kanten finden?

Question

Ich habe eine Reihe von Eckpunkten (genannt A) und ich möchte alle die Grenze Eckpunkte, so dass dieser Grenze Eckpunkte Satz ist eine Übersicht der Form zu finden.

Viele der Scheitelpunkte in A sind redundant, da sie in der Form sind, mag ich diese Eckpunkte loswerden.

Meine Frage ist ähnlich wie besten Algorithmus, um die Kanten zu finden (Polygon) von Eckpunkten , aber ich brauche es, um Arbeit für einen nicht-konvexen Polygon Fall.

EDIT: Zur Verdeutlichung: das Bild unten ist ein konkaves Polygon. Das ist, was ich von nichtkonvexe gemeint. Wenn ich einen konvexen Hülle Algorithmus darauf laufen, wäre es nicht den konkaven Teil des Polygons bewahren. (Es sei denn, ich irre).

Ich habe eine Reihe von Eckpunkten innerhalb und an der Grenze des Polygons: [[x1, y1], [x2, y2] ...] Ich will die Menge zu reduzieren, so dass die Ecken nur die Grenze Umriss der Form sind.

Answer 1

Dies scheint ein heißes Thema zu sein .. https://gis.stackexchange.com/questions/1200/concave- Rumpf-Definition-Algorithmen-and-praktisch-Lösungen

Dieses Papier scheint der Beste zu sein. Duckham, M., Kulik, L., Worboys, MF, Galton, A. (2008 Efficient) Erzeugung von einfachen Polygonen für die Form einer Reihe von Punkten in der Ebene zu charakterisieren. Mustererkennung v41, 3224-3236

Answer 2

ist Ihre Beschreibung etwas vage, aber es ist möglich, dass Sie für den Algorithmus suchen zu konstruieren, ein Convex Hull einer Reihe von Punkten. Einfach ausgedrückt, ist die konvexe Hülle die Form, die Sie erhalten, wenn Sie um alle Scheitel ein Gummiband gelegt.
Schreiben eines konvexen Hülle Algorithmus in 2D ist nicht sehr schwierig, und es gibt einige Bibliotheken, die es tun, wie qhull

(Diese Antwort ist auch in der Frage gegeben, Sie verknüpfen, auf die ein Spezialfall der Frage zu sein scheint)

Answer 3

Dies ist eine alte, vielleicht aufgegeben Frage, aber es hat mich darüber nachgedacht habe. Sie sind nicht für eine konvexe Hülle suchen, möchten Sie die Polygone Form beizubehalten, aber nur loswerden Punkte zu bekommen, dass liegen dazwischen „Kanten“ entlang einer Linie.

könnte die Lösung, um durch benachbarte Punkte sein, und die lineare Steigung der ersten Berechnung und dem zweiten, dann wird diese Steigungswert zu speichern, Berechnen der Steigung der zweiten und der dritten, wenn die Steigung des PT1-PT2 ist gleich der PT2 PT3-dann ist pt2 redundante in die Leitung bildet und somit entfernt werden kann. Halten Sie Schleifen, bis Sie an pt1 aufzuwickeln zurück.

Dies würde sicherstellen, Ihre konkave Form gehalten wird, aber irrelevant Extrapunkte werden entfernt.

Answer 4

Der Begriff Sie suchen ist konkaver Rumpf .

Die einfachste Form des Problems nicht gut ist wie konvexe Hülle definiert, weil die konkave Polygon, dass Punkte Abdeckungen gegeben ist nicht eindeutig. Allerdings gibt es viele gute Ansätze.

Eine der einfachsten Ansatz ist, verwenden Sie den Algorithmus Geschenkverpackung, sondern alle die Punkte bei jedem Schritt Erwägen Sie nur betrachten k nearest Nachbarn des aktuellen Vertex.

Hier k ist Ihr Hyper Parameter einzustellen. Wenn k zu hoch erhalten Sie die konvexe Hülle. Wenn k zu niedrig ist, dass Sie das resultierende Polygon hat viele Höhlungen.

---

Hier sind einige relevante Links:

• https://github.com/mapbox/concaveman
• https: //gis.stackexchange .com / Fragen / 1200 / was-sind-Definition-Algorithmen-und-praktisch-Lösungen-für-konkav-Rumpf
• Konkav Rumpf: Ein k-nächste Nachbarn Ansatz für die Berechnung der Region durch eine Reihe von Punkten belegt ( link )