I am trying to make a 2D map editor, and while I can easily triangulating convex/concave polygons from articles I've read... I'm unsure how to make the jump to handling one with holes in it in practice. So far, I've read a paper that provides a method if connecting two visible vertices to slice it into a monotome polygon, but I get quite lost in practice when I have to polygonize the orangey-yellow area:



The only data I have (as you see above) is:
- The lines and their vertices
- Which side of the line is the 'front' which determines if a sector is being enclosed, or if they're all facing out and it makes a hole

There is no sector information at all, my goal is to use to construct the bounds for a sector.


1) How do I polygonize the colored area with all these holes? Just looking for the logic here, code isn't needed.
Flood filling is not an option since I'm dealing with floating point vertices.


2) How can I use the facing sides to determine if it's an enclosed sector or not?
Basically, how can I tell all the lines I'm tracing are facing inside.
An idea I had was adding up the angles of all the lines, and if the average is >180 degrees, it's facing outward. Is this thinking correct? Is there a better way?

You can use a library such as CGAL or use GLU's tessellators. The general approach seems to be to construct a Delaunay triangulation with all of the edges and then punch out the holes. As for determining what's in and what's out, use the winding order of the contour to determine whether or not it's adding or subtracting from the geometry.

I probably should have specified that I won't be using a library. I have to learn to code this fully on my own, I appreciate the links however.

So from research, one viable method for handling holes and polygons in holes can be done completely with this paper: http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf