Próbuję pokryć prosty wklęsły wielokąt minimalnymi prostokątami. Moje prostokąty mogą mieć dowolną długość, ale mają maksymalną szerokość, a wielokąt nigdy nie będzie miał ostrego kąta.
Pomyślałem o próbie rozłożenia mojego wklęsłego wielokąta na trójkąty, które wytwarzają zestaw minimalnie nakładających się prostokątów minimalnie ograniczających każdy trójkąt, a następnie łączenie tych prostokątów w większe. Nie sądzę jednak, aby działało to w przypadku małych wycięć na krawędziach wielokąta. Trójkąty utworzone przez odruchowe wierzchołki na tych wycięciach utworzą niewłaściwe prostokąty. Szukam prostokątów, które będą obejmowały / ignorowały wycięcia.
Tak naprawdę nie wiem nic o geometrii obliczeniowej, więc nie jestem pewien, jak zacząć zadawać pytanie.
Znalazłem inne posty, które były podobne, ale nie to, czego potrzebuję:
- podziel wielokąt na minimalną liczbę prostokątów i trójkątów
- Pokrycie dowolnego wielokąta minimalną liczbą kwadratów
- Znajdź prostokątów, aby pokryły maksymalną liczbę punktów
- Algorytm znajdowania najmniejszej liczby prostokątów obejmujących zestaw prostokątów
Kilka przykładów: czarny jest wejściem. Kolor czerwony to dopuszczalna moc wyjściowa.
Kolejny przykład: preferowane jest drugie wyjście. Jednak wygenerowanie obu wyników i użycie innego czynnika do określenia preferencji jest prawdopodobnie konieczne, a nie odpowiedzialność tego algorytmu.
Wieloboki naśladujące krzywe są niezwykle rzadkie. W tym scenariuszu znaczna część obszaru prostokątów jest marnowana. Jest to jednak dopuszczalne, ponieważ każdy prostokąt spełnia ograniczenie maksymalnej szerokości.
Również ten artykuł był blisko tego, czego potrzebuję:
- Pokrycie prostokątnymi kawałkami Paula Iacoba, Danieli Marinescu i Cristiny Luca
Być może lepszym pytaniem jest „Jak rozpoznać prostokątne części wklęsłego wielokąta?”
Oto obraz przedstawiający pożądaną implementację:
Kolor zielony to faktyczne zużycie materiału. Czerwone prostokąty to układy. Niebieski to MBR całego wielokąta. Myślę, że powinienem spróbować zdobyć małe MBR i wypełnić je. 2-3 zielone prostokąty w lewym górnym rogu, które kończą się w środku wielokąta, są drogie. Właśnie to chcę zminimalizować. Zielone prostokąty mają minimalną i maksymalną szerokość i wysokość, ale mogę użyć tylu wierszy i kolumn, aby pokryć region. Ponownie muszę zminimalizować liczbę prostokątów, które nie rozciągają się na wejście. Mogę również modyfikować kształt zielonego prostokąta, aby pasował do małych miejsc, co jest również bardzo drogie. Innymi słowy, idealnym rozwiązaniem jest uzyskanie jak największej liczby prostokątów tak, aby obejmowały jak najwięcej.
źródło
Odpowiedzi:
Jest to wariant geometrycznej osłony zestawu. W zależności od dokładnych ustawień może być możliwe dobre przybliżenie. Problemem jest oczywiście NP-Hard. Naturalni huersytycy powinni używać chciwego algorytmu (zawsze wybieraj prostokąt / pasek, który obejmuje większość jeszcze nieobjętego obszaru. Alternatywną techniką jest ponowne ważenie. Istnieją pewne interesujące wyniki teoretyczne, ale szczerze mówiąc, nic, co nie powinno być zbyt przydatne w praktyce Jedną z interesujących hueristy, które możesz wypróbować, jest najpierw rozłożenie wielokąta na minimalną liczbę wypukłych kształtów (za pomocą algorytmu programowania dynamicznego Keila), a następnie pokrycie każdego wypukłego wielokąta osobno ...
źródło
Myślę, że ten artykuł może być pomocny. Oczywiście nie jest to ten sam problem - w rzeczywistości jest to problem odwrotny, obejmujący prostokąt wielokątami - ale niektóre pomysły mogą być punktem wyjścia. W szczególności ten odwrotny problem jest trudny do NP i podejrzewam, że twój również może być (choć, o ile wiem, nie ma wyraźnego rozszerzenia redukcji).
E. Arkin, A. Efrat, G. Hart, I. Kostitsyna, A. Kroller, J. Mitchell i V. Polishchuk. Skandynawskie cienkie ciasteczka na wierzchu ciasta: na najmniejszym jednym uniwersalnym pudełku. Zabawa z algorytmami . str. 16–27. 2012
źródło