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

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

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

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

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

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

alt text http://img401.imageshack.us/img401/6551/samplebj.jpg

Ответ 1

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

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

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

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

Ответ 2

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

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

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

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