Menu
I would like to triangulate between two sets of polygons. One set is always inside the other, in fact, the outer polygons are created as offsets from the original set. Triangulation would be easy if they were on the same plane, but I would like to add depth by moving the outer polygon to a parallel but different plane. The usual method for triangulation that I use (glu tesselator) does not work. Is there an alternative that would?
647
A monotone polygon can be triangulated in linear time by using a simple greedy algorithm which repeatedly cuts off the convex corners of the polygon [Fournier and Montuno 1984]. Hence, all the monotone polygons can be triangulated in O(n) time.
The 42 possible triangulations for a convex heptagon (7-sided convex polygon).
Theorem: Every polygon has a triangulation. Proof by Induction. Base case n = 3. Pick a convex corner p.
A triangulation of a polygon can be thought of as a set of chords that divide the polygon into triangles such that no two chords intersect (except possibly at a vertex). This is a triangulation of the same polygon: An optimal triangulation is one that minimizes some cost function of the triangles.
You are saying that you have a triangulation method that works in 2D. Fine. Put both of your contours on the same plane z = 0, do the 2D triangulation, then set z coordinate of the vertices of the outer contour to the value you need. As you said, move the outer contour to the parallel plane.
Why this approach doesn't suit you?
Yes, you may end up with some horizontal triangles, which have all three vertices with the same z coordinate. If you used a "true" 3D triangulation you also may end up with same horizontal triangles. It all depends on the shape of the contour and algorithm.
If it is not acceptable to have such horizontal triangles you can add a second pass to try to eliminate them:
Find a horizontal triangle. Two of its edges would belong to either original inner or original outer contour. The third edge would "short-circuit" the vertices of the original contour. Find another triangle that has the same edge as the "third" edge described above. The pair of these triangles form a rhombus. There are only two ways to triangulate the rhombus. The one that you've got is not acceptable, so just re-triangulate the rhombus in a different way.
It is hard to explain this without drawings.
95
IMO when you have moved the outer polygon you can try a delaunay triangulation in 3d for example with circumspheres. Cgal can do 3d triangulation.
37
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
