Znajdowanie wolnych nie przecinających się prostokątów w obszarach między prostokąciami w C#

Mam następujący problem. Duży prostokąt zawiera mniejsze nieprzecinające się prostokąty (Czarne prostokąty na poniższym obrazku) i muszę znaleźć algorytm, który wypełni pozostały wolny obszar niepodzielnymi prostokątami (czerwone na poniższym obrazku). Prędkość nie jest problemem dla algorytmu. Również, jeśli ktoś miałby przykładowy kod źródłowy algorytmu, naprawdę bym to docenił.Znajdowanie wolnych nie przecinających się prostokątów w obszarach między prostokąciami w C#

Edytuj. Małe wyjaśnienie Potrzebuję uzyskać współrzędne czerwonych prostokątów, aby ich nie narysować. Pracuję również z danymi punktowymi, a nie z obrazami.

http://koti.mbnet.fi/niempi2/Squares.gif

Źródło

2010-08-04 Jargo

Czy zaczynasz od danych punktowych lub obrazu? –

Dane punktowe, oznaczające współrzędne czarnych prostokątów na rysunku. Muszę też uzyskać współrzędne czerwonych prostokątów, a nie tylko ich narysować. – Jargo

Istnieje więcej niż jeden sposób definiowania zestawu czerwonych prostokątów dla danego zestawu czarnych prostokątów. Czy interesuje Cię, który zestaw jest zwracany? –

Podobnie jak większość problemów z pakowaniem w pojemniki, ten problem wygląda na NP-trudny problem dla mnie. Za 2 prostokąty jest 8! (= 40320) możliwe ustalenia, które należy wziąć pod uwagę. Trzy prostokąty dają 12! możliwości, fajne 480 milionów.

Będziesz potrzebować heurystyki do obliczenia tego. Poza faworyzowaniem zewnętrznych krawędzi prostokąta położonych najbliżej prostokąta ograniczającego, nie widzę dobrego. Potrzebowaliby Państwo ściślejszych wymagań dotyczących otrzymanych prostokątów, których liczba nie pomoże. Cieszę się, że to nie mój problem :)

Źródło

2010-08-04 15:36:16

Jak już powiedziałem przed układem prostokątów nie ma znaczenia i faktycznie mogę zrezygnować z wymogu posiadania najmniejszej możliwej liczby wypełnianych prostokątów. Naprawdę nie muszę przechodzić przez wszystkie możliwe rozwiązania, ponieważ mogę po prostu wybrać pierwszą, która wypełnia całą pustą przestrzeń. Rozwiązaniem, o którym myślałem, było najpierw obliczyć 4 najbardziej zewnętrzne prostokąty wypełniające, co jest zadaniem łatwym, a następnie obliczyć centralne prostokąty osobno, w tym przypadku masz tylko 4! możliwe układy z 2 prostokąciami. – Jargo

Wydaje się, że już wiesz, jak to zrobić. Dlaczego pytasz? –

@Nobugz: Czy możesz mi powiedzieć, jak obliczałeś 2 prostokąty wymagałoby 8! a 3 wymagałoby 12 !? –

Spójrz na klasy regionie.

Źródło

2010-08-04 13:46:17 leppie

proszę przestań dzwonić do nazwisk osób bez żadnego powodu lub prowokacji podczas retagowania ich pytań. Zwłaszcza gdy błędne tagowanie sprowadza się do [błędu] (http://meta.stackexchange.com/questions/59556/tags-with-uppercase-characters-get-cut) –

Chociaż istnieje wiele możliwych rozwiązań, myślę, że można dostać się do jednego dość łatwo.

Chciałbym pracować zwiększając wartości wzdłuż jednej osi. Po zeskanowaniu wszystkich prostokątów i uporządkowaniu ich krawędzi wzdłuż tej osi można przejść przez nie i utworzyć prostokąty. Za każdym razem, gdy uderzysz w nową parę rogów, możesz porównać z prostokątami, które aktualnie masz "otwarte" i określić, co zrobić (zamknij je, zacznij nowe, podziel itd.).

To stwierdzenie nie jest kompletnym rozwiązaniem, ale myślę, że przeniesie cię z rozwiązania złożonego do prostego. Wydaje się również, że nie jest NP kompletny pod względem wydajności. Możesz nawet uzyskać O (n) perf.

Ciekawy problem. Daj nam znać, jak sobie radzisz.

Źródło

2010-08-05 14:48:09

Znajdowanie wolnych nie przecinających się prostokątów w obszarach między prostokąciami w C#

Odpowiedz

Powiązane problemy