BezierInfo-2/components/sections/curveintersection/content.en-GB.md

Curve/curve intersection

Using de Casteljau's algorithm to split the curve we can now implement curve/curve intersection finding using a "divide and conquer" technique:

• Take two curves C₁ and C₂, and treat them as a pair.
• If their bounding boxes overlap, split up each curve into two sub-curves
• With C_1.1, C_1.2, C_2.1 and C_2.2, form four new pairs (C_1.1,C_2.1), (C_1.1, C_2.2), (C_1.2,C_2.1), and (C_1.2,C_2.2).
• For each pair, check whether their bounding boxes overlap.
  • If their bounding boxes do not overlap, discard the pair, as there is no intersection between this pair of curves.
  • If there is overlap, rerun all steps for this pair.
• Once the sub-curves we form are so small that they effectively occupy sub-pixel areas, we consider an intersection found, noting that we might have a cluster of multiple intersections at the sub-pixel level, out of which we pick one to act as "found" t value (we can either throw all but one away, we can average the cluster's t values, or you can do something even more creative).

This algorithm will start with a single pair, "balloon" until it runs in parallel for a large number of potential sub-pairs, and then taper back down as it homes in on intersection coordinates, ending up with as many pairs as there are intersections.

The following graphic applies this algorithm to a pair of cubic curves, one step at a time, so you can see the algorithm in action. Click the button to run a single step in the algorithm, after setting up your curves in some creative arrangement. The algorithm resets once it's found a solution, so you can try this with lots of different curves (can you find the configuration that yields the maximum number of intersections between two cubic curves? Nine intersections!)

advance one step

Self-intersection is dealt with in the same way, except we turn a curve into two or more curves first based on the inflection points. We then form all possible curve pairs with the resultant segments, and run exactly the same algorithm. All non-overlapping curve pairs will be removed after the first iteration, and the remaining steps home in on the curve's self-intersection points.