Algorithm to decompose nested concave polygons into triangles?

Do a Leafy BSP out of it then triangulate resulted faces.

I remember, there was something about raytracing and triangularization, where it had to do with radiosity, but think it was, triangularization. I didm't get too straight forward results.

I think a good way, is to use typical triangular creation from polygon, and then use linear intersection to test for a collision with any of the lines, and just recursively to that, though it seems like there'd be errors.

Though I think a better way, would be to convert the polygon, into separate convex polygons, (to remove the gap), then convert those polygons into triangles, by using one anchor point.

Ah, BSPs, didn't think of that.

I'll investigate futher into that and come back if I run into troubles.

Thanks for the replies!

The most common tactic I've run into for triangulation is to subdivide the polygon into monotonic polygons, which you then triangulate. That involves a trapezoidal decomposition for simple polygons which is then used to detect "splits" and "merges". How it would work for polygons with holes, though, I don't know.

You can make your two polygons a single "key-hole" polygon by introducing two edges connecting an inner vertex and an outer vertex. Those edges must not intersect any other polygon edges (other than at their endpoints). In your example, let P0 be the leftmost vertex of the outer polygon and label the remaining vertices of that polygon P1, P2, P3, and P4, in counterclockwise order. Let Q0 be the leftmost vertex of the inner polygon and label the remaining vertices of that polygon Q1 and Q2, in *clockwise* order. The orderings are chosen so that as you walk around either polygon in the specified order, the interior is to your left.

Introduce two edges connecting P0 and Q0. The key-hole polygon is a simple polygon but where you allow coincident edges. This polygon has vertices listed so that the interior is always to the left: P0, P1, P2, P3, P4, P0, Q0, Q1, Q2, Q0, P0 (this last one to stress that you reached the initial point). You can apply a standard method for triangulating a simple polygon, for example, ear-clipping.

It was easier to find articles on the subject when I discovered the "correct" keywords.

'decomopose into triangles' = 'triangulate' or 'triangulation'
'nested polygons' = 'polygons with holes'

After some futher googling, I found several triangulation algorithms for simple polygons, among them the one you mention, ear-clipping, which I also choosed to implement (the polygons are triangulated on "load time", so I picked a simple algorithm before a fast one).

The approach you describe sounds like a viable one. I am writing this on J2ME, so I can't have overly complex polygons anyway. That will probably be easier than to try implemeting a triangulation algoritm for arbitrary polygons with holes.

Quote:

Original post by Enselic Example:

Not to be anal, but the outer polygon is not convex.

For nested convex polygons, it's really easy O(n+m) to do, start with the min-x vertex of both polygons, and create fans around vertices as you walk around both polygons, alternating between the inside and outside polygon.

For nested non-convex simple polygons, most any triangulation algorithm should be trivially modifiable to allow you to specify already triangulated regions, then you triangulate the polygons starting from the inner-most and walking out.

I have used this polygon-clipping library before, which has a function for decomposing complex polygons into triangles. The result looks like a bunch of trapezoids, which is not the output I would have dreamed of, but it worked for what I wanted it.