Outline kreślenia algorytm

Question

Dostałem tego zadania przez moją żonę, więc priorytetem :-)

Mam zbiór punktów (właściwie Northings & Eastings, ale to naprawdę nie ma znaczenia). Chcę wziąć te punkty i stworzyć zestaw wektorów, które reprezentują kontur, więc mogę spiskować na Google Earth.

Tak, coś takiego:

#      # 
      #    #  # 
#    # # 
     # # 

      # 

Dają:

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

Możliwym rozwiązaniem wymyśliłem, to aby obliczyć wektory pomiędzy każdym punkcie, a następnie wyrzucić każdy wektor, który jest zakrywana przez inny wektor. Nie zaimplementowałem tego jeszcze (nie jestem pewien jak), ale zastanawiałem się, czy są inne sposoby.

Algorytm musi być uruchamiany tylko kilka razy, więc jeśli zajmie to godzinę na przebieg i występy pamięci RAM, nie stanowi to problemu.

Answer 1

Formułowanie wielokątów kandydujących

Wygląda na to co szukasz wielokąta takie, że

• wszystkie jego wierzchołki są w punkcie ustawić
• zawiera każdy punkt w swoim punkcie zestaw

Definiuje to możliwy zestaw wielokątów kandydujących w odniesieniu do Twojego zestawu punktów.

Wypukły kadłub?

Jedną z funkcji celu może być "Wśród tych wielokątów wybierz tę z minimalną liczbą wierzchołków". To byłby wypukły kadłub twojego zestawu punktów. Inne odpowiedzi dotyczą tego podejścia, więc nie powiem nic więcej na ten temat.

Coś więcej ...

Ale to nie jedyna funkcja celu można wybrać. Na przykład można zamiast tego uzyskać kompromis między mniejszymi wierzchołkami, mniejszą powierzchnią całkowitą i mniej ostrymi kątami w wierzchołkach. Nie znam żadnych nazwanych algorytmów dla tego problemu, ale zdecydowanie jest interesujący.

Jednym z podejść może być rozpoczęcie od znalezienia wypukłego kadłuba, a następnie "wciągnięcie" krawędzi do wewnętrznych wierzchołków w miejscach, w których koszt dodatkowego wierzchołka jest przeważony z korzyścią posiadania mniejszej całkowitej powierzchni.

na przykład następująco:

staną się to ciągnąc w krawędzi wzdłuż górnej:

Drugi wielokąta może być bardziej „naturalny” pasuje do zestawu punktów, mimo że jest to wypukły kadłub zestawu punktów.

Answer 2

Prawdopodobnie szukasz kadłuba wypukłego z punktów; istnieje variety of algorithms dla znalezienia tego.

Answer 3

Here jest biblioteką do znalezienia się na wypukłej od code.google.com

Here jest biblioteką github za to samo, ale przy użyciu Jarvis mecz wypukłej Algorithm.

Mam nadzieję, że pomogą!