Geometric Curve Intersection

The problem of intersecting two curves is a difficult one in computational geometry. The Curve.intersect() method (when using the GEOMETRIC strategy) uses a combination of curve subdivision, bounding box intersection, and curve approximation (by lines) to find intersections.

Bounding Box Predicate

Rather than directly trying to find intersection points between curve-curve pairs, an predicate check is used to rule out pairs that are “too far” to intersect.

Since the Bernstein weights are non-negative (when \(s \in \left[0, 1\right]\)) and sum to \(1\), a planar Bézier curve can always be found within the polygon formed by the convex hull of the control points. By similar logic, the curve will also be contained in the bounding box defined by the extreme values in the \(x\) and \(y\) directions, and this bounding box is much simpler to compute than the convex hull.

An intersection check between two bounding boxes amounts to checking if the intervals overlap in each of the \(x\) and \(y\) directions, whereas arbitrary convex polygon intersection is much more involved (though the Sutherland-Hodgman clipping algorithm exists) and the \(x\) and \(y\) components are not independent. In order to eliminate pairs of curves that are guaranteed not to intersect, a bounding box predicate can be used.

../_images/bounding_box_predicate.png

As we can see from the middle column, this predicate may produce some false positives, but is a cheaper alternative to a convex hull intersection predicate:

../_images/convex_hull_predicate.png

Curve Subdivision

If the bounding boxes for a pair of curves are not disjoint, each curve \(\mathcal{C} = b\left(\left[0, 1\right]\right)\) is split into two halves by splitting the unit interval: \(b\left(\left[0, \frac{1}{2}\right]\right)\) and \(b\left(\left[\frac{1}{2}, 1\right]\right)\):

../_images/subdivide_curve.png

The subdivision process continues to use a simple tool (the bounding box predicate) to narrow in on pairs of subintervals where an intersection may occur:

../_images/subdivision_process.png

In cases where curves are almost parallel, the number of subdivided candidate pairs can become too large. When the number of candidates exceeds a certain threshold, we use the convex hull predicate instead to prune the number of pairs:

../_images/subdivision_pruning.png