I am working on a strategy game that has the 'province' aspect (selectable regions), but want to use terrain underneath the provinces.

Say, I have a heightmap of the Earth. Under a simple concept, each pixel represents a quad (two triangles). A province could be drawn anywhere on this heightmap using vertices that are connected. Provinces would not be guaranteed to be convex. There could be any number of vertices within any pixel. Now, to generate a height-accurate border, you would obviously add vertices along the drawn border at every intersection point between pixels. The issue then becomes: how do I generate the geometry -within- the drawn border that would match the underlying heightmap? Basically, I want to cut a 'slice' out of the terrain based on given edges for the slice.

What would be the best way to do this?