def bezier_intersections(bez1, bez2, longer_length, tol=1e-8, tol_deC=1e-8):
    """INPUT:
    bez1, bez2 = [P0,P1,P2,...PN], [Q0,Q1,Q2,...,PN] defining the two
    Bezier curves to check for intersections between.
    longer_length - the length (or an upper bound) on the longer of the two
    Bezier curves.  Determines the maximum iterations needed together with tol.
    tol - is the smallest distance that two solutions can differ by and still
    be considered distinct solutions.
    OUTPUT: a list of tuples (t,s) in [0,1]x[0,1] such that
        abs(bezier_point(bez1[0],t) - bezier_point(bez2[1],s)) < tol_deC
    Note: This will return exactly one such tuple for each intersection
    (assuming tol_deC is small enough)."""
    maxits = int(ceil(1-log(tol_deC/longer_length)/log(2)))
    pair_list = [BPair(bez1, bez2, 0.5, 0.5)]
    intersection_list = []
    k = 0
    approx_point_set = ApproxSolutionSet(tol)
    while pair_list and k < maxits:
        new_pairs = []
        delta = 0.5**(k + 2)
        for pair in pair_list:
            bbox1 = bezier_bounding_box(pair.bez1)
            bbox2 = bezier_bounding_box(pair.bez2)
            if boxes_intersect(bbox1, bbox2):
                if box_area(*bbox1) < tol_deC and box_area(*bbox2) < tol_deC:
                    point = bezier_point(bez1, pair.t1)
                    if point not in approx_point_set:
                        approx_point_set.append(point)
                        # this is the point in the middle of the pair
                        intersection_list.append((pair.t1, pair.t2))

                    # this prevents the output of redundant intersection points
                    for otherPair in pair_list:
                        if pair.bez1 == otherPair.bez1 or \
                                pair.bez2 == otherPair.bez2 or \
                                pair.bez1 == otherPair.bez2 or \
                                pair.bez2 == otherPair.bez1:
                            pair_list.remove(otherPair)
                else:
                    (c11, c12) = halve_bezier(pair.bez1)
                    (t11, t12) = (pair.t1 - delta, pair.t1 + delta)
                    (c21, c22) = halve_bezier(pair.bez2)
                    (t21, t22) = (pair.t2 - delta, pair.t2 + delta)
                    new_pairs += [BPair(c11, c21, t11, t21),
                                  BPair(c11, c22, t11, t22),
                                  BPair(c12, c21, t12, t21),
                                  BPair(c12, c22, t12, t22)]
        pair_list = new_pairs
        k += 1
    if k >= maxits:
        raise Exception("bezier_intersections has reached maximum "
                        "iterations without terminating... "
                        "either there's a problem/bug or you can fix by "
                        "raising the max iterations or lowering tol_deC")
    return intersection_list
def bezier_intersections ( bez1 , bez2 , longer_length , tol = 1e-8 , tol_deC = 1e-8 ) : maxits = int ( ceil ( 1 - log ( tol_deC / longer_length ) / log ( 2 ) ) ) pair_list = [ BPair ( bez1 , bez2 , 0.5 , 0.5 ) ] intersection_list = [ ] k = 0 approx_point_set = ApproxSolutionSet ( tol ) while pair_list and k < maxits : new_pairs = [ ] delta = 0.5 ** ( k + 2 ) for pair in pair_list : bbox1 = bezier_bounding_box ( pair . bez1 ) bbox2 = bezier_bounding_box ( pair . bez2 ) if boxes_intersect ( bbox1 , bbox2 ) : if box_area ( * bbox1 ) < tol_deC and box_area ( * bbox2 ) < tol_deC : point = bezier_point ( bez1 , pair . t1 ) if point not in approx_point_set : approx_point_set . append ( point ) intersection_list . append ( ( pair . t1 , pair . t2 ) ) for otherPair in pair_list : if pair . bez1 == otherPair . bez1 or pair . bez2 == otherPair . bez2 or pair . bez1 == otherPair . bez2 or pair . bez2 == otherPair . bez1 : pair_list . remove ( otherPair ) else : ( c11 , c12 ) = halve_bezier ( pair . bez1 ) ( t11 , t12 ) = ( pair . t1 - delta , pair . t1 + delta ) ( c21 , c22 ) = halve_bezier ( pair . bez2 ) ( t21 , t22 ) = ( pair . t2 - delta , pair . t2 + delta ) new_pairs += [ BPair ( c11 , c21 , t11 , t21 ) , BPair ( c11 , c22 , t11 , t22 ) , BPair ( c12 , c21 , t12 , t21 ) , BPair ( c12 , c22 , t12 , t22 ) ] pair_list = new_pairs k += 1 if k >= maxits : raise Exception ( "bezier_intersections has reached maximum " "iterations without terminating... " "either there's a problem/bug or you can fix by " "raising the max iterations or lowering tol_deC" ) return intersection_list
INPUT:
    bez1, bez2 = [P0,P1,P2,...PN], [Q0,Q1,Q2,...,PN] defining the two
    Bezier curves to check for intersections between.
    longer_length - the length (or an upper bound) on the longer of the two
    Bezier curves.  Determines the maximum iterations needed together with tol.
    tol - is the smallest distance that two solutions can differ by and still
    be considered distinct solutions.
    OUTPUT: a list of tuples (t,s) in [0,1]x[0,1] such that
        abs(bezier_point(bez1[0],t) - bezier_point(bez2[1],s)) < tol_deC
    Note: This will return exactly one such tuple for each intersection
    (assuming tol_deC is small enough).