Wielokąt w ramach problemu generalizacji wielokąta

Chciałbym przeprosić wszystkie poniższe posty. Wybrałem niewłaściwe forum, aby pierwotnie to opublikować. Jednak zamiast uczynić to kompletnym marnotrawstwem, przerobiłem pytanie, aby było prawdziwym problemem „teoretycznej informatyki”.

Problem: Utwórz algorytm, który pobiera zestaw n uporządkowanych punktów na płaszczyźnie 2D, które tworzą kontur prostego wielokąta A, który może, ale nie musi, być wklęsły i tworzy nowy wielokąt B z m punktami, które:

wszystkie punkty w A są zawarte w B
3 <= m <n
B jest wielokątem w zestawie wszystkich Bs o najmniejszym obszarze
B musi być prostym wielokątem (tzn. Bez skrzyżowań własnych).
Dane wejściowe do algorytmu to wielokąt A i „m”.
Dozwolona jest koincydencja segmentów w B z segmentami w A.

Niektóre przykładowe dane wejściowe i oczekiwane wyniki:

Jeśli A jest kwadratem, a m wynosi 3, to B będzie trójkątem o najmniejszym polu powierzchni zawierającym A.
Jeśli A jest sześciokątem, a m wynosi 4, to B będzie czworobokiem o najmniejszym polu powierzchni zawierającym A.

Powodzenia dla wszystkich, którzy próbują rozwiązać ten problem. Mogę obiecać, że będzie to bardzo trudne, szczególnie teraz, gdy rozwiązanie musi być optymalne.

ds.algorithms cg.comp-geom polygon

— Thirlan
źródło

@Joe: Nieprawda: jeśli A jest kwadratem, Thirian prosi o trójkąt o minimalnej powierzchni zawierający A. Z drugiej strony, jeśli A jest trójkątem (

n = 3

$n=3$ ), wówczas rzeczywiście nie ma ważnego rozwiązania.

— Jeffε

Chyba dodaj 17 do mojego pierwszego komentarza. Dlaczego 20?

— Jeffε

Czy FFT nie jest niskim progiem dla „skomplikowanych”?

— Sasho Nikolov

Nie sądzę, że to całkowicie prawda, że problem wcale się nie zmienia, jeśli (powiedzmy) ustawiłeś m = 3. Problem polega na tym, że możesz wymagać wykładniczego czasu wm, i to dobrze, jeśli m jest ustalone na pewną liczbę, ale nie jest dobrze, jeśli m jest częścią wejścia.

— Suresh Venkat,

„wszyscy wiedzą, na czym polega problem” nie jest prawdą. Pytamy, ponieważ nieokreślone wybory mają znaczenie.

— Suresh Venkat,

Odpowiedzi:

Nie wiem, jak wyglądają twoje wielokąty, ale być może wystarczy uproszczona wersja algorytmu Ramera – Douglasa – Peuckera :

dla każdej wypukłej części obliczyć powierzchnię $A_j$ z trójkątów $P_i P_{i+1} P_{i+2}$ utworzone przez trzy kolejne punkty;
dla każdej wklęsłej części obliczyć powierzchnię $B_k$ z dwóch trójkątów $P_i P'_i P_{i+1}$ i $P_{i+1} P'_{i+2} P_{i+2}$ utworzony przez przedłużenie dwóch punktów $P_i, P_{i+2}$ i środkowy punkt $P_{i+1}$
Oblicz $min\{A_j,B_k\}$ i usuń odpowiedni punkt (i przesuń punkty, jeśli operacja jest wykonywana na części wklęsłej);
powtarzaj dopóki $n-m$ punkty zostały usunięte.

wprowadź opis zdjęcia tutaj
Granica wielokąta ( $A_j$ zielone trójkąty, $B_k$ czerwone trójkąty). Po prawej granica po wyeliminowaniu dwóch punktów.

W przypadku bardziej złożonych algorytmów można wyszukiwać „ techniki generalizacji wieloboków ”, chociaż pierwszy warunek (punkty w A są zawarte w B) oznacza pewne dodatkowe operacje skalowania.

— Marzio De Biasi
źródło

@Suresh: Jestem prawie pewien, że obecne 4 głosy poparcia dotyczą przejrzystości, a nie (prawie trywialnego) algorytmu :)

— Marzio De Biasi

Ma to ten sam problem, co algorytmy Ramera-Douglasa-Peuckera: Wyjście nie jest gwarantowane jako prosty wielokąt!

— Jeffε

@Jeffe: masz rację, ale (dalekie od optymalnego, jeśli wielokąt jest złożony) można uniknąć uproszczeń prowadzących do konfliktu . Na koniec, jeśli istnieją inne punkty, które należy usunąć, ale nie można uniknąć prostego wielokąta, użyj metody rozwiązywania konfliktów (na przykład oblicz punkty przecięcia i całkowicie odrzuć „dziury”). Chciałbym jednak zobaczyć prawdziwy przykład z PO.

— Marzio De Biasi,

@MarzioDeBiasi To może działać. Ale może nie. Myślę, że każde opisane przez ciebie uproszczenie może spowodować samo-skrzyżowanie. A „wyrzucanie pętli” może pogorszyć sytuację, a nie poprawić. Jest to prawdopodobnie dobre rozwiązanie w praktyce, ale pamiętaj, gdzie jesteśmy!

— Jeffε

Dzięki Marzio, teraz przynajmniej wiem, jak nazywają się teraz tego rodzaju problemy! Niestety rozwiązanie, które podałeś, jest tym, co (3) i (4) są w moich sugerowanych rozwiązaniach i (4) ma z tym problem. Elipsy, które są bardzo rozciągnięte, a zatem mają ostre końce o kątach około 30 stopni i mniejszych, z łatwością naruszą wymaganie (1).

— Thirlan

Dawno temu napisałem artykuł, w którym wyszczególniono algorytm czasu liniowego do znajdowania najmniejszego trójkąta powierzchni zawierającego zestaw punktów (lub wielokąta):

J. O'Rourke, Alok Aggarwal, Sanjeev Maddila, Michael Baldwin, „Optymalny algorytm znajdowania minimalnych trójkątów otaczających”, J. Al Algorytmy , 1986, 7 : 258--269. Link .

Po naszej pracy nastąpił ogólny algorytm:

„Minimalna powierzchnia otaczająca wielokąty”, Alok Aggarwal, JS Chang i Chee K. Yap, The Visual Computer , Tom 1, Number 2 (1985), 112-117. Link .

Możesz użyć Google Scholar do śledzenia późniejszych artykułów, które je cytują, w celu znalezienia ulepszeń i powiązanych prac.

— Joseph O'Rourke
źródło