Algorytmy geometryczne - obwiednia

Witam,

To moja pierwsza prośba do Was, od kiedy mam konto na tym forum. Proszę o pomoc, gdyż sam utknąłem i nie wiem, co dalej zrobić. Mam nadzieję, że nie zostanę wyzwany od n00bów, wyśmiany, zbanowany, etc (asdf - proszę o litość ;>)... ;)

Otóż... muszę rozwiązać pewne wydumane zadanie algorytmiczne i próbuję znaleźć punkt zaczepienia - mam kilka potencjalnych pomysłów, jakby można było podejść do problemu, lecz żaden nie wydaje mi się w pełni odpowiedni. Z góry dziękuję za wszelkie konstruktywne uwagi oraz wskazówki :)

Treść zadania przytoczę cytując: "Dany jest zbiór prostokątów na płaszczyźnie, których boki są równoległe do osi układu współrzędnych, a współrzędne wierzchołków są całkowite. Prostokąty mogą się ze sobą stykać, na siebie nachodzić, a nawet się zawierać. Takie prostokąty tworzą większe figury. Opracować algorytm liczący sumaryczny obwód powstałych w ten sposób figur." Uff... koniec.

Moje próby podejścia do problemu:

• omiatanie/zamiatanie/miotełkowanie: próbujemy znaleźć jakąś zależność w położeniu punktów (wierzchołków tychże prostokątów) na kolejnych prostych powiedzmy pionowych (kolejne proste np. x=1, 2, 3...). Wydaje mi się to dość trudne, gdyż mogą występować - jak ja to nazywam - "dziury" w tych obszarach tworzonych przez prostokąty i nie mam pomysłu, jakby można było je odróżniać w tej metodzie od skrajnego brzegu figury.

• "szczwany" algorytm wycinania (w miarę dodawania nowych prostokątów do listy) tych części prostokątów, które zawierają się w dotychczas dodanych (w istniejącym już obszarze) i modyfikowanie obszaru o to, co "wystaje" - problem z tym, że tracimy wszelkie informacje, które w przyszłości mogłyby spowodować utworzenie "dziury".

• algorytm przechodzenia (ja go sobie tak nazwałem) - mamy już dodane wszystkie prostokąty do płaszczyzny i w miarę dodawania ich wyznaczaliśmy sobie powiedzmy... skrajny dolny lewy punkt. Teraz, zaczynając od tego punktu, idziemy sobie bokami prostokątów (w zależności od tego, w którym kierunku idziemy, to możemy - tak mi się wydaje - określić, czy w momencie przecięcia się boków (tam też możemy np. dodawać nowe punkty do płaszczyzny w miarę dodawania kolejnych prostokątów) iść do góry, czy skręcić, itd). No więc idziemy sobie, idziemy i w miarę tego, jak chodzimy od punktu, do punktu, to zliczamy sobie sumaryczną długość obwiedni a gdy dojdziemy do początku, to bierzemy kolejny, nieodwiedzony, punkt z jakiegoś stosu wszystkich punktów i zaczynamy zabawę od nowa. Wydaje mi się, że to rozwiązanie obejmie także te "dziury", które ewentualnie powstaną.

Innych, w miarę rozsądnych, pomysłów niestety nie mam. Proszę o uwagi, co do podanych sposobów oraz o pomoc w zdecydowaniu się na jakiś z algorytmów. Jeśli macie pomysł na jakiś lepszy, to też z chęcią wysłucham.

Chciałbym zaznaczyć, że NIE ZALEŻY mi na tym, byście za mnie rozwiązali problem, lecz proszę o pomoc w doborze algorytmu, bo brak mi doświadczenia i nie wiem, który z nich mógłby się nadawać i pozwalałby rozwiązać problem w sensownym czasie.

Z góry dziękuję :) I przepraszam za przydługi post ;)

Ja mam pomysł taki:

1. sumaryczny obwód dzielisz na dwie części: horyzontalną (poziome boki) i wertykalną (pionowe boki).
2. każdy bok dzielisz na jednostkowe odcinki, i przyporządkowujesz mu znak + lub - zależnie od tego czy jest to górna(lewa) czy dolna(prawa) cześć prostokąta.
3. zbierasz wszystkie odcinki horyzontalne o jednej współrzędnej x i sortujesz je po y. Po przesortowaniu idziesz po kolei sumując + i -. Za każdym razem gdy suma + i - jest taka sama dodajesz do obwodu 2.
4. wykonujesz to dla wszystkich dostępnych x
5. wykonujesz to samo dla boków wertykalnych i współrzędnej y
   suma wyników wertykalnych i i horyzontalnych jest twoim wynikiem.

Oczywiście można ten algorytm usprawnić, grupując współrzędne, ale ogólny zarys powinien być zrozumiały.

Nie jest dla mnie jasne co znaczy zwrot

powstałych w ten sposób figur
Chodzi o wsystkie figury powstałe przez sumowanie nierozłącznych prostokątów, czy tylko o maksymalne takie figury?
Np. dla zbioru trzech prostokatów 200X100

odpowiedź winna wynosić 1500 czy 1500+900+1200+600+600+600?

Chodzi o maksymalne figury (dla przytoczonego przykładu odpowiedź wynosi 1500). Ale w momencie, gdy pojawi się kilka rozłącznych obszarów utworzonych z takich ponakładanych prostokątów, to ich obwody (+ obwodu ewentualnych dziur powstałych wewnątrz tych obszarów) sumujemy, a ostatecznym wynikiem jest suma wszystkich obwodów.

@MarekR22: Dziękuję Ci za podsunięcie "świeżej" myśli. Próbuję właśnie zrozumieć ten algorytm, który napisałeś (to znaczy zrozumieć, czemu on będzie działał, bo nie jest to dla mnie na pierwszy rzut oka oczywiste :) Ale wydaje się, że może się on okazać bardzo przydatny :) ).

To jest pokazanie różnych możliwych sytuacji ułożenia prostokątów. Algorytm MarkaR22 nie uwzględnia (przynajmniej o ile go dobrze zrozumiałem) sytuacji z dziurami (rozpatruję tylko przypadek horyzontalny) - przykład czerwony - bo dla tego przypadku dodane tu zostanie "2" a nie "4". Dla przypadku niebieskiego oraz zielonego dziala ten algorytm poprawnie. Wydaje mi sie rowniez, ze bedzie algorytm dzialal dla przypadku fioletowego (rozowego ?) - bo tam "+" i "-" pokrywaja sie, ale w praktyce nadal istnieja jako oddzielne byty.

Prostokat o kolorze oliwkowym pokazuje, o co chodzi z rozlacznymi obszarami, ktorych obwody nalezy zsumowac.

Czy jesteś pewien, że należy uwzględniać dziury? Pytam, bo zadanie z dziurami jest dużo trudniejsze, i to z dwóch powodów:
Jeśli mamy zbiór prostokątów, którego suma teoriomnogościowa jest spójna (tworzy figurę), to łatwo
rozstrzygnąć czy po dodaniu kolejnego prostokąta suma będzie nadal spójna. Łatwo zatem podzielić wszystkie prostokąty na podzbiory ze spójnymi sumami. Ponadto obwód zewnętrzny figury liczy się łatwo, jest on bowiem równy obwodowi opisanego prostokąta. Wystarczy zatem wyznaczyć skrajne wierzchołki - nie trzeba wyznaczać punktów przecięcia.
Jeśli uwzględniamy dziury, to po pierwsze trzeba sprawdzić czy one są, po drugie nie ma (IMHO) prostego sposobu policzenia obwodu dziury.

Mój algorytm uwzględnia dziury i to bardzo dobrze. Napisałem, że za każdym razem gdy suma + i - jest taka sama dodajesz do obwodu 2, a jak dojdziesz do dziury to właśnie zostanie spełniony ten warunek. To tak jakby traktować boki jak nawiasy i kontrolować kiedy nawiasy są zamknięte.
No chyba, że ty chcesz tę dziurę zignorować w liczeniu obwodu. W takim wypadku będzie trudniej, bo powstaje sprzężenie pomiędzy częścią horyzontalną i wertykalną - t/z układ boków horyzontalnych ma wpływ na liczenie obwodu wertykalnego, możesz mieć dziurę niedomkniętą z jednej strony i wtedy ma być policzona do obwodu.
Skonkretyzuj chcesz policzyć tylko obwód zewnętrzny czy obwód całkowity?

@bogdans: No więc niestety dziury muszę uwzględniać. Więc przypadek z tym, że obwód spójnego obszaru jest równy obwodowi prostokąta opisującego tenże obszar niestety odpada :(

@MarekR22: Czyli ja jednak źle zrozumiałem Twoje intencje chyba. Teraz mi się wydaje, że rozumiem: chodzi Ci o to, że jak mamy sekwencję: ++--, to oznacza, że mamy prostokąt, który zawiera się w naszym (przypadki: fioletowy, niebieski i zielony), a jeśli mamy sekwencję: +-+-, to znaczy, że mamy dziurę (przypadek czerwony). Teraz dobrze rozumuję ? Bo szczerze mówiąc, jeśli bierzemy samą sumę ilościową plusów i minusów, to przypadki: czerwony, zielony, niebieski i fioletowy niczym się od siebie nie różnią - we wszystkich mamy dwa plusy i dwa minusy. I dlatego najpierw stwierdziłem, że ten algorytm by sobie nie poradził z dziurami.

@MarekR22, jeżli dobrze zrozumiałem twój algorytym, to daje nieprawidłowy wynik gdy wewnątrz dziury znajduje się kolejna figura(prostokąt) . Obwód tej wewnętrznej figury trzeba liczyć dwukrotnie. Np. poniższa figura: cztery prostokąty 5X1 oraz jeden prostokąt 1X1.

//edit, algorytm działa błędnie nawet po wyrzuceniu środkowego kwadratu, w pierwszym od lewej pionowym pasie dwukrotnie sumy '+' i '-" będą równe, zatem do obwodu dodane zostanie liczba 4, a powinna byc dodana liczba 2.

Najwyraźniej nie zrozumiałeś jak to działa. Biorąc twój przykład, weźmy jednostkowe odcinki horyzontalne pomiędzy x=0 i x=1.
idąc od dołu do góry:
dla y = 0 masz 2+ 0-
dla y = 1 masz 2+ 1-
dla y = 4 masz 3+ 1-
dla y = 4 masz 3+ 3- (do obwodu +2)
wynik +2

dla odcinków horyzontalnych pomiędzy x=2 i x=3:
dla y = 0 masz 1+ 0-
dla y = 1 masz 1+ 1- (do obwodu +2)
dla y = 2 masz 2+ 1-
dla y = 3 masz 2+ 2- (do obwodu +2)
dla y = 4 masz 3+ 2-
dla y = 5 masz 3+ 3- (do obwodu +2)
wynik +6

Jest chyba jasne, że trzeba liczyć pokrywające się odcinki jako osobne a nie jako jeden.

Nie zrozumiałem, teraz rozumiem, wycofuję zastrzeżenia.

A jak myślicie, czy jest jakiś sprytny algorytm pozwalający nie dzielić wszystkich boków na jednostkowe odcinki (bo wtedy złożoność bardzo zaczyna nam zależeć od wymiarów podanych prostokątów, a nie tylko od ich ilości), tylko na jakieś odcinki o większej długości ? Tak, jak w przykładzie bogdans'a (przy pominięciu środkowego, niebieskiego kwadratu ! - czyli to, co zamieściłem powyżej) środkowe boki prostokątów można byłoby traktować jako całość (zamiast dzielić każdy z nich na 3 odcinki o długości 1) i ostateczny wynik pomnożyć razy długość takiego segmentu (w tym wypadku 3). Segmenty wyróżniłem kolorami: jasnozielonym i fioletowym.

Osobiście zastanawiam się nad tym, że przy dodawaniu nowego prostokąta wyszukujemy po prostu punkty przecięcia prostych, do których należą boki nowego prostokąta z bokami istniejących już prostokątów i tam je dzielimy (te istniejące).

Koncepcję przedstawia obrazek poniżej: Istniejące "wcześniej" prostokąty mają kolor bordowy (maroon) (taki, jak ten w prawym górnym rogu). Dodany właśnie prostokąt jest oznaczony na jasnoczerwono. Proste, które zawierają jego boki są oznaczone czarnymi przerywanymi liniami. A odcinki, które zostają wydzielone z boków prostokątów istniejących poprzez cięcia tymi prostymi pooznaczane są przez kreskowane linie o kolorach: bordowy-inny kolor. Odcinki o tym samym kolorze mają takie same długości. Punkty przecięć (czyli de facto początki/końce nowych odcinków powstałych poprzez podzielenie istniejących boków) są oznaczone jasnozielonymi kropkami.

Po mojemu powinno działać. Można nie wyznaczać punktów przecięcia, i dzielić odcinki poziome prostymi pionowymi przechodzącymi przez wierzchołki, analogicznie dla odcinków pionowych. Takie podejście istotnie zmniejsza czas obliczenia obwodu figury złozonej z jednego prostokata o wymiarach 1 mld. x 2.mld.

Właśnie o tym mówiłem :) No tylko, żeby podzielić dany odcinek prostą, to musisz ustalić, czy ona przecina tenże odcinek oraz jeśli przecina, to w którym miejscu. Zatem w zasadzie musisz ustalić punkt przecięcia ;)

Myślicie, że hashmap'a przechowująca (np. dla odcinków poziomych) pary: współrzędna x (jako indeks) i lista odcinków rozpoczynających się na tejże współrzędnej jest wystarczająco wydajna do celu przeszukiwania odcinków pod katem sprawdzania tych przecięć (z prostymi) ?

Mówię o hashmapie, gdyż współrzędne reprezentują tu zbiór rzadki (nie mamy określonego ani zakresu minimalnego/maksymalnego dla tych współrzędnych, ani nie ma gwarancji, że będą one ułożone w miarę "blisko siebie"), więc ta struktura wydaje mi się dobra do przechowywania informacji o nich, gdyż pozwala w szybki sposób odwołać się do "kolejnego" elementu o wyższej współrzędnej (zakładając, że przechodzimy po współrzędnych w porządku rosnącym), niezależnie od tego, jaka to by nie była w rzeczywistości wartość.

A ja to widzę tak.
a) Mając zbiór wierzchołków W wyznaczyć zbiór wszystkich odcinków tworzących boki a następnie wyznaczyć wszystkie punkty przecięcia P tych odcinków, trywialne, zwłaszcza, że mamy zagwarantowaną prostopadłość.
b) Znaleźć wierzchołek najbardziej odstający (wszystko jedno, w którą stronę, to zapewni, że będzie to wierzchołek niezawarty przez inne prostokąty).
c) Poruszając się 'zasadą prawej/ lewej ręki' chodzić po krawędziach, eliminując z W i P odwiedzone wierzchołki i krawędzie przecięcia, licząc jednocześnie przebytą drogę.
d) Wyeliminować prostokąty, które się w pełni zawierają.
d) Jeśli są jeszcze wierzchołki w W powtórzyć punkty b i c.

@vixen03: No to jest to jeden z zaproponowanych przeze mnie algorytmów (tylko ja nie podałem, że można by to zrobić za pomocą "reguły lewej ręki") ;) No i jest tam pewien problem... jak wyeliminować (w efektywny sposób) prostokąty, które zawierają się w innych ? ;>

algorytm przechodzenia (ja go sobie tak nazwałem) - mamy już dodane wszystkie prostokąty do płaszczyzny i w miarę dodawania ich wyznaczaliśmy sobie powiedzmy... skrajny dolny lewy punkt. Teraz, zaczynając od tego punktu, idziemy sobie bokami prostokątów (w zależności od tego, w którym kierunku idziemy, to możemy - tak mi się wydaje - określić, czy w momencie przecięcia się boków (tam też możemy np. dodawać nowe punkty do płaszczyzny w miarę dodawania kolejnych prostokątów) iść do góry, czy skręcić, itd). No więc idziemy sobie, idziemy i w miarę tego, jak chodzimy od punktu, do punktu, to zliczamy sobie sumaryczną długość obwiedni a gdy dojdziemy do początku, to bierzemy kolejny, nieodwiedzony, punkt z jakiegoś stosu wszystkich punktów i zaczynamy zabawę od nowa. Wydaje mi się, że to rozwiązanie obejmie także te "dziury", które ewentualnie powstaną.

W zasadzie nie muszę wyznaczyć punktów przecięcia. Tworzę posortowaną kolekcję współrzędnych x-owych
wierzchołków prostokątów, tworzę posortowaną (wg wsp. y) kolekcje odcinków poziomych ze znakiem (pomysł MarkaR22).

Dla każdej pary kolejnych wierzchołków (x[k],x[k+1]) przeglądam rosnąco kolekcję odcinków poziomych, odcinki zielone pomijam, czerwonei liczę zgodnie z algorytmem MarkaR22.
Jak ilości odcinków dodatnich i ujemnych są równe, to dodaję do obwodu 2*(x[k+1]-x[k]).
Próbuję właśnie zaimplementować ten algorytm.
//edit, zrobione.
Program jest w Javie w dwóch wersjach:
(a) czyta współrzędne prostokatów z pliku - żeby sprawdzić czy wyniki są poprawne,
(b) losuje współrzędne prostokątów - żeby sprawdzic czas działania, dla 100000 prostokątów liczy około 100 sekund.

W czym trzymasz wspołrzędne ? W hashmapie ?

Hmm... a co w wypadku sekwencji:

Szara strzałka obrazuje kierunek sprawdzania linii poziomych po y'ach. Żółte odcinki symbolizują poziomy (y-eki), na któych następuje "dodanie czegoś do obwodu". Czy ten dolny żółty odcinek z drugiego etapu sekwencji też dodam ponownie do obwodu ? Bo chyba nie powinien być dodawany, jako, że poprzednio był dodany wraz z resztą tego dolnego boku pierwszego prostokąta.

Być może znów coś źle zrozumiałem, więc w razie czego się nie gniewaj ;)

Off-topic: Czy nie uważacie, że ten temat powinien dostać jakieś wyróżnienie za to, jak porządnie i schludnie jest prowadzony ? ;D

Odpowiadam od końca, nie rozumiem twoich rozterek:

W lewym pasie po natrafieniu na pierwszy czerwony odcinek dodajesz do obwodu 2*(6-5), po trafieniu na drugi czerwony odcinek również dodajesz 2*(6-5), łącznie dodajesz 4. W prawym pasie, po trafieniu na pierwszy czerwony odcinek nic nie dodajesz, po trafieniu na drugi dodajesz 2*(10-8) = 4, i tak powinno być.
Współrzędne (osobno X-owe i Y-owe) wierzchołków prostokątów przechowuję w zbiorach (standardowa klasa Javy TreeSet),. Pozwala mi to nie sprawdzać czy dodawana do zbioru współrzęna jest "nowa" , ponadto zbiór zawierający liczby jest automatycznie posortowany.
P.S. Przyłączam sie do wniosku o nagrodę za wartości estetyczne,

No to tu albo coś zostało wymieszane (kwestia zliczania obwodu sumarycznego i kwestia dzielenia istniejących odcinków na większe, niż jednostkowe, by przyspieszyć działanie algorytmu), albo ja nie zrozumiałem Twojego pomysłu ;p

Wydawało mi się, że na rysunkach, gdzie występują pionowe przerywane linie chodzi o momenty dodawania nowych prostokątów do płaszczyzny (i dzielenie odcinków na fragmenty). A wtedy występuje anomalia, o której napisałem - jeśli będziemy chcieli obliczać obwód w miarę dodawania coraz to nowych prostokątów, to (powołam się na ten mój rysunek sekwencji z mojego poprzedniego posta) dodajemy prostokąt i wliczamy jego boki do obwodu (lewa część obrazka), a następnie dodajemy kolejny prostokąt (ten, który na prawej części obrazka jest u góry), wliczamy jego boki do sumarycznego obwodu a następnie dodajemy znów poziome boki (a w zasadzie ich fragmenty) poprzednio dodanego prostokąta, które także są pomiędzy "pionowymi przerywanymi liniami" (prostymi zawierającymi pionowe boki nowego prostokąta)... bo że ten algorytm działa w momencie, gdy już mamy wszystkie prostokąty dodane i sobie omiatamy przestrzeń, to ja już wiem - a przy okazji, to dziękuję Wam bardzo za pomoc w uściśleniu działania tego algorytmu omiatania ;)

Algorytm MarkaR22 z moją małą modyfikacją wyglada tak. Mam dwa posortowane zbiory W_x i W_y zawierające współrzędne x-owe i y-owe wszystkich wierzchołków, oraz dwie posortowane kolekcje O_x oraz O_y zawierające wszystkie boki prostokątów równoległe do osi X i równoległe do osi Y. Dla każdej pary kolejnych liczb ze zbioru W_x stosuję zmodyfikowany algorytm MarkaR22 - jeżeli ilość '+' i '-' jest taka sama to dodaję do obwodu 2*odległość punktów.
//dopisane, Moim zdaniem liczenie obwodu w locie jest bez sensu, ostatini badany protokąt może przecież zawierać wszystkie wcześniejsze prostokąty. Wtedy obwód figury jest obwodem tego ostatniego prostokąta.

No mi też właśnie wydawało się, że jest trochę bez sensu liczenie tego 'w biegu'.

Na razie nie mam więcej pytań, więc dziękuję Wam bardzo uprzejmie za pomoc :) Jesteście genialni :]