Algorithm to find individual, closed groups of lines in a large set of connected lines

Question

I'm currently trying to write an algorithm that can find individual groups of connected lines within a larger set of lines. The images below should explain this a bit more clearly.

In the first image you can see a set of lines. What I'm trying to do is split those lines into 3 groups, as seen in the second image. The red and green groups share a line.

I can assume that each line has a start and an end coordinate, and each line can belong to one or more groups.

I'm currently trying to write a recursive function that follows each line until it reaches an end point with one or more lines it can follow. At this point the function recalls itself until it's followed the lines back round to the split point. However this is proving unsuccessful.

The output of this example, as shown in the second image, should be 3 separate groups of lines, stored in a list. I'm currently using c#, however I should be able to use a suitable algorithm in any language, including pseudocode. I know there must be an algorithm that can achieve this, however I cannot seem to work it out or find it online.

Answer 1

Assuming you essentially want to partition the 2D space into pieces using the given lines and border where

• no two pieces overlap
• all pieces sum to the original space
• all the pieces primitive i.e. can not be split further

Consequently, there is a nice property that each line that actually border a polygon will be between exactly 2 polygons. This is more apparent when thinking about the notions of dual graph of plane graph

Note the outer partition piece formed with the border of the whole picture.

Algorithm

Initialise

Each line has 2 pointer to be pointed to the partition it borders (red dot). These pointer are initialised to empty. Our algorithm terminates when all of these pointers are non empty.

Main

1. Pick a line with at least one still empty partition pointer.
2. Walk along the adjacent edge that makes the least angle from the side of the line that still has a free pointer. (do remember the properties of vector's cross product and dot product. These will be your tools in calculating the angle and determining the side.)
3. [If there is no adjacent line to walk at all, you need to mark the current line as not being part of any polygon and backtrack]
4. Once you complete a cyclic walk, update all the "sides" used and point them to a newly created "partition" object.
5. Repeat step (1) until all lines has been assigned 2 pointers to its bordering partition. (except if that line is marked as not a part of any polygon or is the border of whole picture.)

Answer 2

Here is an idea - something to start with.

A good first step is to use BFS/DFS (on the edges) to find the connected components of your diagram - in your case there are two. From now on we consider a single connected component.

Given a component and an edge, find a way to determine which direction is "in" and which is "out". For example, if you shoot a ray in the perpendicular direction, "in" is the direction which hits an odd number of edges on its way to infinity. Run flood fill in this direction. This should give you one shape. Find another edge which is not adjacent to a shape (if any), and repeat. Eventually you will have found all shapes.