curve_intersection module
This is a collection of procedures and types for computing intersections between two Bézier curves in \(\mathbf{R}^2\).
Procedures

void BEZ_bbox_intersect(const int *num_nodes1, const double *nodes1, const int *num_nodes2, const double *nodes2, BoxIntersectionType *enum_)
Determine how the bounding boxes of two Bézier curves intersect.
 Parameters:
num_nodes1 (const int*) – [Input] The number of control points \(N_1\) of the first Bézier curve.
nodes1 (const double*) – [Input] The actual control points of the first curve as a \(2 \times N_1\) array. This should be laid out in Fortran order, with \(2 N_1\) total values.
num_nodes2 (const int*) – [Input] The number of control points \(N_2\) of the second Bézier curve.
nodes2 (const double*) – [Input] The actual control points of the second curve as a \(2 \times N_2\) array. This should be laid out in Fortran order, with \(2 N_2\) total values.
enum (BoxIntersectionType*) – [Output] The type of intersection between the bounding boxes of the two curves.
Signature:
void BEZ_bbox_intersect(const int *num_nodes1, const double *nodes1, const int *num_nodes2, const double *nodes2, BoxIntersectionType *enum_);

void BEZ_curve_intersections(const int *num_nodes_first, const double *nodes_first, const int *num_nodes_second, const double *nodes_second, const int *intersections_size, double *intersections, int *num_intersections, bool *coincident, Status *status)
Compute the intersection points of two Bézier curves in \(\mathbf{R}^2\). Does so by subdividing each curve in half and rejecting any pairs that don’t have overlapping bounding boxes. Once each subdivided segment is close enough to a line, this uses Newton’s method to compute an accurate intersection.
Each returned intersection point will be a pair \((s, t)\) of the parameters that produced the intersection \(B_1(s) = B_2(t)\).
Tip
If the
status
returned isINSUFFICIENT_SPACE
that meansintersections_size
is smaller thannum_intersections
. In that case,intersections
needs to be resized and the procedure must be invoked again.To avoid false starts occurring on a regular basis, keep a static workspace around that will continue to grow as resizing is needed, but will never shrink.
Failed invocations can be avoided altogether if Bézout’s theorem is used to determine the maximum number of intersections.
 Parameters:
num_nodes_first (const int*) – [Input] The number of control points \(N_1\) of the first Bézier curve.
nodes_first (const double*) – [Input] The actual control points of the first curve as a \(2 \times N_1\) array. This should be laid out in Fortran order, with \(2 N_1\) total values.
num_nodes_second (const int*) – [Input] The number of control points \(N_2\) of the second Bézier curve.
nodes_second (const double*) – [Input] The actual control points of the second curve as a \(2 \times N_2\) array. This should be laid out in Fortran order, with \(2 N_2\) total values.
intersections_size (const int*) – [Input] The size \(S\) of
intersections
, which must be preallocated by the caller. By Bézout’s theorem, a hard upper bound is \(S \leq (N_1  1)(N_2  1)\) (since the degree of each curve is one less than the number of control points).intersections (int*) – [Output] The pairs of intersection points, as a \(2 \times S\) array laid out in Fortran order. The first
num_intersections
columns ofintersections
will be populated (unless the array is too small).num_intersections (int*) – [Output] The number of intersections found.
coincident (bool*) – [Output] Flag indicating if the curves are coincident segments on the same algebraic curve. If they are, then
intersections
will contain two points: the beginning and end of the overlapping segment common to both curves.status (Status*) –
[Output] The status code for the procedure. Will be
SUCCESS
on success.INSUFFICIENT_SPACE
ifintersections_size
is smaller thannum_intersections
.NO_CONVERGE
if the curves don’t converge to approximately linear after being subdivided 20 times.An integer \(N_C \geq 64\) to indicate that there were \(N_C\) pairs of candidate segments that had overlapping convex hulls. This is a sign of either roundoff error in detecting that the curves are coincident or that the intersection is a nonsimple root.
BAD_MULTIPLICITY
if the curves have an intersection that doesn’t converge to either a simple or double root via Newton’s method.
Signature:
void BEZ_curve_intersections(const int *num_nodes_first, const double *nodes_first, const int *num_nodes_second, const double *nodes_second, const int *intersections_size, double *intersections, int *num_intersections, bool *coincident, Status *status);

void BEZ_newton_refine_curve_intersect(const double *s, const int *num_nodes1, const double *nodes1, const double *t, const int *num_nodes2, const double *nodes2, double *new_s, double *new_t, Status *status)
This refines a solution to \(F(s, t) = B_1(s)  B_2(t)\) using Newton’s method. Given a current approximation \((s_n, t_n)\) for a solution, this produces the updated approximation via
\[\begin{split}\left[\begin{array}{c} s_{n + 1} \\ t_{n + 1} \end{array}\right] = \left[\begin{array}{c} s_n \\ t_n \end{array}\right]  DF(s_n, t_n)^{1} F(s_n, t_n).\end{split}\] Parameters:
s (const double*) – [Input] The first parameter \(s_n\) of the current approximation of a solution.
num_nodes1 (const int*) – [Input] The number of control points \(N_1\) of the first Bézier curve.
nodes1 (const double*) – [Input] The actual control points of the first curve as a \(2 \times N_1\) array. This should be laid out in Fortran order, with \(2 N_1\) total values.
t (const double*) – [Input] The second parameter \(t_n\) of the current approximation of a solution.
num_nodes2 (const int*) – [Input] The number of control points \(N_2\) of the second Bézier curve.
nodes2 (const double*) – [Input] The actual control points of the second curve as a \(2 \times N_2\) array. This should be laid out in Fortran order, with \(2 N_2\) total values.
new_s (double*) – [Output] The first parameter \(s_{n + 1}\) of the updated approximation.
new_t (double*) – [Output] The second parameter \(t_{n + 1}\) of the updated approximation.
status (Status*) –
[Output] The status code for the procedure. Will be
Signature:
void BEZ_newton_refine_curve_intersect(const double *s, const int *num_nodes1, const double *nodes1, const double *t, const int *num_nodes2, const double *nodes2, double *new_s, double *new_t, Status *status);

void BEZ_free_curve_intersections_workspace(void)
This frees any longlived workspace(s) used by
libbezier
throughout the life of a program. It should be called during cleanup for any code which invokesBEZ_curve_intersections()
.Signature:
void BEZ_free_curve_intersections_workspace(void);
Types

enum BoxIntersectionType
This enum is used to indicate how the bounding boxes of two Bézier curves intersect.

enumerator INTERSECTION
(
0
) The bounding boxes intersect in a rectangle with positive area.

enumerator TANGENT
(
1
) The bounding boxes are tangent, i.e. they intersect at a single point or along an edge and the region of intersection has zero area.

enumerator DISJOINT
(
2
) The bounding boxes do not touch at any point.

enumerator INTERSECTION