У меня есть невыпуклый многоугольник, который я хочу заполнить плитками фиксированного размера на сетке так, чтобы как можно больше плиток из сетки было полностью , содержащихся в многоугольнике.
Дополнительная Важным требованием является то, чтобы плитки были, насколько это возможно, выровнены (то есть параллельно) к краям многоугольника (или, по крайней мере, к более длинным) краям.
Вот две сетки, наложенные на один и тот же многоугольник:
Я ищу алгоритм, который найдет «шов» который разделит многоугольник так, что он сохранит максимальное количество целых плиток с каждой стороны.
В этом примере черные пунктирные линии показывают такие швы, которые сохраняют больше целых плиток, чем если бы мы использовали диагональ (оранжевым цветом):
Примечания:
- В примере не показаны сетки, выровненные по другим краям, но такая поддержка желательна;
- Другой аспект заключается в том, можно ли выбрать лучшую «фазу» (перемещая ее вдоль осей X и Y) для каждой сетки, чтобы максимизировать количество целых плиток, содержащихся в конечном многоугольнике.