Split a self-intersecting polygon (code C)

Question

I want to split a self-intersecting polygon into simple polygons. I have edges and intersection points stored in a data structure (linked list).

So here is an example. I have a linked list with the x, y coordinates of the edges and the intersection points of the polygon. According to the polygon in this picture, it will be :: (1) → (2) → (3) ... → (7). What I'm trying to do is get the edges of simple polygons (triangles here). In this case :: 1,2,7 / 3,4,5 / 5,6,7.

Answer 1

I think Bentley-Ottman will be your best bet. There is a nice interactive visualization here . Another nice description here .