Заполнение многоугольника наименьшим количеством прямоугольников

Question

Я пытаюсь отрисовать полигоны, но они могут быть отрисованы только с помощью выровненных по оси прямоугольников. Итак, я ищу алгоритм, который может в основном заполнить многоугольник, используя минимум возможного количества прямоугольников. Если это поможет уменьшить количество, прямоугольники могут перекрывать друг друга.

Я уже реализовал этот алгоритм заполнения , которого в основном достаточно. Недостатком является то, что он ограничивает прямоугольники для каждой строки пикселей. В конечном итоге я хочу максимально уменьшить количество прямоугольников.

Answer 1

Пиксельное представление многоугольника такое же, как у прямолинейного многоугольника, и вы можете разбить его довольно быстро.Смотрите ответ на этот вопрос .

Answer 2

Снятие этого ограничения (высота каждого прямоугольника равна одному пикселю) помогает в некоторых особых случаях, когда многоугольник состоит из больших прямоугольников, но не в общем случае.

Как насчет этого: используйте этот алгоритм, но максимально увеличьте каждый прямоугольник вверх и вниз, а когда все прямоугольники на месте, удалите лишние.

Есть еще немного возможностей для улучшения, в котором порядок , в котором вы исключаете лишние прямоугольники, может иметь значение в некоторых очень редких случаях, но, честно говоря, я не думаю, что стоит беспокоиться о практическое решение.