Mam zestaw S punktów (2D: zdefiniowany przez x i y) i chcę znaleźć P, najmniejszy (czyli: z najmniejszą liczbą punktów) wielokąt obejmujący wszystkie punkty zestaw, P jest uporządkowanym podzbiorem S.Wielokąt obejmujący zbiór punktów
Czy są jakieś znane algorytmy do obliczenia tego? (Mój brak kultury w tej dziedzinie jest zadziwiająca ...)
Dzięki za pomoc
Istnieje wiele algorytmów do tego problemu. Nazywa się "minimum bounding box". Znajdziesz tu również rozwiązania szukające "convex hull", zwłaszcza here.
Jednym ze sposobów jest znalezienie lewego skrajnego punktu, a następnie powtórzenie, aby wyszukać punkt, w którym wszystkie inne punkty znajdują się po prawej stronie linii p (n-1) p (n).
Dziękuję, to było dokładnie to, czego szukałem. Pisząc "jarvis march java" lub "quick hull java" na google, znalazłem nawet implanty Java. –
"Minimalne pole ograniczające" to ... pole. Nie ogólny wielokąt. Pozostałe linki mogą być dobre. –
Nie jestem pewien, co ma do czynienia z "minimalnym ograniczeniem", biorąc pod uwagę, że P musi być podzbiorem S. – AnT
Prawdopodobnie oznacza to, że chcesz najmniejszy obszar, którym jest wypukły kadłub.
Jeśli naprawdę potrzebujesz mniejszej liczby punktów, możesz po prostu utworzyć trójkąt z super dużymi pozycjami wierzchołków, tak aby wszystkie twoje punkty były zamknięte.
Punkty P w twoim wielkim trójkącie nie będą podzbiorem S, co jest jednym z wymagań. –
@DanielDaranas W jaki sposób uzyskać wierzchołki tego super dużego trójkąta? – Dinesh
Oto proste rozwiązanie ...
Rozpocznij z dowolnych trzech punktów, tworząc trójkąt. Dodaj każdy dodatkowy punkt do wielokąta, wykonując następującą operację:
Podziel krawędzie na dwie ciągłe ścieżki, gdzie na jednej ścieżce linia każdej krawędzi oddziela punkt, który ma zostać dodany od reszty wielokąta (nazwijmy to "ścieżka oddzielania"), a na drugiej ścieżce linia każdej krawędzi ma punkt po tej samej stronie, co wielokąt.
(Uwaga: tak długo, jak kształt pozostaje wypukły, który musi te dwie ścieżki będą ciągłe i tworzą całą kształt)
Jeżeli oddzielenie ścieżka ma krawędzie, punkt znajduje się wewnątrz wielokąta i należy zignorować, w przeciwnym razie usunąć ścieżkę oddzielającą od wielokąta. Zastąp go dwoma segmentami, łącząc każdy punkt końcowy ścieżki oddzielającej z nowym punktem.
Ta-da! :)
Oto dobrym źródłem informacji na algorytmach kadłuba wypukłych: The Convex Hull of a 2D Point Set or Polygon (by Dan Sunday)
cześć, muszę wdrożyć taką samą funkcjonalność w mojej aplikacji. czy mógłbyś udostępnić mi algorytm? –
Użyłem QuickHull. Odniesienia tutaj: https://en.wikipedia.org/wiki/Quickhull –