Эффективный алгоритм упаковки для правильных многоугольников
Я ищу алгоритм упаковки, который уменьшит правильный многоугольник в прямоугольники и прямоугольные треугольники. Алгоритм должен попытаться использовать как можно меньше таких форм и должен быть относительно легок реализовать (учитывая трудность проблемы).
Если возможно, ответ на этот вопрос должен объяснить общую эвристику, используемую в предложенном алгоритме.
3 ответа
Я думаю, что ответ довольно прост для регулярных многоугольников.
Найдите ось симметрии и проведите линию между каждой вершиной и ее зеркалом. Это делит многоугольник на трапеции. Каждая трапеция может быть превращена в прямоугольник и два правильных треугольника.
Это не конкретно прямоугольники + прямоугольные треугольники, но хорошая точка исследования для изучения мозаичных многоугольников - это Диаграммы Вороного и триангуляции Делоне и здесь и здесь .
Фактически, если "только прямоугольные треугольники" достаточно хороши, они гарантированно будут выполнять триангуляцию для вас, и вы всегда можете разделить любой треугольник на два прямоугольных треугольника, если они вам действительно нужны. Или вы можете отрезать «кончики» треугольников, чтобы сделать больше правильных треугольников и несколько прямоугольников из прямоугольных.
Вы также можете попробовать вырезать уши , либо проведя радиально, если вы знаете, что у вас достаточно правильные многоугольники, либо путем «обрезки самого большого выпуклого фрагмента». Затем разделите каждый оставшийся треугольник на два, чтобы создать прямоугольные треугольники.
(источник: eruciform.com )
Вы можете попытаться сделать меньше перерывов, проведя в одну сторону, а затем в другую, чтобы образовать трапецию и разделить ее по-другому, но тогда вам придется сделать проверьте, чтобы ваша линия развертки не пересекла где-нибудь другую линию. Всегда можно ушную клипсу, даже что-то практически фрактальное.
Однако иногда при этом получаются очень тонкие треугольники. Вы можете выполнить эвристику, например «взять самое большое», вместо непрерывного отсечения по краю, но это займет больше времени, приближаясь к O (n ^ 2). Delaunay / Vornoi сделает это в большинстве случаев быстрее, с менее тонкими треугольниками.
Вы можете попробовать «вырезать» самый большой прямоугольник, который может поместиться в многоугольник , оставив после себя некоторые остатки. Продолжайте вырезать прямоугольники на остатках, пока не получите треугольные кусочки. Затем при необходимости их можно разделить на два прямоугольных треугольника. Я не знаю, всегда ли это будет давать решения, которые дадут вам наименьшее количество прямоугольников и прямоугольных треугольников.