C++: CGAL 2D треугольная триангуляция: вогнутые фигуры

Question

Я вхожу в CGAL для некоторых задач 2D триангуляции, и у меня также есть что-то простое для работы allready. Во всяком случае, я действительно не понимаю, как триангулировать вогнутые формы, так как прямо сейчас я всегда получаю выпуклую оболочку всех точек. В основном я хочу добавить точки на mouseClick, подобно тому, как он работает в иллюстраторе, так что все точки в их порядке являются контуром формы. Как я могу это сделать с CGAL? Простой пример того, как триангулировать вогнутые формы в целом, поместит меня на правильный путь! благодаря!

Answer 1

Я думаю, вам сначала понадобится partition многоугольник в выпуклые части. После этого вы можете создать треугольники каждого отдельного многоугольника с чем-то вроде этого:

for (int i = 1; i + 1 < polygon.size(); ++i) { 
    const Point_2& v0 = polygon[0]; 
    const Point_2& v1 = polygon[i]; 
    const Point_2& v2 = polygon[i + 1]; 
} 

Answer 2

http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml