Люди, просьба поделиться опытом. Нужен алгоритм для триангуляции поверхности с полигонами у которых есть дырки, или непересекаемые ломанные линии внутри.

Есть отработанный алгоритм Делоне для поверхности из точек, есть Ухорезка для полигонов тоже хорошо работает, но не с дырками.

Заранее спасибо.

То, что нужно?

Да, спасибо, я это пробовал, там готовая DLL.

Как правило почти всегда встречается либо частичное описание, либо готовая DLL.

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

всёравно спасибо.

Есть книга: "Вычислительная геометрия и компьютерная графика на C++", Майкл Ласло. Издательство BINOM. Книга у меня уже несколько лет, поэтому не знаю, можно ли ее сейчас найти.
По-моему, книга замечательная, содержит очень доступное описание многих геометрических алгоритмов.
В частности, там описывается несколько алгоритмов триангуляции полигона, например, путем расщепления произвольного полигона на т.н. монотонные части, затем триангуляция каждого по отдельности.


Это сообщение отредактировал(а) Earnest - 18.6.2005, 08:10

Можно посмотреть в CGAL
(в районе http://www.cgal.org/Manual/doc_html/cgal_m...pter_main.html)
в Wild Magic (в районе http://www.geometrictools.com/SourceCode.html)
и в FastGEO (в районе http://www.partow.net/projects/fastgeo/index.html)
Да и насколько я помню, у Manoche-Seidel всегда были исходники на сайте.
Еще кажется триангуляция произвольных поверхностей была в книге Аммералла (в одном из 4-х его томов). Не уверен, что для такого случая у него были готовые исходники, но алгоритм был, т.к. я такую триангуляцию написал после прочтения его. К сожалению, дело было очень давно, лет 12 назад, и поэтому исходники не сохранились.

да, срасибо,
вот, нашёл вроде подходящую
http://www.codeproject.com/cpp/hgrd.asp