Detecting all the shapes formed by intersecting lines

Processing.py
5

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.

2 Likes