Interval Spline Inclusion

Given two interval splines and , we want to determine if . Figure 4 gives an example where this is true, and defines our notation.

First, note that if corresponding control points of the three splines of the interval spline are collinear, then so are corresponding points on the spline curve (e.g., , , and ). To determine inclusion, we sample as finely as necessary across the interval . At each sample point, , we determine the line, , passing through ,, and . We then intersect with the interval and obtain ,, and . If , , and lie between and , then at .

This requires a method to intersect a line with the interval . This intersection is done with a divide and conquer algorithm, checking the sign of (while watching for 0):

where, , , and , is a point on the spline. To avoid multiple solutions, the process begins around the closest points to the center point of the nominal interval with a change of sign.

However, as can be seen in Figure 5, interval splines don't necessarily begin or end at the same time. So, once the former algorithm fails (as well as the first time it succeeds), it is necessary to check that the process is actually on one ending of the common piece of curve. It is necessary to check - on the whole spline - that 2 consecutive points are on the same part of the first interval to fail. That can be done by looking at a determinant:

If you consider the 2D point (x,y) to be the same as the 3D point (x,y,0), then the last coordinates of the cross products and will be of the same sign if and only if the 2 points at the end of and are on the same side of the plane . This implies that the 2D determinants and have the same sign.