# Generate polygons from a set of intersecting lines

This is a simple and quite common question which has already been asked for different purposes (see this link and this too, for example), here, however, we are looking for not a software package but algorithms that we could try to implement say in Python.

So, as shown below a set of lines are mapped (they are already trimmed, BTW).
Algorithms/ideas to generate polygons (as red ones shown)?

-
Is the Outer square boundary known, or is that too, to be read from the input lines? – Devdatta Tengshe Apr 17 '13 at 8:50

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.

-
As the code description says it won't work as expected by the question author: "edges must be correctly noded; that is, they must only meet at their endpoints. The Polygonizer will run on incorrectly noded input but will not form polygons from non-noded edges" – Pablo Apr 17 '13 at 12:54
There is an operation within JTS for correctly splitting the Lines at vertices. Maybe the OP could look at that as well. – Devdatta Tengshe Apr 17 '13 at 13:28

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.

-

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

-
A quick note that polygonize in Shapely (`from shapely.ops import polygonize`) uses GEOS.Polygonize from GEOS. So this is a link where there is a link to a link ... :| – Developer Apr 18 '13 at 3:48
Our trials with `polygonize` wasn't successful at all. However thanks for reminding us `Shapely` with which we could find a solution (a trick, actually) as posted as an answer. – Developer Apr 21 '13 at 5:16

Here is another solution we could find.

Using `DCEL` we can make blocks from touching lines.

For Python there is a package {here}. It is a tiny implementation with some bugs. Nevertheless with some effort it can be used for this problem. Also note the following stages:

A pre-processing stage with which all intersections between lines are found. Then accordingly all lines are broken into segments at the interaction points. A list of intersection points and a list of associated edges are those needed for DCEL.

-
As this method is an original solution and gives much better performance compared to the other method in which `difference` operation is being used. – Developer May 8 '13 at 23:27