CODEWITHSUNDEEP
algorithmgeometry
Rook
Rook

Reputation: 62538

Finding an intersection between something and a line

I have a set of points which are interpolated with an unknown method, or to be more precise, the method is known but it can be one of the several - it can be polynomial interpolation, spline, simple linear ... - and a line, which, let's for now imagine it is given in the simple form of y = ax + b.

For interpolation, I don't know what method is used (i.e. the function is hidden), so I can only determine y for some x, and equally, x for a given y value.

What is the usual way to go about finding an intersection between the two?

Upvotes: 1

Views: 681

Answers (3)

Ilia K.
Ilia K.

Reputation: 4962

You have (an interpolation polynomial) f1(x) and (a line) f2(x) and you want to solve f(x) = f1(x)-f2(x) = 0. Use any method for solving this equation, e.g. Newton-Raphson or even bisection. This may not be the most optimal for your case. Pay attention to convergence guarantees and possible multiple roots.

Upvotes: 1

casablanca
casablanca

Reputation: 70701

Say your unknown function is y = f(x) and the line is y = g(x) = ax + b. The intersection of these curves will be the zeroes of Δy = f(x) - g(x). Just use any iterative method to find the roots of Δy - the simplest would be to use the bisection method.

Upvotes: 1

David Titarenco
David Titarenco

Reputation: 33396

Spline: bezier clipping.
Polynomial: Viète's formulas (to get the zeroes, I think).
Line: line-line.

Not a trivial question (or solution) under any circumstance.

Upvotes: 0

Related Questions