jak sprawdzić kolekcję prostokątów na dziury i przejścia?

Question

Poszukuję sposobu sprawdzenia kolekcji prostokątów (Java TreeSet) - implementowanej przez "porównywalną" klasę Java przy użyciu google guavas Range dla zakresu x i y - dla skrzyżowań i otworów. Wiem, że opcją może być używanie drzewek kd, ale nie mam pojęcia jak zbudować takie drzewo-kd (dla prostokątów powinno to być 4d, czyż nie?) I jak rozwiązać problem (skrzyżowanie , dziury).

sortowanie priorytetuje oś x na osi Y.

EDIT: (starają się przekształcić problem): przypadek użycie jest tworzenie dowolnych tabel (składające się z 2 lub 3 bloki prostokąty „cel”, „pre kolumnę”, „dane”). muszę zagwarantować, że w każdym bloku nie ma przecięć ani dziur (tj. dostarczonych przez nieprawidłowy html lub inne źródła danych tabel) (poza tym bloki muszą pasować do siebie). Obecnie (właśnie wpadłem na pomysł) staram się zapisać w tablicy 2d, które pozycje (x, y) są zajęte. na końcu wszystkie pozycje muszą być zajęte dokładnie raz.

Answer 1

Istnieje wiele metod rozwiązywania tego typu problemów, z których każdy ma inne zalety i wady. Oto niektóre z nich:

Prostokąt Pair Przecięcie + Area Suma

Spójrz na każdej pary prostokątów - jeśli dwa prostokąty przecinają, występuje nakładanie. Dodaj obszary prostokąta i sprawdź, czy suma pasuje do obszaru roboczego - jeśli obszary się nie zgadzają, istnieje luka.

Malowanie

To podejście wspomniałeś: tworzenie 2D tablicę, która ma wymiary płótna. Następnie należy powtórzyć prostokąty i "pomalować" je w tablicy.

Jedną z optymalizacji tego podejścia jest kompresja współrzędnych. Załóżmy, że masz prostokąty [(10,20), (15,25)] i [(7,3), (15, 25)]. Możesz przyjrzeć się różnym współrzędnym x (7, 10, 15) i przyporządkować je do (0, 1, 2) i odrębnych współrzędnych y (3, 20, 25) i przyporządkować je do (0, 1, 2). Następnie pozostawiasz prostokąty [(1, 1), (2, 2)] i [(0,0), (2,2)], więc do malowania potrzebujesz tylko tablicy 3x3, zamiast 26x26 szyk.

Sweep Linia Algorytm

Sweep linii od lewej do prawej, zatrzymując się w miejscach „ciekawych” oraz śledzenie, które obszary są zajęte.

2D Zakres Drzewa

Struktura danych, które mogą skutecznie wykonywać zapytania nad zakresami prostokąta.

Który wybrać?

To zależy od liczby posiadanych prostokątów, ich rozmieszczenia w regionie, szybkości działania algorytmu, stopnia złożoności, z jaką chcesz się zmierzyć itd. Pierwsze dwa algorytmy, o których wspomniałem, to: znacznie prostsze niż te dwa ostatnie, więc polecam zacząć tam.

Więcej informacji

Jeśli chcesz dowiedzieć się więcej na temat tych algorytmów, spróbuj wyszukać „unii prostokąt” online. Najbardziej wydajnym rozwiązaniem jest algorytm linii przeciągnięcia.

Oto kilka odniesień na algorytmie linii przemiatania:

1. What is an Efficient algorithm to find Area of Overlapping Rectangles
2. http://compgeom.cs.uiuc.edu/~jeffe/open/klee.html
3. J. L. Bentley, Algorytmy dla problemów prostokąt Klee. niepublikowane notatki, Computer Science Department, Carnegie Mellon University, 1977

referencyjny 3. jest zwykle podawana jako oryginalnego źródła algorytmu linii omiatania dla unii prostokąt, ale muszę przyznać, że faktycznie nie znaleźć papier online, być może dlatego, że jest "Niepublikowane" ...