Biorąc pod uwagę wiele linii poziomych i pionowych, jak znaleźć wszystkie prostokąty, które mają wewnątrz podarty prostokąt?

Question

Mam wiele linii poziomych i pionowych, które tworzą prostokąt, takich jak w tym przykładzie.

Czy istnieje algorytm lub kod, który może zlokalizować każdy prostokąt, który nie zawiera innego prostokąta. Mam na myśli, że największy prostokąt na tym obrazie nie jest prostokątem, którego szukam, ponieważ zawiera w sobie inne prostokąty.

Prostokąty, których szukam, muszą być puste. Mam listę punktów początkowych i końcowych każdej linii, jak (a, b) do (c, d). Chcę w rezultacie listę prostokątów (x, y, w, h) lub równoważnych.

Należy zauważyć, że niektóre linie mają linie przecinające je pod kątem prostym, na przykład górna linia najszerszego prostokąta na tym obrazie to pojedyncza linia, której przecinająca się pionowa linia biegnie w dół.

Answer 1

Czy wszystkie linie są równoległe do osi X lub Y? A może wszystkie twoje linie są równoległe lub prostopadłe?

Z podanego przykładu zakładam, że wszystkie twoje linie są równoległe do osi X lub Y. W takim przypadku twoje wiersze będą miały postać [(a, b), (a, d)] lub [(a, b), (c, b)].

W każdym przypadku, pierwszym zadaniem jest znalezienie rogów. to zbiór punktów, w których spotykają się dwie prostopadłe linie.

Drugim zadaniem jest wykrywanie prostokątów. Dla każdej pary rogów możesz sprawdzić, czy tworzą one prostokąty.

Trzecim zadaniem jest sprawdzenie, czy prostokąt zawiera w sobie jakiekolwiek prostokąty.

Do pierwszego zadania należy oddzielić linie na dwa zestawy: pionowy i poziomy. Po tym sortowaniu jeden z zestawów. Dawny. Sortuj pionowe linie zgodnie z ich współrzędnymi osi x. Następnie możesz wziąć wszystkie poziome linie i wykonać binarne wyszukiwanie, aby znaleźć wszystkie przecinające się punkty.

W drugim zadaniu rozważ każdą parę rogów i sprawdź, czy istnieją dwa pozostałe rogi. Jeśli tak, sprawdź, czy istnieją linie łączące wszystkie te cztery rogi. Jeśli tak, masz prostokąt.

Dla trzeciego zadania, umieść wszystkie prostokąty w drzewie interwałowym. Następnie możesz sprawdzić, czy dwa prostokąty pokrywają się.

Answer 2

Myślę, że inna reprezentacja pomoże rozwiązać problem. Jako przykład rozważ duży prostokąt (bez bloku na końcu). Istnieją cztery unikalne współrzędne x i y, sortuj je i indeksuj. Obrazowo to będzie wyglądać następująco:

Jeśli jest narożnik prostokąta o współrzędnych (x_i, y_j) umieścić go w matrycy tak:

__|_1__2__3__4_ 
1 | x x 0 x 
2 | x x 0 0 
3 | 0 x x x 
4 | x x x x 

Teraz definicji prostokąt real space to prostokąt na współrzędnych macierzy. Na przykład istnieje prostokąt o numerze (3,2) (3,4) (4,4), (4,3), ale nie jest to prostokąt "podstawowy", ponieważ zawiera podtemat (3,3) (3,4), (4,4), (4,3). Algorytm rekursywny jest tutaj łatwo zauważalny, a dla dodatkowej prędkości należy użyć funkcji zapamiętywania, aby zapobiec powtarzającym się obliczeniom.

Answer 3

A sweep-line algorithm ...

struktury wymagane:

• V = Zestaw linii pionowych, sortowane przez współrzędną x.

• H = Zbiór wszystkich punktów początkowych i końcowych linii poziomych (i każdy punkt ma odniesienie do linii) i posortowany według współrzędnej x.

• CH = An (początkowo pusty) posortowany (według współrzędnej y) zestaw bieżący linie poziome.

• CR = Posortowany (według współrzędnej y) zestaw obecnych prostokątów. Te prostokąty będą miały współrzędne lewy, górny i dolny, ale nie będą mieć jeszcze prawej współrzędnej. Pamiętaj, że w tym zestawie nie będzie nakładania się.

Algorytm:

Jednocześnie proces V, H, od lewej do prawej.

Po napotkaniu początku linii poziomej dodaj linię do CH.

Po napotkaniu końca linii poziomej usuń ją z CH.

Kiedy spotyka pionowa linia:

• Usuń z CR wszystkie prostokąty, które pokrywają się z linią. Dla całego usuniętego prostokąta, jeśli jest on całkowicie zawarty w linii, porównaj jego wielkość z najlepszym prostokątem do tej pory i zapisz go, jeśli jest lepszy.

• Sposób każdy element CH iteracyjnie pomiędzy punktem dolnym i górnym punkcie linii następująco:

  • Dodać prostokąt CR z ostatniego przetworzonego punktu jako dno, bieżący punkt jako górze współrzędna y linii pionowej po lewej stronie.

Gotowe.

Uwaga:

Gdy współrzędna x poziomych punktów startowych lub punktów końcowych lub pionowe linie są równe następujący porządek musi być utrzymana:

x of horizontal start < x of vertical line < x of horizontal finish 

przeciwnym razie umknie prostokąty.

Answer 4

Tego rodzaju pytania są w dużej mierze odbierane przez niektóre standardowe algorytmy Computational Geometry. Mogę wymyślić algorytm vertical sweep line dla tego konkretnego problemu.

Zakładając, że prostokąt jest reprezentowany przez parę punktów (p1, p2), gdzie p1 jest lewym górnym rogiem, a p2 jest prawym dolnym rogiem. A punkt ma dwa atrybuty (może być dostępny jako p.x i p.y).

Oto algorytm.

1. posortować wszystkie pary punktów - O(n log n)
2. zainicjować listę o nazwie sweep line status. Spowoduje to zatrzymanie wszystkich prostokątów, które napotkano do tej pory, czyli alive. Inicjuj także inną listę o nazwie event queue, która zawiera zbliżające się wydarzenia. Ten event queue zawiera obecnie punkty początkowe wszystkich prostokątów.
3. Przetwarzaj zdarzenia, zacznij od pierwszego elementu w event queue.
   • Jeśli zdarzenie jest start point, a następnie dodać, że prostokąt sweep line status (posortowanych według współrzędnej y) (w O(log n) czasu) i dodanie jej prawy dolny punkt na event queue w odpowiednim położeniu (sortowany przez punkty) (ponownie w O(log n) czasie). Po dodaniu go do sweep line status, wystarczy sprawdzić, czy ten punkt leży w prostokącie żywy tuż nad nim w sweep line status. Jeśli leży w środku, to nie jest twój prostokąt, w przeciwnym razie dodaj to do listy wymaganych prostokątów.
   • Jeśli wydarzenie jest punktem końcowym, po prostu usuń prostokąt odradzający się z sweep line status.

czasu (n prostokąty) biegany

• Sortowanie odbywa O(n log n).
• Liczba zdarzeń = 2 * n = O(n)
• Każde zdarzenie trwa O(log n) czasu (wstawki w event queue jak sweep line status. Więc Całości jest O(n log n).

Dlatego O(n log n).

Dla Więcej szczegółów można znaleźć na stronie Bentley–Ottmann algorithm. Powyższa prosta modyfikacja to:

EDYCJA:

Po prostu uświadomiłem sobie, że dane wejściowe są pod względem segmentów linii, ale ponieważ zawsze tworzą prostokąty (zgodnie z pytaniem), liniowe przejście dla procesu wstępnego może przekształcić je w prostokąt (para punktów).