Help Needed with CGAL Constrained Delaunay Triangulation (CDT) for Complex 2D Shapes

[leviskim17]

Hello, I'm a beginner with CGAL.

I'm currently updating legacy code and replacing the triangle.c library, as it no longer works in an x64 environment. My goal is to triangulate complex 2D shapes (including concave, convex, and those with holes).

In the code below, I am using CDT (Constrained Delaunay Triangulation) to sequentially add vertices and impose constraints with edge information. However, unwanted triangles are still being generated.

Could you help me understand what might be missing or what additional steps are required?

Thank you for your help!

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Constrained_Delaunay_triangulation_2.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_with_holes_2.h>
#include <CGAL/Triangulation_vertex_base_with_info_2.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Triangulation_vertex_base_with_info_2<int, K> Vb;
typedef CGAL::Constrained_triangulation_face_base_2<K> Fb;
typedef CGAL::Triangulation_data_structure_2<Vb, Fb> TDS;
typedef CGAL::Constrained_Delaunay_triangulation_2<K, TDS> CDT;
typedef CDT::Point Point_2;
typedef CGAL::Polygon_2<K> Polygon_2;
typedef CGAL::Polygon_with_holes_2<K> Polygon_with_holes_2;

Math3DTriangle* Math3D::TriangulatePolygon2(long vertexCount, const CPointd3D* vertex, const CPointd3D& normal, std::list<int> listContour, std::list<double> listInnerWalls, int* pnTriNum, BOOL bClockWise)
{
	// If no vertices, return nullptr
	if (vertexCount == 0) {
		return nullptr;
	}

	// Define outer polygon with vertex coordinates
	std::vector<Point_2> points;
	for (int i = 0; i < vertexCount; ++i) {
		points.emplace_back(vertex[i].m_x, vertex[i].m_z);

		std::string strBuffer;
		strBuffer.clear();
		strBuffer = StringUtility::GetInstance().Format("vertex %d: %f, %f\n", i, vertex[i].m_x, vertex[i].m_z);
		OutputDebugStringA(strBuffer.c_str());
	}

	// Initialize constrained Delaunay triangulation
	CDT cdt;

	// Insert vertices into triangulation
	std::vector<CDT::Vertex_handle> vertex_handles;
	for (int i = 0; i < vertexCount; ++i) {
		CDT::Vertex_handle vh = cdt.insert(points[i]);
		vh->info() = i;
		vertex_handles.push_back(vh);
	}

	// Insert polygon constraints (edges) into triangulation
	for (int i = 0; i < vertexCount; ++i) {
		cdt.insert_constraint(vertex_handles[i], vertex_handles[(i + 1) % vertexCount]);

		std::string strBuffer;
		strBuffer.clear();
		strBuffer = StringUtility::GetInstance().Format("edge %d: %d, %d\n", i, vertex_handles[i]->info(), vertex_handles[(i + 1) % vertexCount]->info());
		OutputDebugStringA(strBuffer.c_str());
	}

	// Extract finite faces (triangles) from the triangulation
	std::vector<Math3DTriangle> triangles;
	for (auto f = cdt.finite_faces_begin(); f != cdt.finite_faces_end(); ++f) {
		int v0 = f->vertex(0)->info();
		int v1 = f->vertex(1)->info();
		int v2 = f->vertex(2)->info();

		std::string strBuffer;
		strBuffer.clear();
		strBuffer = StringUtility::GetInstance().Format("triangle : %d, %d, %d\n", v0, v1, v2);
		OutputDebugStringA(strBuffer.c_str());

		// Create triangle with proper vertex ordering
		Math3DTriangle triangle;
		if (bClockWise) {
			triangle.index[0] = v0;
			triangle.index[1] = v2;
			triangle.index[2] = v1;
		}
		else {
			triangle.index[0] = v0;
			triangle.index[1] = v1;
			triangle.index[2] = v2;
		}
		triangles.push_back(triangle);
	}

	*pnTriNum = static_cast<int>(triangles.size());

	Math3DTriangle* result = new Math3DTriangle[triangles.size()];
	std::copy(triangles.begin(), triangles.end(), result);

	return result;
}

Shape with Vertics:

Log Result:

vertex 0: 182.225677, -189.000000
vertex 1: -182.928925, -189.000000
vertex 2: -182.928925, 189.000000
vertex 3: 182.928925, 189.000000
vertex 4: -10.214628, -4.143560
edge 0: 0, 1
edge 1: 1, 2
edge 2: 2, 3
edge 3: 3, 4
edge 4: 4, 0
**triangle : 4, 0, 3** (unnecessary)
triangle : 4, 3, 2
triangle : 1, 4, 2
triangle : 1, 0, 4

[MaelRL]

The triangulation is a partition of the convex hull of the points, which is why you have the triangle 0 3 4 in the finite faces. See https://doc.cgal.org/latest/Triangulation_2/index.html#Chapter_2D_Triangulations.

Check out the function CGAL::mark_domain_in_triangulation(), which can be used to tag connected components bounded by constrained edges. You can find an example of usage in this example: https://doc.cgal.org/latest/Triangulation_2/Triangulation_2_2polygon_triangulation_8cpp-example.html#a8.