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