Эффективный алгоритм упаковки для нерегулярных полигонов

Question

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

Если возможно, ответ на этот вопрос должен объяснить общую эвристику, используемую в предлагаемом алгоритме.

Это должно выполняться в детерминированное время для нерегулярных полигонов с менее чем 100 вершинами.

Цель состоит в том, чтобы произвести «разумную» разбивку неправильного многоугольника для непрофессионала.

Первая эвристика, примененная к решению, будет определять, является ли многоугольник правильным или неправильным. В случае правильного многоугольника мы будем использовать подход, описанный в моем аналогичном посте о регулярных многоугольниках: Эффективный алгоритм упаковки для правильных многоугольников

альтернативный текст http://img401.imageshack.us/img401/6551/samplebj.jpg

Answer 1

Я не знаю, даст ли это оптимальный ответ, но, по крайней мере, даст ответ:

1. Вычислить триангуляцию Делоне для данного многоугольника. Для этого существуют стандартные алгоритмы, которые будут работать очень быстро для 100 вершин или меньше (см., Например, эту библиотеку здесь. ). Использование триангуляции Делоне должно гарантировать, что у вас не будет слишком много длинных, тонкие треугольники.
2. Разделите любые неправильные треугольники на два прямоугольных, опустив высоту от наибольшего угла к противоположной стороне.
3. Поиск треугольников, которые вы можете объединить в прямоугольники: любые два конгруэнтных прямоугольных треугольника (не зеркальные изображения), которые разделяют гипотенузу. Я подозреваю, что в общем случае их будет не слишком много, если только у вашего неправильного многоугольника много прямых углов.

Я понимаю, что нужно заполнить много деталей, но я думаю, что начинать с триангуляции Делоне - это, вероятно, путь. Триангуляции Делоне на плоскости могут быть эффективно рассчитаны, и они обычно выглядят вполне «естественными».

ИЗМЕНЕНО ДЛЯ ДОБАВЛЕНИЯ: так как мы находимся в специальном эвристическом мире, в дополнение к жадным алгоритмам, обсуждаемым в других ответах, вы должны также рассмотреть некоторую стратегию «разделяй и властвуй». Если фигура невыпуклая, как в вашем примере, разделите ее на выпуклые фигуры, многократно вырезая из вершины рефлекса в другую вершину так, чтобы это было как можно ближе к делению угла рефлекса. После того, как вы разделите фигуру на выпуклые части, я бы рассмотрел следующее деление выпуклых частей на части с красивыми «основаниями», куски которых по крайней мере с одной стороны имеют два острых или прямых угла на концах. Если у какой-либо фигуры нет такой «основы», вы сможете разделить ее на две части по диаметру фигуры и получить две новые фигуры, каждая из которых имеет «основу» (я думаю). Это должно свести проблему к работе с выпуклыми многоугольниками, которые являются своего рода трапециевидными, и оттуда жадный алгоритм должен преуспеть. Я думаю, что этот алгоритм будет довольно естественным образом разделять исходную форму, пока вы не доберетесь до трапециевидных фигур своего рода сорта.

Answer 2

Хотелось бы, чтобы у меня было время поиграть с этим, потому что это звучит очень весело!

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

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

Отказ от ответственности: я не эксперт в этом, и я даже не пробовал это ...