intersection of a closed-spline and a line

Question

given a closed piecewise polynomial spline and a line, what is the most efficient way to find the intersection(s) of the line and the spline?

each piece of the spline is given as:

$P_j(x)=\sum_{i=1}^k (x-b_j)^{k-i} c_{ji}$

where $k$ is the order for each polynomial, $j$ represents the number of pieces $j=1:L$, $b_j$ is the $j$th break, $c_{ji}$ is the coefficient.

I assume that the origin $[0,0]$ is inside the closed spline and the line always passes through the origin, hence $y=mx$.

As it can be seen in the following picture, the line passing through the origin intersects with the spline in 2 points that I am interested in. Is there a closed form solution for that?

Answer 1

Plug your spline equations into a line equation of the form $ax+by= 0$, and you will get a polynomial equation of degree $k-1$. The solutions of this equation are the parameter values on the spline where it intersects the line.

There is a closed-form solution only for the cases $k=2,3,4, 5$. But, even for the cases $k=4$ and $k=5$, the closed-form solutions are very complex and difficult to implement in floating-point arithmetic, so you might be better off with numerical methods.

None of this is related to the spline being closed -- the same approach works with splines that are either open or closed.

Tom Sederberg has written several papers comparing the reliability and efficiency of curve-curve intersection algorithms. You could start by looking up his paper on "Bezier clipping", or his notes here.