занятная геометрия.... черезчур....

← →
wicked © (2006-02-17 19:41) [0]

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

← →
wicked © (2006-02-17 19:42) [1]

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

← →
Джо © (2006-02-17 19:50) [2]

Я бы начал с поиска пересекающихся отрезков (ребер, sections), и собственно, точек пересечения. Как-то так.

← →
umbra © (2006-02-17 19:53) [3]

а если многоугольник определен только координатами вершин, то откуда следует, что он самопересекающийся?

← →
Джо © (2006-02-17 19:54) [4]

> [3] umbra © (17.02.06 19:53)

Общепринято считать, что порядок описания вершин существенен.

← →
Ученик чародея © (2006-02-17 19:56) [5]

>>wicked © (17.02.06 19:42) [1]

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

http://www.cs.man.ac.uk/~toby/alan/software/
Ссылки на другие библиотеки работы с многоугольниками:
http://www.complex-a5.ru/polyboolean/comp.html
(CGAL, Leda - самые известные)

всем спасибо.... что-то проясняется.......

> Я бы начал с поиска пересекающихся отрезков (ребер, sections),
> и собственно, точек пересечения. Как-то так.
так и начал.... после нахождения таких точек стало возможным сформировать направленный циклический граф.... осталось найти его циклы с учетом направленностей полученных полигонов....
уфф, ну и медленно мне это всё дается.... :(

> MBo © (18.02.06 14:47) [6]
отдельное спасибо, но.... думаю, клиент не согласится покупать или одно, или другое.... это таки коммерческая разработка.... приходится строгать самому...
хотя, Мурта "впереди планеты всей" в данной тематике.... что радует....

занятная геометрия.... черезчур.... Найти похожие ветки