Здравствуйте!
Подскажите, пожалуйста, есть ли реализация построения пересечения полигонов на С++ ?(нужна с открытым кодом )
Требования к полигонам
Полигоны задаются в общем виде: могут быть невыпуклыми, состоять из нескольких контуров (т.е. иметь "полые" области).

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

Предполагаемое решение
(Фрмагмент из книги — стр. 120)
1. Построение триангуляции с ограничениями на массиве вершин полигонов;
2. Нахождение общих треугольников и слияние их в искомое пересечение.

Возможно иное решение. Выбор триангуляционного алгоритма обусловлен типом полигонов (общий вид) и их многоконтурностью.
Сравнительный анализ алгоритмов — http://num-meth.srcc.msu.ru/zhurnal/tom_2002/pdf/art1_8.pdf — стр. 123

Есть такие варианты (пока не ознакомился в деталях, возможно кто-то сможет прокомментировать по своему опыту):
1) FASTGeo (under Common public license )
2) Clipper (under Boost Software License)

Существуют ли уже реализации, использующие мощности графических процессоров (в основном интересует под NVIDIA)?

С уважением.

GPC
boost Geometry