5

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?

How do find polygons (green) from line segments?

user366312
  • 16,949
  • 65
  • 235
  • 452
Tyson
  • 1,226
  • 1
  • 10
  • 33

3 Answers3

6

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:

Edit modified from original due to excellent point by FooBar.

Ami Tavory
  • 74,578
  • 11
  • 141
  • 185
  • One edge case for the connected Components would be an edge that divides an area (so that it is part of several connected components). – FooTheBar Jun 05 '15 at 07:53
  • 1
    And what is the goal of the convex hull step? What happens for a non convex area? – FooTheBar Jun 05 '15 at 14:01
  • @FooBar That's a question for the OP, I think. – Ami Tavory Jun 05 '15 at 14:15
  • If theres 2 squares apart that share a line your algorithm would construct big rectangle instead of 2 squares. – Photon Jul 18 '20 at 05:45
  • using bi-connected components instead seems to work – Photon Jul 18 '20 at 05:51
  • @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. – Hans Olsson Jul 20 '20 at 07:40
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.

One Lyner
  • 1,964
  • 1
  • 6
  • 8
1

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.

Dharman
  • 30,962
  • 25
  • 85
  • 135
Roger Hill
  • 3,677
  • 1
  • 34
  • 38
  • 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. – Roger Hill Jul 23 '20 at 21:48