Poszukiwanie algorytmu "brutalnej siły" do usuwania obszarów przecinających się z kolekcji Rectów

Question

Mam n-rozmiar kolekcji Rektów, z których większość się przecina. Chciałbym usunąć skrzyżowania i zredukować przecinające się Reksy do mniejszych nie przecinających się rectów.

Mogę łatwo wymusić rozwiązanie, ale szukam skutecznego algorytmu.

Oto wizualizacja:

oryginalny:

Przetworzony:

Idealnie podpis metoda będzie wyglądać następująco:

public static List<RectF> resolveIntersection(List<RectF> rects); 

dane wyjściowe będą większe lub równe wartości wejściowej, w której wyjście rozwiązuje powyższą reprezentację wizualną.

Answer 1

to jest problem, który rozwiązałem w przeszłości. Pierwszą rzeczą jest posortowanie prostokątów za pomocą wartości x lub y jednej z krawędzi. Powiedzmy, że zamawiamy w kierunku y i używamy górnej krawędzi. Najwyższy prostokąt w twoim przykładzie jest najpierw posortowany. Dla każdego prostokąta znasz jego rozmiar w kierunku y.

Teraz dla każdego wpisu (nazwij go bieżącym wpisem, odpowiada prostokącie) na posortowanej liście, którą przeszukujesz do przodu, aż osiągniesz wpis większy niż bieżący wpis + odpowiadający rozmiar prostokąta. (nazwij to wejście zatrzymania)

Wszelkie pozycje w posortowanej liście między bieżącym wpisem a tym miejscem zatrzymania będą potencjalnymi przecięciami. Po prostu sprawdź, czy prostokąty x zakresy przecinają się.

Decydując się na sortowanie w kierunku X lub Y, lepiej będzie wybrać większy wymiar, ponieważ spowoduje to mniejszą liczbę przecięć, a więc mniejszą kontrolę.

Oto przykład. Prostokąty są zdefiniowane jako R (x1, x2, Y1, Y2), w którym X1 jest po lewej stronie, X2 jest po prawej stronie, Y1 górna i Y2 jest dolny

rectangle 1 (1,5,0,4) 
rectangle 2 (7,9,6,8) 
rectangle 3 (2,4,2,3) 
rectangle 4 (3,6,3,7) 
rectangle 5 (3,6,9,15) 

sortowania według y1 otrzymując

#    y1 size 
rectangle 1  0 4 
rectangle 3  2 3 
rectangle 4  3 4 
rectangle 2  6 2 
rectangle 5  9 6 

więc prostokąt 1 ma y1 + wielkość = 0 + 4 = 4 sugeruje to potencjalnie przecinają prostokąt 3 (Y1 = 3 < 4) i prostokąta 4 (Y1 = 3 < 4), ale nie prostokąt 2 (Y1 = 6> 4) ... nie ma potrzeby sprawdzania żadnych prostokątów na liście po 2

Prostokąt 3 ma y2 + rozmiar = 2 + 3 = 5 oznacza, że ​​potencjalnie będzie przecinał prostokąt 4 (wartość y1 = 3 < 5), ale nie ma odwrotności 2 (wartość y1 = 6> 5), nie trzeba sprawdzać żadnych prostokątów na liście po 2

Prostokąt 4 ma wielkość y2 + = 3 + 4 = 7 sugerując, że potencjalnie będzie przecinał prostokąt 2 (wartość y1 = 6 < 7), ale nie będzie ponownie odnawiać 5 (wartość y1 = 9> 7)

Oczywiście przy dużej liczbie prostokąty zazwyczaj wystarczy sprawdzić ułamek możliwych par dla skrzyżowania.

Answer 2

czego descrbing jest problem pakowania, zajrzyj na wikipedia

odnosi się do this artykuł opisujący algorytm pakowania prostokątów w prostokątach

to z artykułu:

W tym artykule opisano szybki algorytm do pakowania serii prostokątów o różnych szerokościach i wysokościach do pojedynczego otaczającego prostokąta, bez nakładania się i w sposób minimalizujący ilość zmarnowanej przestrzeni w otaczającym prostokącie. .

Answer 3

Algefony linii grzbietu są dobre na skrzyżowaniach przetwarzania w 2D wszechświatach. Mam na myśli linię poziomą przesuwającą się z krawędzi prostokąta do następnej krawędzi prostokąta. Linia uderza w kilka prostokątów, tworząc tzw. Listy aktywne. Aktywna lista jest aktualizowana przy każdym ruchu.

Analizując zasięgi odciętych wzdłuż linii poziomej, można wykryć nakładanie się.

Dokładne badanie wszystkich konfiguracji powinno pozwolić na podział prostokątów w jeden sposób, przy mniejszej złożoności niż brute force (bliżej N^1.5 niż N^2).