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 is INSUFFICIENT_SPACE that means intersections_size is smaller than num_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 pre-allocated 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 of intersections 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 if intersections_size is smaller than num_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 round-off error in detecting that the curves are coincident or that the intersection is a non-simple 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
- SUCCESS on success.
- SINGULAR if the computed Jacobian \(DF(s_n, t_n)\) is singular to numerical precision.

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 long-lived workspace(s) used by libbezier throughout the life of a program. It should be called during clean-up for any code which invokes BEZ_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.