How can I detect enclosed areas in an arbitrary set of overlapping lines

Question

I have game where there can be arbitrary lines, these lines can overlap. I want to find out first if there are any enclosed shapes created by overlapping lines, and then I want to fill the enclosed shape.

The best guess I have at doing this comes from this other post: determine if a set of tiles on a grid forms and enclosed shape. From what I can gather this would be, given a graph you can detect loops. However I can't quite figure out how to construct the graph from my data.

Is this a good way to go about solving this problem? And if so, any pointers on how I might get there given a list of collisions?

Answer 1

Hello and welcome to the site!

Here are some hindsights about how to construct a graph from your data:

• The collisions are the nodes of your graph.
• Each collision is bound to at least two lines (the two crossing, making the collision).

Then, each node is connected to all the others node having a line in common.

For example, the top collision in your image (let's call it Node A) is bound to the two green lines. On the left green line, there's another collision (Node B) with a pink line ; same thing on the right green line and another pink line (Node C). So we can start to build the graph with Node A being linked to Node B and Node C, since both of these two share a line with Node A (respectively the left and green ones). However, there is not link between Node B and Node C since they don't share a line.
Now do the same with your other collisions, then apply the graph magic from the other post, and you're done!