intersection of two paths

Is there an easy way to calculate the coordinates of the intersections of two paths?

I know how to find out how two paths intersect using intersects, and I guess I could recursively break one of the paths down recursively and test each part, but that doesn't seem very efficient.

The implementation of intersects in graphics/cocoa.py looks like it uses intersects_path from Polymagic to figure out if the paths intersect. This function looks like:

static bool intersects_path(NSBezierPath* p1, NSBezierPath* p2) 
{ 
     NSRect        bbox = [p2 bounds]; 
     if ( NSIntersectsRect( bbox, [p1 bounds])) 
     { 
         // bounds intersect, so it's a possibility - find the intersection and see if 
              it's empty. 
         //return path_intersects_quick(p1, p2); 
         NSBezierPath* ip = path_intersection(p1, p2); 
         return ![ip isEmpty]; 
     } 
     else 
         return false; 
}

It looks to me as though the intersection points are calculated at that point and are counted to see if there are more than one. I would like to be able to get at this information in nodebox. Maybe it's already possible and I'm just missing something. If it isn't already implemented, I think that it would be a usefull addition to nodebox.

Sorry about the formatting. I forgot to close the code block.

Hi Patrick,

The only way I know of is by brute force: checking if each point on a path falls within the confines of another path. However, this does not necessarily mean it takes ages to calculate. The Bezier Editor library has similar code (native Python) that is fast enough to run in an interactive animation.

Below are some rough algorithms you may find interesting:

nofill()
stroke(0)
p1 = oval(100, 100, 200, 200)
p2 = oval(100, 200, 200, 200)
 
def overlap(from_path, in_path, precision=100):
    """ Returns a list of points along from_path that fall inside in_path.
    """
    points = []
    if precision == None:
        # Traverse the points in the Bézier-path.
        rng = list(from_path)
    else:
        # Interpolate new points for better precision:
        # this is nice because each point is a curve element with handles,
        # we could use them to construct a smooth new path for example.
        rng = from_path.points(precision)
    for pt in rng:
        if in_path.contains(pt.x, pt.y):
            points.append(pt)
    return points
 
def intersection(path1, path2, precision=100):
    # XXX - this is only an quick example!
    # To return a "real" new path from the intersection,
    # it needs more work at the point where the overlap from path1
    # transgresses into the overlap from path2.
    # You'll see some strange things as you move the oval around.
    o1 = overlap(path1, path2, precision)
    o2 = overlap(path2, path1, precision)
    horizontal = lambda pt1, pt2: int(pt1.x-pt2.x)
    o1.sort(horizontal)
    o2.sort(horizontal)
    o2.reverse()
    points = o1 + o2
    if len(points) > 0: 
        points[0].cmd = MOVETO
    return points
 
fill(1, 0, 0)
nostroke()
pts = overlap(p1, p2)
for pt in pts:
    oval(pt.x-2, pt.y-2, 4, 4)
 
fill(0, 0.2)
drawpath(intersection(p1, p2))

PS. I fixed the code block so your post gets displayed correctly.