C ++: CGAL 2D-триангуляция Делоне

Question

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

Answer 1

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

Answer 2

Если вы получаете выпуклый контур вместо вогнутого, это, вероятно, связано с передаваемым альфа-значением. Попробуйте использовать find_optimal_alpha (1) в качестве альфа-значения или вычислите значения относительно ограничивающего размера облака точек, в котором вы находитесь прохождение. Например.

Alpha_shape_2 aShape(inPoints.begin(), inPoints.end());
aShape.set_alpha( aShape.find_optimal_alpha(1) );
aShape.set_mode(Alpha_shape_2::REGULARIZED);

Answer 3

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

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];
}