Polygon Triangulation with Holes

by

To give you some more choices of libraries out there:

Polyboolean. I never tried this one, but it looks promising: http://www.complex-a5.ru/polyboolean/index.html

General Polygon Clipper. This one works very well in practice and does triangulation as well as clipping and holes holes: http://www.cs.man.ac.uk/~toby/alan/software/

My personal recommendation: Use the tesselation from the GLU (OpenGL Utility Library). The code is rock solid, faster than GPC and generates less triangles. You don’t need an initialized OpenGL-Handle or anything like this to use the lib.

If you don’t like the idea to include OpenGL system libs in a DirectX application there is a solution as well: Just download the SGI OpenGL reference implementation code and lift the triangulator from it. It just uses the OpenGL-Typedef names and a hand full of enums. That’s it. You can extract the code and make a stand alone lib in an hour or two.

In general my advice would be to use something that alreay works and don’t start to write your own triangulation.

It is tempting to roll your own if you have read about the ear-clipping or sweep-line algorithm, but fact is that computational geometry algorithms are incredible hard to write in a way that they work stable, never crash and always return a meaningful result. Numerical roundoff errors will accumulate and kill you in the end.

I wrote a triangulation algorithm in C for the company I work with. Getting the core algorithm working took two days. Getting it working with all kinds of degenerated inputs took another two years (I wasn’t working fulltime on it, but trust me – I spent more time on it than I should have).

More Related Contents:

  1. Closest point on a cubic Bezier curve?
  2. How to test if a line segment intersects an axis-aligned rectange in 2D?
  3. How do you check for intersection between a line segment and a line ray emanating from a point at an angle from horizontal?
  4. Algorithm to detect intersection of two rectangles?
  5. how should i handle (morphing) 4D objects in opengl? [closed]
  6. Does anyone know of a low level (no frameworks) example of a drag & drop, re-order-able list?
  7. How to print R graphics to multiple pages of a PDF and multiple PDFs?
  8. correcting fisheye distortion programmatically
  9. GraphViz – How to connect subgraphs?
  10. How to draw a decent looking Circle in Java
  11. Why doesn’t hue rotation by +180deg and -180deg yield the original color?
  12. Create the square, rectangle, triangle of java in jframe [closed]
  13. Creating a Movie from a Series of Plots in R [closed]
  14. Sort Four Points in Clockwise Order
  15. extracting a quadrilateral image to a rectangle
  16. Calculate a point along the line A-B at a given distance from A
  17. How to recognize rectangles in this image?
  18. Blackberry – how to resize image?
  19. Finding the coordinates of points from distance matrix
  20. How do you find a point at a given perpendicular distance from a line?
  21. Find if a point is inside a convex hull for a set of points without computing the hull itself
  22. Transformation of 3D objects related to vanishing points and horizon line
  23. How to offset a cubic bezier curve?
  24. Algorithm for drawing a 4-connected line
  25. Bouncing Ball. Making it slow down at peak of height
  26. Bump-map a sphere with a texture map
  27. Most underused data visualization [closed]
  28. In MATLAB, how do I plot to an image and save the result without displaying it?
  29. How to best approximate a geometrical arc with a Bezier curve?
  30. How to mix two ARGB pixels?

Leave a Comment