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

• Pick a line with at least one still empty partition pointer.

• 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.)

• [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]

• Once you complete a cyclic walk, update all the "sides" used and point them to a newly created "partition" object.

• 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.)

StackExchange Computer Science Q#80980, answer score: 3