3
$\begingroup$

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.

Connected lines before

Groups of lines after

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.

$\endgroup$
1
$\begingroup$

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

enter image description here

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.)
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Joe Morgan Sep 8 '17 at 8:55
  • $\begingroup$ 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. $\endgroup$ – Apiwat Chantawibul Sep 8 '17 at 19:22
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ As you described, the parity of intersection an outwards ray method is standard for determining whether a point is inside or outside a cyclic sequence of points forming a polygon. However, care has to be taken since a connected component isn't necessarily a single closed polygon. $\endgroup$ – Apiwat Chantawibul Sep 7 '17 at 14:25
  • $\begingroup$ Perhaps one should find an edge such that the entire component lies on one of its sides. $\endgroup$ – Yuval Filmus Sep 7 '17 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.