Pytanie Algorytm kreślenia konturu


Zadanie to dostałam od mojej żony, więc to najwyższy priorytet :-)

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

A więc coś takiego:

  #                       #
           #             #       #
#             #    #
      #   #

            #

Czy dałbym:

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

Możliwym rozwiązaniem, które wymyśliłem, jest obliczenie wektorów między każdym punktem i odrzucenie każdego wektora, który nakłada się na 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 zajmuje godzinę na przebieg i występy pamięci RAM, nie stanowi to problemu.


11
2017-07-03 16:18


pochodzenie


Dobre pytanie. Możesz uzyskać lepszą odpowiedź programmers.stackexchange.com lub math.stackexchange.com - Fogmeister
Dlaczego ten kształt? Dlaczego nie narysować wypukły kadłub punktów? - Chowlett
@Chowlett właśnie sprawiają, że odpowiedź; miał właśnie wspomnieć, że istnieje kilka "solidnych" kształtów, które można wykonać za pomocą tych punktów. - David Ellis
Możesz ewentualnie wyszukać algorytm wypukłego kadłuba community.topcoder.com/... - sasha sami


Odpowiedzi:


Formułowanie potencjalnych wielokątów

Wygląda na to, że szukasz takiego wielokąta

  • wszystkie jego wierzchołki znajdują się w twoim zestawie punktów
  • zawiera każdy punkt w twoim zestawie punktów

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 nie jest to jedyna funkcja celu, jaką możesz wybrać. Na przykład możesz zamiast tego mieć kompromis pomiędzy mniejszą liczbą wierzchołków, 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:

enter image description here

Stanie się tym, ciągnąc za krawędź wzdłuż wierzchołka:

enter image description here

Ten drugi wielokąt może być bardziej "naturalnym" dopasowaniem do zestawu punktów, nawet jeśli tak jest nie wypukły kadłub ustawionego punktu.


7
2017-07-03 16:36



Dla zestawu punktów 2D można opisać "wklęsły" kadłub za pomocą kształtów alfa. - Cyril
@Xerto Nice, nauczyłem się czegoś nowego. :) OP powinien zdecydowanie rzucić okiem na te. - Timothy Shields


Prawdopodobnie szukasz Kadłubu Wypukłego z punktów; istnieją różnorodność algorytmów za znalezienie tego.


2
2017-07-03 16:28





Tutaj to biblioteka do wyszukiwania wypukłego kadłuba z code.google.com

Tutaj jest biblioteką Github dla tej samej rzeczy, ale z użyciem Algorytm kadłubowego wypukłości Jarvisa.

Mam nadzieję, że pomagają!


0
2017-07-03 16:37