Войти
ПрограммированиеФорумОбщее

Триангуляция невыпуклых полигонов. Алгоритмы ?

Страницы: 1 2 3 Следующая »
#0
13:54, 22 янв 2008

1. Самое эффективное что есть вроде как алгоритм Зейделя, но найти толковое его описание я так и не смог. Работает вроде как за время O(N).
2. Есть еще алгоритм в котором делят полигон на монотонные части.. Вроде как O(n*logN)
3. И есть алгоритм в котором тупо проводим линию и проверяем на пересекаемость с остальными ребрами. Есть еще алгоритм "Разделяй и властвуй" я его не читал, но вообщем всё это O(N^2).

В чем вопрос:
1. Может кто-нить может дать толковое описание или поделится ссылкой по алгоритму Зейделя.
2. В принципе устроило бы и N*log N.. Но везде где не читаю везде делают исключения.. Мол а давайте предположим что у нас координата х не может быть одинаковой.. Ну тоесть у вершин не может она совпадать..

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

#1
14:55, 22 янв 2008

можно использовать стандартный тесселятор имеющийся в OpenGL

#2
15:00, 22 янв 2008

MOD
Приму к сведению. Спасибо. Но думаю, что привязка к конкретному АПИ не есть ГУТ.

#3
16:33, 22 янв 2008

Gladiator
кури исходники glut'а glu
ЗЫ. прафко

#4
16:42, 22 янв 2008

Blew_zc
очень смешно =\

#5
17:27, 22 янв 2008

>>Но думаю, что привязка к конкретному АПИ не есть ГУТ.

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

#6
18:38, 22 янв 2008

По Зейделю, алгоритм состоит из 3-х шагов.

Вот цитата первого:
"Let S be a set of non-horizontal, non-intersecting line segments of the polygon . The randomized algorithm is used to create the trapezoidal decomposition of the X-Y plane arising due the segments of set S. This is done by taking a random ordering s1 .. sN of the segments in S and adding one segment at a time to incrementally construct the trapezoids. This divides the polygon into trapezoids (which can degenerate into a triangle if any of the horizontal segments of the trapezoid is of zero length). The restriction that the segments be non-horizontal is necessary to limit the number of neighbors of any trapezoid. However, no generality is lost due to this assumption as it can be simulated using lexicographic ordering. That is, if two points have the same y-coordinate then the one with larger x-coordinate is considered higher. The number of trapezoids is linear in the number of segments. Seidel proves that if each permutation of  s1 .. sN  is equally likely then trapezoid formation takes O(n log*n) expected time."

Если кто знаком, подскажите плз. почему есть ограничение (выделенное).. Не очень понял. =(

#7
20:01, 22 янв 2008

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

#8
20:49, 22 янв 2008

uss
Ну о качетсве говорить не приходится потому как любой алгоритм должен всё правильно триангулировать. На данном этапе мне скорость не так важна, но мне намекнули, что это может пригодится в задачах, для которых скорость алгоритма имеет первостепенное значение. Конечно, можно взять и реализовать разные алгоритмы. )
Да и.. Вопрос на засыпку: а Вы реализовывали Зейделя ? :) Я просто перерыл по инету кучу инфы, и получил ответ такой что Зейдель наибыстрейший алгоритм (Но он рассматривает полигоны без дыр, но они (дыры) мне и не нужны).

И еще есть может кто-нить на вскидку предложить несколько алгоритмов ? :)

#9
23:36, 22 янв 2008

из тех алгоритмов которые я знаю нормального я незнаю(не устраивают меня может комуто и подходят)
ещё стоит учитывать поддаётя ли алгоритм распаралеливанию сосбенно глядя в будущее

#10
23:59, 22 янв 2008

uss
ой... Зачем такие сложности ? :) Мне и этих хватает :)))

#11
10:45, 23 янв 2008

Gladiator
я работаю с полигонами с дырками произвольной формы. Лучше жадного алгоритма (тым где тупо проводим линию и проверяем на пересекаемость с остальными ребрами) на данный момент не знаю. По крайней мере результат хороший. А если в полигоне ребер немного, то и не слишком медленный

#12
12:19, 23 янв 2008

Gladiator
попробуй так:
обходиш полигон до первого угла больше 180 градусов и начинаеш трианлуляцию таким образом чтоб в этой части полигон утратил "вывернутость" потом ищеш следующий угол больше 180 градусов...когда у погигона все углы будут меньше 180 градусов он становится выпуклым и кромсаем его как угодно.
этот алгоритм имеет огромнейший недочёт ибо он не всегда работает(когда форма полигона позволяет ему выполнится то он прекрасен когда нет то... он виснет :)
намного лучше следующий подход:
ищеш угол больше 180 градусов и режеш полигон на 2 полигона секущей выходящей из вершины которой принадлежит этот угол тамим образом чтоб угол стал меньше 180 градусов у каждого из полученых полигонов ... потом берёш следующий угол....(не забудь о новых полигонах их тоже нада триангулировать)
алгоритм прекрасно распаралеливается, всегда работает

#13
12:25, 23 янв 2008

Freckle
Это вроде как O(N^2) ?

Нету в сети толкового описания Алгоритмов. Нашел этого Зейделя. Но там есть много вопросов, задать которые собсно некому. Разве, что автору :)

#14
12:28, 23 янв 2008

uss
А что если у меня все углы <180 градусов ?

Страницы: 1 2 3 Следующая »
ПрограммированиеФорумОбщее

Тема в архиве.