Polygon Triangulation with Holes

graphics geometry direct3d triangulation cgal
Agnel Kurian picture Agnel Kurian · Jan 2, 2009 · Viewed 41.9k times · Source

I am looking for an algorithm or library (better) to break down a polygon into triangles. I will be using these triangles in a Direct3D application. What are the best available options?

Here is what I have found so far:

  1. Ben Discoe's notes
  2. FIST: Fast Industrial-Strength Triangulation of Polygons
  3. I know that CGAL provides triangulation but am not sure if it supports holes.

I would really appreciate some opinions from people with prior experience in this area.

Edit: This is a 2D polygon.

Answer

zweiterlinde picture zweiterlinde · Mar 9, 2009

Jonathan Shewchuk's Triangle library is phenomenal; I've used it for automating triangulation in the past. You can ask it to attempt to avoid small/narrow triangles, etc., so you come up with "good" triangulations instead of just any triangulation.

Related questions

Algorithm to detect intersection of two rectangles?

I'm looking for an algorithm to detect if two rectangles intersect (one at an arbitrary angle, the other with only vertical/horizontal lines). Testing if a corner of one is in the other ALMOST works. It fails if the rectangles …

Read More
fast algorithm for drawing filled circles?

I am using Bresenham's circle algorithm for fast circle drawing. However, I also want to (at the request of the user) draw a filled circle. Is there a fast and efficient way of doing this? Something along the same lines …

Read More
How to draw a decent looking Circle in Java

I have tried using the method drawOval with equal height and width but as the diameter increases the circle becomes worse looking. What can I do to have a decent looking circle no matter the size. How would I implement …

Read More