Polygons from line segments

Question

I have a list of line segments in no particular order.

I want to find all enclosed spaces (polygons) formed by the segments. Is there an efficient algorithm or method that I could use to do this?

The following image illustrates the problem. How can I detect the green polygons, given the black line segments?

Levitt

Answer 1

One way would be to build a graph as follows:

• the nodes are the intersection points of the edges

• there's an edge between nodes i and j iff points i and j are on the same edge

Once you've built the graph:

• Run the Connected Components Algorithm on it, and check for connected components of size > 2

• Run a convex hull algorithm on the intersection points within such a component

Edit modified from original due to excellent point by FooBar.

Gammy

One edge case for the connected Components would be an edge that divides an area (so that it is part of several connected components). – Filiation

And what is the goal of the convex hull step? What happens for a non convex area? – Filiation

@FooBar That's a question for the OP, I think. – Gammy

If theres 2 squares apart that share a line your algorithm would construct big rectangle instead of 2 squares. – Cultured

using bi-connected components instead seems to work – Cultured

@photon I agree that it seems that bi-connected components seems better. In the shown graph all the green areas seem to be part of the same connected component, but split into three different bi-connected components. – Epigoni

Answer 2

This is indeed a classical problem in computational geometry.

Your are looking for the faces of an arrangement of your segments.

For a discussion of this topics with (too many) details, and source code, there is this wonderful library: CGAL .

Note that you'll have to decide what you do for e.g. a polygon inside another, many polygons intertwined, etc.

Mcwhorter

Answer 3

Ami's answer is a good pointer in the correct direction, but here are the more detailed steps you might need to know about:

1. Take the list of line segments and build a collection of vertexes. Since check each individual segment for intersections with each other segment is basically a N^2 operation when done via brute force, you might want to build a quad-tree and use that to reduce the number of checks you are performing. If n is small or you have a lot of cpu time to burn, just brute force it, otherwise you need to be clever about your collision detection. Here is a library that implements quad-tree collision detection: https://github.com/hroger1030/SpatialTrees

2. With your list of nodes and edges, you have the pieces to build a graph. you can call your lines nodes and the intersections the edges or vice-versa, it kind of doesn't matter. The important thing is you can now just go find all the cycles on the graph where the number of nodes in the cycle > 2.

I just so happens that I wrote an implementation of Tarjan Cycle detection in c#: Tarjan cycle detection help C#. This might be an alternative to the suggested Connected Components Algorithm.

Garlan

Once you have identified it? I have no idea, I don't know what you are going to do with it once you have identified it. You need to figure that out, there are many ways to represent polygons. – Garlan