Generate polygons from a set of intersecting lines

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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

Answer 6

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.