Algorytm „leczenia” wielu prostokątów w mniejszą liczbę prostokątów?


14

wprowadź opis zdjęcia tutaj

Powiedzmy, że mam siatkę prostokątów o różnych kształtach i kolorach i chcę zmniejszyć (w miarę zbliżona do optymalnej jest w porządku, optymalna nie jest konieczna) liczbę prostokątów reprezentujących ten sam układ kolorów.

Powyższy obraz jest bardzo uproszczonym przypadkiem, a odstępy między prostokątami służą wyłącznie do wizualizacji - byłyby właściwie ciasno upakowane.

Jaka jest metoda lub nazwa algorytmu (chętnie google), która może mi w tym pomóc?


3
Czy możesz nam powiedzieć coś o tym, skąd pochodzą te prostokąty? Czy mają tendencję do (zgrubnego) wyrównywania z jakąkolwiek leżącą pod nią siatką, czy mają wspólny blok konstrukcyjny lub jakiś najmniejszy prostokąt „atomowy”? Czy można je obracać? Wygląda to na problem, który może być bardzo drażliwy w najbardziej ogólnym przypadku, ale może stać się o wiele łatwiejszy, jeśli będziemy mogli wykorzystać pewne ograniczenia lub podobieństwa w konkretnym scenariuszu.
DMGregory

Istnieje podstawowa siatka kwadratów (jak szachownica), a każdy prostokąt dzieli granice z tymi kwadratami. tzn. możesz użyć liczby całkowitej, aby opisać górę / dół / lewo / prawo każdego prostokąta. Dlatego nie można ich obracać pod kątami niepodzielnymi o 90 stopni. Również siatka NxM jest w pełni wypełniona prostokątami - nie ma odsłoniętych pozycji siatki.
xaxxon

Staram się po prostu uniknąć przypadku, który wygląda jak powyższy przykład (z perspektywy kolorowania), ale składa się z tony prostokątów 1x1 i przetwarzam każdy z nich, gdy mogę obsłużyć przestrzeń na wielu mniej połączeń.
xaxxon

Zgaduję, że „po prostu zacznij gdzieś i próbuj coraz większych prostokątów w jednym wymiarze (powiedzmy w pionie), aż trafisz na obramowanie koloru, a następnie powiększ drugi wymiar (poziomo), aż dojdziesz do obramowania. Następnie spróbuj najpierw w poziomie Może spróbuj tylko kwadraty (rosnące po przekątnej), ale nie jestem pewien, czy po prostu wybranie największej z powyższych 3 możliwości jest właściwym podejściem
xaxxon

Czy dopuszczalne jest podzielenie istniejącego prostokąta, jeśli spowoduje to mniej prostokątów na końcu? A może algorytm powinien się kiedykolwiek łączyć? Czy całkowite zliczanie jest jedynym kryterium, czy wolisz kwadratowe kształty niż długie wąskie paski / większe prostokąty niż mniejsze?
DMGregory

Odpowiedzi:


15

Po pierwsze, możemy przekonwertować źródłowe prostokąty na komórki w podstawowej siatce, aby ujednolicić dane wejściowe. (Skutecznie rasteryzuje problem)

Pozwoli nam to znaleźć optymalizacje, które mogą nie być oczywiste przy bezpośredniej pracy z prostokątami źródłowymi - szczególnie gdy obejmuje podział wielu prostokątów źródłowych w celu ich rekombinacji w inny sposób.

Przykład przekształcania prostokątów w komórki siatki i odwrotnie

Następnie możemy znaleźć połączone regiony tego samego koloru, korzystając z algorytmów wyszukiwania w pierwszej głębokości lub wypełniania zalewowego. Możemy rozważyć każdy połączony region ( poliomino ) w oderwaniu - nic, co robimy z innym regionem, nie musi wpływać na ten region.

Skutecznie chcemy znaleźć sposób na podzielenie tego poliomino na prostokąty (niestety większość literatury, którą mogę znaleźć, dotyczy przeciwnego problemu: przecinanie prostokątów na poliomino! To utrudnia poszukiwanie potencjalnych klientów ...)

Jedną z prostych metod jest łączenie poziomych przebiegów sąsiednich kwadratów w długie chude prostokąty. Następnie możemy porównać z powyższym wierszem i połączyć, jeśli nasze uruchamianie i końce pasują do siebie - albo gdy kończymy każdy przebieg / wiersz, albo gdy rozważamy każdą komórkę, aby dodać do bieżącego przebiegu.

Rozkładanie poliomino na przebiegi poziome, a następnie scalanie w pionie

Nie wiem jeszcze, jak blisko ta metoda jest optymalna. Wygląda na to, że może mieć trochę kłopotów, gdy rząd, którego jeszcze nie rozpatrzył, sugeruje inny podział niż wiersze, które widział do tej pory:

Przykład przypadku z rozwiązaniem 3-prostokątnym, w którym powyższa metoda znajduje 4

Wykrywanie, kiedy przebieg / prostokąt jest dokładnie objęty przebiegami powyżej i poniżej, a następnie podzielenie go i scalenie rozwiąże ten konkretny przypadek, ale nie zbadałem, jak ogólny jest problem.

Przyjrzałem się także metodom, w których chodzimy po obwodzie poliomino, i przecinamy je za każdym razem, gdy napotykamy wklęsły róg, ale takie podejście wydaje mi się bardziej podatne na błędy. Wydaje się, że uzyskanie optymalnych wyników wymaga priorytetowych cięć, które łączą dwa wklęsłe narożniki, a kształty zawierające wgłębienia wymagają specjalnego traktowania, więc metoda skanowania rzędów wydaje się mieć tę zaletę prostoty.

Jeszcze jedną metodą, na którą patrzę, jest wykonanie pierwszego biegu znalezionego w górnym rzędzie i przedłużenie go w dół, na ile to możliwe. Następnie weź pierwszy bieg w górnym rzędzie tego, co zostało ... To się jednak potknie na odwróconych kształtach T, więc też nie jest optymalne.

Wydaje mi się, że istnieje sposób na użycie programowania dynamicznego w celu znalezienia optymalnego podziału, ale jeszcze go nie znalazłem.


Dzięki za niesamowitą odpowiedź! to rozwiązanie wygląda na tyle szybko, że mógłbym uruchomić go w kilku różnych kierunkach i wybrać, który wydaje się najlepszy - poziomy lewy -> prawy, poziomy prawy -> lewy, a następnie również pionowy w każdą stronę.
xaxxon

2
Problem polega na tym, że możemy konstruować kształty, które wprowadzą algorytm w błąd z każdego kierunku przeciągnięcia. Być może nie pojawią się one w rzeczywistości, ale wciąż mnie to wkurza. Myślę, że jest jeszcze prosta poprawka ... Coś takiego jak odnotowanie w każdym przebiegu, czy nad nią są wklęsłe rogi w połowie biegu. Następnie, jeśli kolejny bieg zakończy się dokładnie w tym punkcie, cofamy się przez biegi powyżej, dzieląc je pionowo. Jednak nie uporządkowałem wszystkich szczegółów.
DMGregory

1
Nie jestem też pewien, dlaczego krok wypełniania powodzi jest konieczny. Przechodząc z positino siatki do długiego chudego prostokąta, możesz po prostu przejść pełny rząd lub kolumnę siatki (w dowolną stronę), aby utworzyć te prostokąty 1xN. Nie musisz nigdy znać poliomino, prawda?
xaxxon

Masz rację, wypełnienie powodzi nie jest koniecznym krokiem. Dodałem go, aby usprawiedliwić skupianie się tylko na jednym kolorowym obszarze na raz w kolejnych krokach, ale można łatwo zastosować metodę skanowania wiersza do przeplatanych wielu kolorowych regionów. Metoda oparta na obwodzie musi jednak działać na obwodzie jednego kształtu na raz.
DMGregory
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.