У меня есть несколько 2D-полигонов, каждый из которых представляет собой список координат по часовой стрелке. Многоугольники простые (т. е. они могут быть вогнутыми, но не пересекаются друг с другом) и не не перекрывают друг друга.
Мне нужно разделить эти многоугольники на меньшие многоугольники, чтобы соответствовать ограничению размера. Как и исходные многоугольники, меньшие должны быть простыми (несамопересекающимися), и ограничение состоит в том, что каждый из них должен помещаться в пределах одного «единичного квадрата» (который для простоты я могу предположить равным 1x1).
Дело в том, что мне нужно сделать это максимально эффективно, где «эффективно» означает наименьшее возможное количество результирующих (маленьких) полигонов. Время расчета не имеет значения.
Есть ли какой-то умный алгоритм для этого? Сначала я подумал о рекурсивном подразделении каждого полигона (разделив его пополам, либо по горизонтали, либо по вертикали, в зависимости от того, какое направление больше), что работает, но, похоже, я не получаю при этом очень оптимальных результатов. Любые идеи?
