To verify that one interval spline is inside another, the following three
steps are used:: Putting the parameters of the 2 splines together:
We want to ensure that for all the two corresponding intervals are on the same line
(resp. in the same plane, for ellipses). We implement a divide and conquer
algorithm, using the sign of:
or (in the 3D case)
Those two determinants are the equations of the lines (or the plane where
the ellipse lies) that correspond to one interval spline, thus the algorithm
cuts the second interval spline to redefine it (the determinant
utilizes the initial points used to define the first interval spline at the beginning).
So there is no need to have two interval splines of same degree at the beginning, since the
second one is completely rebuilt (with the same degree, and control points
on the same line or plane as the first interval spline). See figure 3 where cuts the interval spline
in
,
and
to
define a new interval: with classical methods, that have to be done (see [6]).
: Compare as many intervals as possible.
Now that the intervals came together, this part is computable in O(n)
where n is the number of points on a spline (resp. ellipses). When
fails, check if it's an ending:
If not, then the inclusion fails. This check has to be made as both splines do not
necessarily begin or end at the same time.
To check an ending, the methods in 2D and 3D are very similar. The method
utilizes the fact that the sign of the determinant of vectors gives
the orientation of such a frame - when it is compared to the canonic frame.
Hence, comparing two determinants can decide whether two points are on the
same side of a line or a plane. See figure 4 for the 2D vectors.
For example, in 2D you compare the signs of and
.
A same sign means the points are on the same side.