Wypełnianie wielokąta z najmniejszą ilością prostokąta

Question

Próbuję renderować wielokątów, ale mogą być renderowane tylko za pomocą prostokąty wyrównane do osi. Tak więc, szukam algorytmu, który może w zasadzie wypełnić wielokąt przy użyciu możliwej liczby prostokątów. Jeśli pomaga to zmniejszyć ilość, prostokąty mogą się nakładać na siebie.

Ja już wdrożone this fill algorithm, które najczęściej wystarcza. Upadek polega na tym, że ogranicza prostokąty do każdego rzędu pikseli. Ostatecznie chcę zmniejszyć ilość prostokątów tak bardzo, jak to możliwe.

Answer 1

Reprezentacja pikseli wielokąta jest taka sama jak wielokąta prostoliniowego i można ją szybko podzielić na partycje. Zobacz odpowiedź na to question.

Answer 2

Usunięcie tego ograniczenia (że każdy prostokąt ma wysokość jednego piksela) pomaga w niektórych szczególnych przypadkach, gdy wielobok składa się z dużych prostokątów, ale w ogóle nie w ogólnym przypadku.

Co powiesz na to: użyj tego algorytmu, ale rozciągnij każdy prostokąt w górę i w dół, jak tylko możesz, a gdy wszystkie prostokąty są na swoim miejscu, wyeliminuj zbędne.

Jest jeszcze trochę miejsca na poprawę, że zamówienie w którym można wyeliminować zbędne prostokątów może materia w niektórych bardzo rzadkich przypadkach, ale szczerze mówiąc nie sądzę, że warto martwić się na praktyczne rozwiązanie .