Разбиение многоугольника на «внутри» и «снаружи»

Question

У меня есть (не обязательно выпуклый) многоугольник.Я хотел бы найти набор прямоугольников, которые занимают все пространство в границах мира ((0,0) - (100,100)), не занимая места внутри многоугольника.Какой самый простой способ найти эти полигоны?Существуют ли алгоритмы для такого рода вещей?

Спасибо!

Например, полигон

 __    __
|  |__|  |
|________|

может быть разбит на следующие пять прямоугольников:

aaabbbbbbbbbbeee
aaa|  |cc|  |eee
aaa|________|eee
aaaddddddddddeee

или, альтернативно, следующие шесть прямоугольников:

aaaaaaabbccccccc
eee|  |bb|  |ddd
eee|________|ddd
ffffffffffffffff

Существует ли простой способ разбить многоугольник на прямоугольники между многоугольником и границами мира?

Answer 1

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

• Используйте треугольники, чтобы сделать все ребра многоугольника вертикальными или горизонтальными
• Используйте четыре прямоугольника, чтобы вырезать как можно больше места сверху / снизу / слева / справа
  • Теперь у вас есть многоугольник, имеющий только вертикальные / горизонтальные края и простирающийся до каждой границы
• Жадно поместите самый большой прямоугольник, который вы можете в самые большие отверстия в форме
  • Найдите самые большие промежутки между сторонами
• Заполните треугольники от шага 1 до предельной точности