Determine the Intersection points of 2 splines

[Shapoor]

I have 2 sets of x,y points, from which I have created 2 splines. These lines intersect each other at a number of points. How can I determine these intersection points? As there are over 200 pairs of lines, each whose intersection points have to be calculated, I require a solution that executes very quickly.

Thanks,

Shaps

[francois-normandin]

Hi Shaps,

I'd consider making a high-order polynomial fit of the curves and then you could solve for intersecting points between any two curves. This could be fast but would require some good maths and matrix manipulation.

There are probably approximative methods that could work better, it just depends on the precision level you require for your application. Anyhow, a solution that works for any two splines can be extended to "n" lines pretty easily.

[Shapoor]

Hi, Thanks for your reply. Where can I learn more about matrix manipulation for this application?

Regards,

Shapoor

[francois-normandin]

You'll have to take a look at Solving Polynomial Equations.

If you're not mathematically inclined, you might want to find help on this one. Otherwise, I'd start with Mathworld. It's a great site for Maths and Physics questions.

The higher the order of your polynomial, the harder it is to solve.

You should consider a more brute-force approach if you don't need high precision. It depends on your application, but here I cannot offer advice.

Let's say you take the following approximations for your curves: (3rd order curves, very small chance of being perfect fit...)

1) ax^3+bx^2+cx+d = 0

2) a'x^3+b'x^2+c'x+d' = 0

The curves cross each other for each x that satisfy this equation: 

(a-a')x^3+(b-b')x^2+(c-c')x+(d-d') = 0

Now, the analytical solution to this can be taken from Wolfram Mathworld website and is not too complicated, but to solve for a 7th order curve... good luck!

All solutions will not necessarily fall within your data range, but if you want an approximative order for your equation, count the number of times each curve cross... and add a few orders!

As I said, it might need a brute-force approach. Good Luck.