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?
Odpowiedzi:
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.
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.
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:
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.
źródło