osi wyrównany prostokąty przecięcia

Question

trzeba algorytm bierze niesegregowanych szereg osiowych obróconych prostokątów i powraca każdy parę prostokątów pokrywa

każdego prostokąta ma dwa zmienne, współrzędne górnego lewego rogu oraz dolny prawy narożnik

Answer 1

To może być nieco skomplikowane do rozmowy kwalifikacyjnej, zależy jakiego rodzaju pracy, jest to geometryczne obliczenia rodzaj algorytmu,

odpowiedź można znaleźć tutaj: http://www.cs.princeton.edu/~rs/AlgsDS07/17GeometricSearch.pdf

Answer 2

Oto krótki opis algorytmu przecięcia przedstawionego w DuduAlul linku „s.

Rozwiązanie wymaga użycia drzewa wyszukiwania zdolnego do wykonywania zapytań dotyczących zakresu. Zapytanie zakresowe prosi o wszystkie elementy z wartościami między K1 i K2, i powinno być operacją O (R + log N), gdzie N jest całkowitą liczbą elementów drzewa, a R jest liczbą wyników.

Algorytm wykorzystuje podejście Przesunięcie:

1) Sortuj wszyscy lewej i prawej krawędzi prostokąta, w zależności od ich wartości X, w liście L.

2) Utwórz nowy pusty szukaj zakres drzewa T, o Y zamawiania wierzchołki prostokąta/podestylacyjnej

3) Tworzenie nowych zbiór pusty wynik RS unikalnych par prostokątnych

4) Traverse L w porządku rosnącym. Dla wszystkich V w l:

      Jeśli V.isRightEdge()

            T.remove (V.rectangle.top)

            T .remove (V.rectangle.bottom)

      inny

            Dla wszystkich U (w T.getRange V.rectangle.top, V.rectangle.bottom)

                  RS.add (< V.rectangle, U.rectangle>)

          T.add (V.rectangle.top)

            T.add (V.rectangle.bottom)

5) powrót RS

---

Złożony czas O (R + N log n), gdzie R to rzeczywista liczba skrzyżowań.

- EDIT -

prostu zorientowali się, że rozwiązanie nie jest w pełni poprawne - test skrzyżowanie w drzewie T strzela niektórych przypadkach. Drzewo powinno zachowywać odstępy Y zamiast wartości Y, najlepiej powinno być to Interval Tree.

Answer 3

Sweep and prune to metoda, którą wiele silników fizycznych rozwiązuje ten problem.

Istnieje dobre wyjaśnienie w David Baraff's SIGGRAPH notes, w sekcji 7.2 Skrzynki ograniczające.