This algorithm, generateFaces(), calculates and stores all the faces, and ran once at the beginning

A face won't be created if there is a stray edge poking into the polygon.

Face Finding Algorithm

Faces are found by walking down edges, and whenever reaching a node, always making the sharpest right turn, a face is found when you end up where you began.

To find the sharpest right turn, we need to sort adjacent edges by their angles.


After sorting the lines by angle, it's easy to find the next most right turn.

Along the way it's important to sum up the angles visited along the walk. Interior angles are right turns.

Since we know we are making right turns, if there are 4 angles of 270 degrees, we just walked around the outside of a perimeter of a square.