How to split a self-intersection polygon to multipolygon

Question

I would like to implement a Java method which can split a self-intersection polygon to multipolygon. Is there any API or algorithm to do? Thanks.

The following code uses JavaGeom API.

/**
 * Split a polygon by its intersection(s)
 * @param polygon
 * @return a list of splitted polygons, return itself if no intersection found.
 */
public List<Polygon2D> splitSelfIntersectionPolygon(Polygon2D polygon){
    List<Polygon2D> multiPolygon = new ArrayList<Polygon2D>();

    Polygon2D splittedPolygon = null;
    for(int i = 0; i < polygon.vertexNumber(); i++){
        //...
        multiPolygon.add(splittedPolygon);
    }

    return multiPolygon;
}

Answer 1

The overall algorithm might be as follows:

1. Find the points where the edges of original polygon intersect using Bentley–Ottmann algorithm
2. Split intersecting edges in their crossing points, and convert the original polygon in the graph having vertices in crossing points of degree 4 (or higher degree if more than 2 original edges meet in one point).
3. Сonstruct a minimal spanning tree of the graph and apply these answers to form loops in it, which will be the polygons forming multipolygon.