Прямолинейный непересекающийся многоугольник

Question

У меня есть некоторый непересекающийся многоугольник, и мне нужно «выровнять» его так, чтобы все углы были углами 90 градусов.

Есть ли хороший алгоритм для этого?

РЕДАКТИРОВАТЬ

Допуская самопересечения в получающемся многоугольнике, я ищу «лучший» метод тесселяции плиток прямоугольной формы в исходном многоугольнике.Прямоугольники могут охватывать исходные края многоугольника, и цель состоит в том, чтобы расположить большинство прямоугольников прямо в многоугольнике.

Answer 1

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

Вы можете использовать квадродерево для разделения сегментов линии до тех пор, пока каждый сегмент линии не окажется один в своей ячейке квадродерева (в качестве альтернативы вы можете подразделить дальше, пока не будет достигнут некоторый коэффициент аппроксимации).Затем замените каждый отрезок на два отрезка его ограничительной рамки.

hth

Answer 2

Вы можете заменить каждую сторону многоугольника «лестницей», которая напоминает исходную сторону, например:

чем больше «шагов» вы добавляете к каждой лестницеЧем ближе он напоминает исходную форму.