Divide self-intersecting polygon into simple polygons
A self-intersecting polygon induces a plane partition, which should be represented by some data structure. This structure should include at least three types of objects - vertices, edges and faces. The faces are what you are trying to construct.

This data structure is called DCEL and it usually represents both planar graphs - the original graph with vertices and edges (where intersection points are added as new vertices, and some edges are split), and a dual graph with polygonal faces as vertices. Each vertex in the original graph should refer to a list of adjacent edges (sorted by angle, yes) and each vertex in the dual graph should refer to a list of adjacent edges, forming its boundary. Edges are usually represented by two arcs with orientations, opposite to one another. In this case each arc is adjacent to exactly one face (including the exterior face), which normally lies "to the left" of it.

Having this data structure implemented you'll be able to calculate all the faces by finding proper cycles in the set of all arcs.