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