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.