Вопрос:

Минимальная квадрилатерлизация полигонов - существующие алгоритмы?

computational-geometry cgal polygons

78 просмотра

1 ответ

25 Репутация автора

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

Я нигде не могу найти очевидный из готового алгоритма, который делает это, поэтому я думаю пойти по двум возможным путям.

1. Сначала получить оптимальную триангуляцию, а затем преобразовать ее в четырехугольники

2. Попытка изменить функцию CGAL optim_convex_partitions из пакета разбиения 2d полигонов для создания четырехсторонних разделов https://doc.cgal.org/latest/Partition_2/group__PkgPolygonPartitioning2.html#ga3ca9fb1f363f9f792bfcc55555

Я абсолютный новичок в вычислительной геометрии, поэтому я просто хотел бы знать, не кажется ли какой-либо из этих подходов глупым поручением, прежде чем я попытаюсь изучить C ++? Если кто-нибудь знает что-нибудь о наилучшем подходе к этому, это будет еще лучше. Спасибо!

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

пример многоугольника

Автор: davis_grubin Источник Размещён: 05.01.2018 02:19

Ответы (1)


0 плюса

560 Репутация автора

Решение
  1. Я предполагаю, что если вы начнете с треугольников, а затем попытаетесь жадным образом объединить два соседних треугольника в один четырехугольник, у вас может получиться много изолированных треугольников.

  2. Не уверен, как выпуклая перегородка может пригодиться.

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

Тед Д. Блэкер и Майкл Б. Стивенсон, «Мощение: новый подход к автоматической генерации четырехугольной сетки» Int. J. Num.Meth.Engg, Vol 32, 811-847 (1991)

Jinwoo Choi и Yohngjo Kim, Разработка нового алгоритма для автоматической генерации четырехугольной сетки, Международный журнал CAD / CAM Vol. 10, № 2, с. 00 ~ 00 (2011

Я далеко не эксперт в этой области, но я уверен, что эти alg. может быть реализовано с помощью CGAL ...

Автор: Efi Fogel Размещён: 05.01.2018 08:18
Вопросы из категории :
32x32