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:

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

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

1. Jeśli A jest kwadratem, a m wynosi 3, to B będzie trójkątem o najmniejszym polu powierzchni zawierającym A.
2. 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.

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.

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.

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.