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)?

enter image description here

  • 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

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:
enter image description here

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.

|improve this answer|||||

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.

|improve this answer|||||
  • 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
  • 1
    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

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

|improve this answer|||||
  • 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.

|improve this answer|||||
  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.