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

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.

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.)
• thanks for the comment. Just to clarify a few things... Are 'sides', 'edges' and 'lines' the same things? I also don't really understand what you mean by the word 'pointer'? thanks @billiska Commented Sep 8, 2017 at 8:55
• One line has two sides. The term edge was mistakenly used, I meant the same thing as line there. For the word pointer, that is a programming analogy. Perhaps just think of there being two parallel (has same domain-codomain) functions from set of lines to set of partition. Sorry for the informal-ness. Will make it formal if I'm less busy. Commented Sep 8, 2017 at 19:22