I have a computational problem - I have an arbitrary polygon chain, which I wish to triangulate, but I wish to triangulate it in such a way that the inside of the polygon is divided over my terrain grid, the resulting triangle mesh should be decomposed so that there are vertices at each grid point within the polygon. Example:

I'm thinking that a scan-line algorithm could work well, as per seidels trapizoidation algorithm - though modified so that extra internal points are generated as I traverse across the polygon.

Otherwise, a multi-phase approach could work where I first clip the polygon into vertical strips, inserting extra edge points at grid locations on those new vertical edges, and then triangulating each resulting polygon using one of my existing triangulation routines - but that feels awkward and in-efficient.

I also had another hairbrained idea where I start of with the polygon earclipped, and then detect and insert points from prominant terrain features into the mesh, splitting triangles as I go - but without a round of triangle improvement, the triangulation could get nasty.

Ultimately the number of points involved is not going to be insanely high, so I could be crude, but I'd like to 'do-it-right'.

You can assume that all polygons are concave, non-intersecting, and without holes. Any suggestions, and any approaches are welcome

Cheers,

Alex