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.
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.
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.
ok, let’s say you make
make a second line and check on collision ( with all other lines )
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
If you want to do this geometrically, here is one approach:
- a Line is a list of xy tuples (or PVectors).
- for each line, create a Line containing two points, and add it to the
- detect intersections by doing line-line collision on each pair (itertools.combinations)
- 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.
- when done adding all intersections, sort each Line list by x,y.
- 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:
- 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)
- advance to next point on the line
- save that point
- if the point==origin point then
- elif the point is not an intersection,
- 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.