Need help with finding where curves intersect

Hi!

I have two lists with 20 2D-points each (X and Y).

From these, I need to extrapolate a third curve that points from curve 1 before the two curves intersect, and points from curve 2 after the two lines intersect. The problem is that with only 20 points, the accuracy is not enough to create a reliable third curve since I can't get the exact point where the two lines cross.

Is there some library that can help me with this? I was told to figure out the polynom for the curve to get an exact match that way, but that I find is overly complicated. Some kind of linear interpolation should be good enough.

Any thoughts? A really interesting problem, but I can't find an good solution. As for the accuracy, I think a 40 point curve should be good enough for this.

/H

A drawing that shows your problem would be most useful.

It's not hard to solve this problem in VB.Net without calculating a polynomial, and with reasonably high precision.

As a first approximation, you can check for straight line segment intersections between successive points on each line. I take it you already know how to do this, if not I can dig out some code somewhere. Here's how you get higher precision.

1. Define a Drawing2D.GraphicsPath for each line. Add the array of points in each line to the path with GraphicsPath.AddCurve. (This effectively calculates the polynomial for you, but you don't need it.)

2. Flatten each path with GraphicsPath.Flatten(Matrix, Flatness). This effectively turns the curve back into a polyline or polygon. The accuracy with which it does so depends on the Flatness argument: the smaller the value, the more precisely it follows the curve. The default Flatness value is 0.25, and for higher precision you could choose something like 0.05.

3. Now you can get an array of points (actually PointFs) for each line with the GraphicsPath.PathPoints property. And you can search for points of intersection between successive line segments using the normal method.

Of course, there's a trade-off between accuracy and speed. After flattening with 0.01, there will be a lot more points in the PathPoints than in the original curve, so a lot more calculations are needed. But that's what computers are good at.

Note: for the Matrix argument, you can use Nothing.

BB