Bei einer großen Menge von Scheitelpunkten in einem nicht konvexen Polygon, wie kann ich die Kanten finden?

Question

Ich habe eine Reihe von Scheitelpunkten (genannt A) und ich möchte alle Grenzscheitelpunkte so finden, dass diese Scheitelpunktscheitelgruppe einen Umriss der Form darstellt.

Viele der Scheitelpunkte in A sind überflüssig, weil sie innerhalb der Form liegen, ich möchte diese Scheitelpunkte loswerden.

Meine Frage ist ähnlich wie Best Algorithm to find the edges (polygon) of vertices, aber ich brauche es für einen nicht-konvexen Polygon-Fall zu arbeiten.

EDIT: Klarstellung: Das Bild unten ist ein konkaves Polygon. Dies ist, was ich mit nicht-konvex gemeint habe. Wenn ich einen konvexen Hüllenalgorithmus darauf anwende, würde der konkave Teil des Polygons nicht erhalten bleiben (außer ich täusche mich).

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

Answer 1

Dies scheint ein heißes Thema .. scheint https://gis.stackexchange.com/questions/1200/concave-hull-definition-algorithms-and-practical-solutions

Dieses Papier, um die Besten zu sein. Duckham, M., Kulik, L., Worboys, M.F., Galton, A. (2008) Efficient generation of simple polygons for characterizing the shape of a set of points in the plane. Pattern Recognition v41, 3224-3236

Answer 2

Ihre Beschreibung ist etwas vage, aber es ist möglich, dass Sie nach dem Algorithmus suchen, um eine Convex Hull einer Menge von Punkten zu konstruieren. Einfach gesagt, die konvexe Hülle ist die Form, die man bekommt, wenn man ein Gummiband um alle Ecken legt.
einen konvexen Rumpf Algorithmus in 2D zu schreiben ist nicht sehr schwierig, und es gibt einige Bibliotheken, die es tun, wie qhull

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

Answer 3

Dies ist eine alte, vielleicht aufgegeben Frage, aber es hat mich darüber nachdenken. Sie suchen nicht nach einer konvexen Hülle, sondern möchten die Polygonform beibehalten, sondern nur Punkte entfernen, die zwischen "Kanten" entlang einer Linie liegen.

Die Lösung könnte sein, durch benachbarte Punkte zu treten und die lineare Steigung der ersten und zweiten zu berechnen, dann diesen Steigungswert zu speichern, die Steigung der zweiten und dritten zu berechnen, wenn die Steigung von pt1-pt2 gleich ist von pt2-pt3 ist dann pt2 redundant beim bilden der linie und kann somit entfernt werden. Machen Sie weiter, bis Sie wieder bei Punkt 1 sind.

Dies würde sicherstellen, dass Ihre konkave Form beibehalten wird, aber irrelevante Extrapunkte entfernt werden.