Generate polygons from a set of intersecting lines

Well, we put an answer here which is not a complete answer to our question, that is, the question will remain "open for answering". It is however a solution for the problem in the question. Here is the trick we used:

First let see the results:

So the given lines in the left built polygons shown in the middle. They are real polygons as shown in the right;)

For the algorithm given below we used Shapely package in Python.

• lines ==> MultiLineString {:: M}
• add a tiny buffer, say eps {:: MB}
• region ==> Polygon {:: P} (region here is a square)
• P.difference(MB) {resulting polygons}

Note that it is quiet fast in operation. However, the missing point is that the algorithm is not an original method for building polygon from lines. Nevertheless it worked perfectly for the problem we had in our hand.

JTS Topology Suite has a Polygonizer class, which pretty much does this.

You could have a look at the source code, available here, and convert that to Python.

You might take a look at the Python Shapely package, particularly polygonize()