Эффективный алгоритм упаковки для неправильных полигонов
Я ищу алгоритм упаковки, который уменьшит неправильный полигон в прямоугольники и прямоугольные треугольники. Алгоритм должен попытаться использовать как можно меньше таких форм и должен быть относительно легок реализовать (учитывая трудность проблемы). Это должно также предпочесть прямоугольники по треугольникам, если это возможно.
Если возможно, ответ на этот вопрос должен объяснить общую эвристику, используемую в предложенном алгоритме.
Это должно работать в детерминированное время за неправильными полигонами меньше чем с 100 вершинами.
Цель состоит в том, чтобы произвести "разумную" разбивку неправильного полигона для неспециалиста.
Первая эвристика относилась к решению, определит, правилен ли многоугольник или неправилен. В случае правильного многоугольника мы будем использовать подход, обрисованный в общих чертах в моем подобном сообщении о регулярных уловках: Эффективный Алгоритм Упаковки для Правильных многоугольников
сопроводительный текст http://img401.imageshack.us/img401/6551/samplebj.jpg
2 ответа
Я не знаю, даст ли это оптимальный ответ, но он, по крайней мере, даст ответ:
- Вычислить триангуляцию Делоне для данного многоугольника. Для этого существуют стандартные алгоритмы, которые будут работать очень быстро для 100 вершин или меньше (см., Например, эту библиотеку здесь. ). Использование триангуляции Делоне должно гарантировать, что у вас не будет слишком много длинных вершин, тонкие треугольники.
- Разделите любые непрямые треугольники на два прямоугольных, понизив высоту с наибольшего угла на противоположную сторону.
- Найдите треугольники, которые можно объединить в прямоугольники: любые два конгруэнтных прямоугольных треугольника (не зеркальные изображения), которые имеют общую гипотенузу.Я подозреваю, что в общем случае их не будет слишком много, если ваш неправильный многоугольник не имеет для начала много прямых углов.
Я понимаю, что нужно заполнить много деталей, но я думаю, что начать с триангуляции Делоне, вероятно, лучше. Триангуляции Делоне на плоскости могут быть вычислены эффективно, и в целом они выглядят вполне «естественно».
ИЗМЕНЕНО, ЧТОБЫ ДОБАВИТЬ: поскольку мы находимся в специальном эвристическом парке, в дополнение к жадным алгоритмам, обсуждаемым в других ответах, вам также следует подумать о какой-то стратегии «разделяй и властвуй». Если форма невыпуклая, как в вашем примере, разделите ее на выпуклые формы, многократно разрезая от одной вершины рефлекса к другой вершине таким образом, чтобы максимально приблизить угол рефлекса к делению пополам. После того, как вы разделите форму на выпуклые части, я бы подумал о том, чтобы разделить выпуклые части на части с красивыми «основаниями», части, у которых хотя бы одна сторона имеет два острых или прямых угла на концах. Если у какой-то части нет такой «основы», вы сможете разделить ее пополам по диаметру части и получить две новые части, каждая из которых имеет «основу» (я думаю). Это должно свести проблему к работе с выпуклыми многоугольниками, которые являются своего рода трапециевидными, и оттуда жадный алгоритм должен работать хорошо. Я думаю, что этот алгоритм разделит исходную форму довольно естественным образом, пока вы не дойдете до трапециевидных частей.
Хотел бы я поиграть с этим, потому что это звучит как действительно забавная задача!
Моей первой мыслью (глядя на вашу диаграмму выше) было бы искать 2 смежных прямых угла, вращающихся в одном направлении. Я уверен, что это не уловит каждый случай, когда прямоугольник поможет, но с точки зрения пользователя это очевидный случай (квадратные углы снаружи = это должен быть прямоугольник).
После того, как вы нашли смежную пару прямых углов, возьмите длину более короткого отрезка, и получится один прямоугольник. Вычтите это из многоугольника слева от плитки и повторите. Когда больше нет очевидных внешних прямоугольников, которые нужно удалить, сделайте свою обычную мозаику (ответ Питера звучит великолепно).
Заявление об ограничении ответственности: я не специалист в этом вопросе и даже не пробовал ...