11

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

1
  • Is the Outer square boundary known, or is that too, to be read from the input lines? Apr 17, 2013 at 8:50

6 Answers 6

7

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.

5

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.

3
  • 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, 2013 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. Apr 17, 2013 at 13:28
  • To help others (since it took me a while to find...): To split lines at points of intersection in JTS use one of the implementations of org.locationtech.jts.noding.Noder.
    – micycle
    Aug 8, 2021 at 20:48
3

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

2
  • 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, 2013 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, 2013 at 5:16
2

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.

1
  • 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, 2013 at 23:27
0

Building on @Developer's answer and assuming your set of intersecting lines is stored in .geojson format, here is the solution using Shapely:

import geopandas as gpd
import json
from shapely.geometry import shape, MultiLineString
import pandas as pd

with open("lines.geojson") as f:
    features = json.load(f)["features"]

## Get all 'LineString' objects
lines = [x for x in features if x['geometry']['type'] == 'LineString']
## Convert to 'MultiString'
lines = MultiLineString([shape(feature["geometry"]) for feature in lines])
## Convert Lines to Polygons by applying a tiny buffer
lines = lines.buffer(0.0000000000001)
## Get outer boundary of the lines as a polygon
boundary = lines.convex_hull
## Get a difference to generate a multipolygon
multipolygons = boundary.difference(lines)
## Export individual polygons:
polygons = pd.DataFrame(list(multipolygons), columns =['geometry'])
polygons = gpd.GeoDataFrame(polygons, geometry='geometry')
polygons.to_file("polygons.geojson", driver="GeoJSON")
0

I've tested shapely's polygonize and it seems to correctly identify all the polygons when lines are split at their intersections.

A simple solution for this problem that yields completely accurate polygons is to:

  1. Create a spatial index for each LineString
  2. Iterate over each line in the region of interest
  3. Find all other lines that intersect with the line from 2.
  4. Find the points of intersection between the line from 2. and the lines from 3.
  5. Sort the points by x1 breaking ties on y1
  6. Create new lines by iterating over adjacent points from 4.

This produces the previously mentioned "split lines" which can then be fed to shapely's polygonize method.

One advantage of this method over using buffer and difference as instructed in Developer's answer is that this method will also find polygons created from 4 lines that create a rectangle whereas the previous method does not for some reason unknown to me.

I'm not sure of the computational complexity of this but I can't see that it would be more than the other methods mentioned. I think polygonize is likely using backtracking and branching to construct the polygons by looking to see what points on other lines overlap with the current point of interest.

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.