Многоугольники

[Nymph666]

Поможите пжлста!
Задачка такая: даны простые(т.е.могут быть вогнутыми, но без самопересечений) многоугольники(их может быть хоть сколько). Каждый из них задается списком точек. Нужно найти их пересечение, объединение и разность.

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

Если есть какие-нибудь исходники по этой теме, - поделитесь пожалуйста.

[крыс]

http://citforum.univ.kiev.ua/programming/theory/alg_triangl/index.shtml

[Nymph666]

http://citforum.univ.kiev.ua/programming/theory/alg_triangl/index.shtml

Пасиб, посмотрю

[Nymph666]

появилась новая идея: все многоугольники ориентированы по часовой стрелке. Строя пересечение(объединение) мы двигаемся по точкам пересечения все время направо(налево при объединении). Правда там еще нужна навигационная информация расстояние до многоугольников, вектора. Плюс нужно знать как определять правый вектор...
Кто-нибудь сталкивался с таким алгоритмом?

[Oxygene]

появилась новая идея: все многоугольники ориентированы по часовой стрелке. Строя пересечение(объединение) мы двигаемся по точкам пересечения все время направо(налево при объединении). Правда там еще нужна навигационная информация расстояние до многоугольников, вектора. Плюс нужно знать как определять правый вектор...
Кто-нибудь сталкивался с таким алгоритмом?

Почитайте, например, Ласло "Вычислительная геометрия и компьютерная графика на C++". И сразу же отпадет куча вопросов.