Triangulating the polygons with holes

[Nikismyname]

Hi could you tell me how you approach the triangulation of the polygons that have holes in them?

[pvlso]

Hey,

I used a simple triangulation method like ear clipping for this algorithm. You triangulate the outer polygon and its hole, then find overlapping triangles and subtract them. It’s not the most efficient approach, but it gets the job done pretty well.

I’m not sure why you need polygon-with-hole triangulation, but I’ve explored a few other methods. One option is Delaunay Constrained Triangulation, which produces well-spaced triangles. However, it’s primarily designed for triangulating a set of points rather than a polygon boundary. You’d also need to remove triangles outside the polygon boundary, including those within the hole, so it’s not the ideal solution.

If you’re triangulating polygons for navigation meshes, it’s better to first partition the polygon to eliminate holes and then triangulate the resulting shapes. Alternatively, you can use an algorithm to partition the polygon into convex shapes, which eliminates the need for triangulation entirely.

If you’re performing operations like subtraction, union, XOR, or intersection on polygons, I highly recommend the Clipper2 library. I’ve also developed my own version, which is faster and rewritten in my style with memory and SIMD optimizations. It focuses solely on the operations mentioned above without additional features.

For more details, check out my website. I recommend these posts:

Triangle Boolean Subtraction
Triangulation
Clipper2 Reimplementation
Progress on Navigation Meshes for Map Editing Mode

Feel free to reach out if you have more questions.