I am trying to automatically "fill" all of the areas in my code that are completely enclosed by line(segment)s.
What I have is a grid of fixed size (x,y) in 2D space, and a list of lines, defined by their start- and end-points. These lines do not necessarily enclose a space.
What I am looking for is the area's shaded in the different colors of blue here (specifically their bounding points, as I'm trying to create meshes for these areas)
How could I go about algorithmically finding these areas?
The trick is to find complete circuits of intersecting line segments that define each area (polygon).
Let's assume the line segments are named with letters (A, B, C, ...).
I'd start by building a table that lets you find intersections by line segment.
A -> B
A -> C
A -> D
B -> A
C -> A
C -> D
D -> A
(In this example, ACD forms a triangular area, and B is just a stray line segment that happens to cross A.)
Pick a line segment, say A, and check its first intersection, which happens to be with line segment B. Now we start scanning B's intersections. B connects back to A, which completes a circuit, but there were only two steps, so it's not a valid area.
Since B has no more intersections, we backtrack and look at A's next intersection, which is with C. C's first intersection is with A, which completes a circuit, but it's only two steps, so it's not a valid area. But C's next intersection is D, and D's first intersection is A, which completes a three-step circuit, so now we have valid area, specifically a triangle. The area is defined by the points of intersections we used in our circuit: Pac, Pcd, Pda.
Once you've explored all the possible paths from A, you'd start again with B. Note that you'll find areas multiple times, so you have to filter out the duplicates. But you can't skip checking B altogether, because it might be an edge of another area that you haven't already found.