BezierInfo-2/docs/chapters/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:

1. Take two curves C₁ and C₂, and treat them as a pair.
2. If their bounding boxes overlap, split up each curve into two sub-curves
3. 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).
4. For each pair, check whether their bounding boxes overlap.
5. If their bounding boxes do not overlap, discard the pair, as there is no intersection between this pair of curves.
6. If there is overlap, rerun all steps for this pair.
7. 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. You can also change the value that is used in step 5 to determine whether the curves are small enough. Manipulating the curves or changing the threshold will reset the algorithm, 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

Finding self-intersections is effectively the same procedure, except that we're starting with a single curve, so we need to turn that into two separate curves first. This is trivially achieved by splitting at an inflection point, or if there are none, just splitting at t=0.5 first, and then running the exact same algorithm as above, with all non-overlapping curve pairs getting removed at each iteration, and each successive step homing in on the curve's self-intersection points.