Detecting all the shapes formed by intersecting lines

[Raums]

Hi All,
I have a series of overlapping lines forming multiple closed areas. I want to take all these lines and generate separate shapes for each area they form. What would be the best way to go about this? Below is an example image.

[kll]

i understand your thinking comes from a paint program where you can select the
“fill” brush and click on a CLOSED “area” defined by several line segments,
and it fills it.

i not say it would be impossible, but
generally: Processing does not work that way.

so, if i see that correct ( and also judge your knowledge status correctly )
even if someone here give you a solution
( like pixel color compare… / and pix color overwrite )
you might not understand it, so it could be just wasted time for all.

to get a better idea i would like you to post your processing code
you made the above picture with,
so we might see if there could be a reasonable next step.

[Raums]

I know it doesn’t work that way, but I figured this is a problem that someone must have come across before. I can’t post the full program as it’s 1500 lines long, but each line on the screen is stored as a line object which is a set of coordinates (c1 and c2). Pixel color compare wouldn’t be ideal as I assume that would lead to inaccuracies in the exact coordinates given for the shape. I’m fairly certain there’s a way to do this, (after all, I have the lines and can detect intersections) but I wanted to see if anyone had any ideas before I sunk several hours into figuring it out.

[kll]

ok, let’s say you make
one line,
make a second line and check on collision ( with all other lines )
http://jeffreythompson.org/collision-detection/line-line.php ,
AND remember in a array:
line ‘a’ (xa0,ya0,xa1,ya1) , ‘b’ (xb0,yb0,xb1,yb1) , intersectionX, intersectionY

for all your lines,

but what idea you have to define, with all that info in an array,
what intersection points do build a SHAPE?
i would think you must find what are CLOSED SHAPEs
like start on any intersection point, follow a line to next intersection point,
now follow the intersecting line ?clock wise?..
and if you end up at the same point, it is a closed shape!
feed all involved intersection points to a vertex shape ( and fill it for show )

but no idea how to check if you missed a shape?

---

so you do not want to invest 20 min to cut down your 1500 lines
to ?20? lines to have a good
MCVE (Minimal Complete Verifiable Example)
just for this challenging question?

so others might be inclined

• to step in and
• play with it and
• test their own ideas on it?

that might be your loss

---

[jeremydouglass]

If you want to do this geometrically, here is one approach:

1. a Line is a list of xy tuples (or PVectors).
2. for each line, create a Line containing two points, and add it to the lines list
3. detect intersections by doing line-line collision on each pair (itertools.combinations)
4. store each intersection point found in the line list. Include a third term in the tuple – the id of the line it intersects. This gives your lines a lightweight graph property.
5. when done adding all intersections, sort each Line list by x,y.
6. Create a Walker class object, which has a current heading and can store a list of visited points.

Now loop over your point set and run a walker on each point twice.

results = []
for point in set(itertools.chain_from_iterable(lines)):
    for heading in [PI, TWO_PI]:
        walker = Walker(point, heading)
        shape = walker.run()
        if shape:
            results.append(shape)

Here is what the walker does to find a closed shape:

1. change heading:
   • if there is one neighbor point, change heading toward that point
   • if there are two neighbors, check their angle from current heading, then change heading to match to the closest one e.g. clockwise (right hand maze walking rule)
2. advance to next point on the line
3. save that point
4. if the point==origin point then return shape (DONE)
5. elif the point is not an intersection, return None (DONE)
6. switch to the point on that other line. continue from 1

Give the walker a shape() method that returns a canonically ordered tuple of its points. Many of your walkers will discover the same shapes, but when added to a set this will not matter – as long as they are canonically ordered.

shapes = set() 
for walker in walkers:
    set.add(walker.shape())
print(shapes)

For example, walker.shape could choose the leftmost-then-topmost point as the beginning, and rotate the list (slice / concat) so that point is first before converting to a tuple and returning.

The approaches above are based on your image and assume no intersections are shared by more than 2 lines – although those could be accommodated by making the line jumping decision more complex.