Umriss Plotten Algorithmus

Question

Ich habe diese Aufgabe von meiner Frau gegeben worden ist, so ist es höchste Priorität :-)

ich eine Sammlung von Punkten (eigentlich Koordinaten X & Ostwerte, aber es ist nicht wirklich wichtig). Ich möchte diese Punkte nehmen und eine Reihe von Vektoren erstellen, die den Umriss darstellen, sodass ich auf Google Earth plotten kann.

Also, so etwas wie:

#      # 
      #    #  # 
#    # # 
     # # 

      # 

würde:

#-----------------------#-- 
/       \ --# 
#     #------------/ 
\-----#  /
     \ /
      # 

Eine mögliche Lösung kam ich mit, ist Vektoren zwischen jedem Punkt zu berechnen, und verwerfen jeden Vektor, der durch überlappt wird ein anderer Vektor. Ich habe das noch nicht umgesetzt (nicht wirklich sicher wie), aber ich habe mich gefragt, ob es andere Wege gibt.

Der Algorithmus muss nur ein paar Mal ausgeführt werden, also wenn es eine Stunde pro Lauf und Gigs RAM ist, ist das kein Problem.

Answer 1

Formulierung von Kandidaten Polygonen

Es scheint so, was Sie für ein Polygon, so dass

• alle seine Eckpunkte in Ihrem Punkt suchen gesetzt
• es jeden Punkt in Ihrem Punkt enthält Set

Dies definiert eine machbare Menge von Kandidaten Polygone in Bezug auf Ihre Punktmenge.

Konvexe Hülle?

Eine Zielfunktion könnte lauten: "Wählen Sie unter diesen Polygonen das mit der kleinsten Anzahl an Scheitelpunkten aus." Das wäre die konvexe Hülle Ihres Punktsatzes. Andere Antworten sprechen diesen Ansatz an, daher werde ich nichts mehr dazu sagen.

Etwas mehr ...

Aber das ist nicht die einzige objektive Funktion Sie wählen könnten. Sie könnten beispielsweise einen Kompromiss zwischen weniger Eckpunkten, weniger Gesamtfläche und weniger scharfen Winkeln an Eckpunkten haben. Ich kenne keine existierenden benannten Algorithmen für dieses Problem, aber es ist definitiv eine interessante. Ein Ansatz könnte darin bestehen, zunächst die konvexe Hülle zu finden und dann an den Stellen, an denen die Kosten des zusätzlichen Eckpunkts durch den Vorteil einer geringeren Gesamtfläche aufgewogen werden, Kanten an innere Eckpunkte "einzuziehen".

Zum Beispiel diese:

dies werden würde, indem sie entlang der Oberseite im Rand ziehen:

Dieses zweite Polygon könnte ein "natürlicher" sein fit für die Punktmenge, auch wenn es nicht die konvexe Hülle der Punktmenge ist.

Answer 2

Sie suchen wahrscheinlich nach dem Convex Hull der Punkte; Es gibt eine variety of algorithms für das Finden.

Answer 3

Here ist eine Bibliothek für die Suche aus der konvexen Hülle aus code.google.com

Here eine Github-Bibliothek für die gleiche Sache, aber Jarvis Spiel Convex Hull Algorithmus verwenden.

Hoffnung sie helfen!