# Solve for the intersection point, given two sets of data

I need to (numerically, specifically in C++) solve for the intersection point of two curves, f(x) and g(x). I am given two sets of data, one for each curve (eg. {($x_1$,f($x_1$)),($x_2$,f($x_2$)),($x_3$,f($x_3$))....} and {($x_4$,g($x_4$)),($x_5$,g($x_5$)),($x_6$,g($x_6$))....}). The intersection point lies outside of the two sets, and none of the $x_i$ values in "f-set" are in "g-set" (excuse the wording). The solution therefore involves some iterative loop of (a) extrapolation to a guess $x_n$ and calculating $f(x_n)$ and $g(x_n)$, and (b) checking some relation between these two values to see if $x_n =$ or $>$ or $< x_{intersection}$.

If you like, you can visualize this problem as follows: you are given points on two sides of a triangle, and you would like to extrapolate these points to find the corner point. However, in general, the curves $f$ and $g$ are not straight lines.

Could you please walk me through the methods used to solve this problem?

-
Where did these points you have come from? One could certainly use piecewise polynomials to represent your two curves, but depending on the provenance of your points, there might be a more natural way to interpolate them... – J. M. Jul 10 '12 at 4:05
The visualization I provided is actually quite close to where they came from, but as stated, the sides of the triangle are not straight. Consider laying the "triangle" on side, with the point up. Given points on the "bottom edge" of the triangle, I "evolve" them upwards and can solve for where the top left/right edges are. I need to use some extrapolation method from these edges points to solve for the top point. Thanks – Kurt Jul 10 '12 at 4:10
I suppose you could start with building an interpolating Bézier curve from your points. The convenience of this is that there are a number of efficient algorithms for finding the intersection points of two Bézier curves... – J. M. Jul 10 '12 at 4:16
Do you have some underlying model for the data that would suggest a form for the extrapolation? – copper.hat Jul 10 '12 at 4:28
Unfortunately, no. The shapes are generally smooth, but could really be anything. I guess I could just try a cubic spline, but then what is an efficient method to solve for the intersection of two cubic splines? – Kurt Jul 10 '12 at 5:36