Декомпозиция полигона на треугольники

← →
Unknown user © (2009-06-13 11:28) [0]

Подскажите, пожалуйста, алгоритм декомпозиции невыпуклого полигона на треугольники. Стороны полученных треугольников не должны пересекать контур полигона. Желательно получить набор треугольников максимально близких к равносторонним.

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

← →
Kerk © (2009-06-13 11:33) [1]

Треугольников нужно минимальное количество или пофиг?

← →
MBo © (2009-06-13 11:42) [2]

http://prografix.narod.ru/rus_trian2d.html

← →
@!!ex © (2009-06-13 11:57) [3]

тесселяция это называется. гугл знает

← →
Unknown user © (2009-06-13 12:02) [4]

> Треугольников нужно минимальное количество или пофиг?

Минимальное.

> MBo

Спасибо, а есть что-то готовое на паскале? Демо программка по ссылке не загружает полигоны, лишь генерит случайные. Мне придется перекладывать исходники на Делфи только, чтобы оценить подойдет ли алгоритм для моих полигонов.

← →
Unknown user © (2009-06-13 12:14) [5]

> не загружает полигоны

Вру. Демо программа имеет множество версий, последняя загружает Wavefront OBJ

← →
oldman © (2009-06-15 00:57) [6]

Первое, что приходит на ум - для начала вписать внутрь полигона выпуклый полигон, который разбивается по минимуму легко "радиусами"

Остается подумать, какие есть варианты "оставшейся" части

← →
Unknown user © (2009-06-15 11:38) [7]

> Первое, что приходит на ум - для начала вписать внутрь полигона
> выпуклый полигон, который разбивается по минимуму легко
> "радиусами"

ТО ест ьразбить задачу на 2 части сначала невыпуклый полигон разбиват ьна выпуклые, затем уже полученные полигоны резать на треугольники?

← →
Unknown user © (2009-06-15 11:42) [8]

> тесселяция это называется. гугл знает

Гугл выдает ссылки на стандартные функции OpenGL и других граф. библиотек, мне же нужно получить на выходе список индексов треугольников.

MBo советовал примеры на С. Судя по демке работает неплохо, жаль что не могу загрузить свои полигоны, программа хоть и понимает WaveFront OBJ файлы, открывает их, однако при демонстрации алгоритмов все равно генерит случайные фигуры.

Вобщем так ничего толкового не нашел. неужели никто не решал аналогичную задачу?

← →
oxffff © (2009-06-15 12:00) [9]

> Вобщем так ничего толкового не нашел.

Обманываешь.

google

http://algolist.ru/maths/geom/polygon/triang1.php

← →
boa_kaa © (2009-06-15 12:09) [10]

обход по/против часовой стрелки + поиск сопряженной точки справа / слева такой, чтобы созданные 2 линии к ней не пересекали границу

Можно копать в сторону автоматических генераторов сеток для конечно-элементных программ. Точно есть готовое opensource на языке Ц++.

← →
Franzy (2009-06-15 16:55) [12]

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

Алгоритм работает, эту задачу я уже решал когда-то.

> Franzy (15.06.09 16:55) [12]

> В цикле перебираешь все пары ребер, образующих угол и смотришь,
> можно ли из них образовать корректный треугольник.

А что есть случай когда из пары ребер, образующих угол не получится треугольника? Наверное, этот треугольник должен быть вложен в исходный многоугольник.

← →
Franzy (2009-06-15 17:23) [14]

Это самая затратная часть алгоритма.
Третье ребро треугольника, которое образуется соединением двух первых, не должно пересекаться с другими ребрами многоульника (= вычисление 4 скалярных произведений для каждого ребра); кроме того, внутри новообразованного треугольника не должно лежать никаких других вершин многоугольника (=вычисление трех скалярных произведений для каждой вершины).

Декомпозиция полигона на треугольники Найти похожие ветки