Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

4 Answers 4

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.

share|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
    
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
add comment

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.

share|improve this answer
add comment

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

share|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
add comment
up vote 0 down vote accepted

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.

share|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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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