How to calculate the intersection points of a straight line and an arbitrary shape?

Question

Is there a way to geometrically calculate the intersection points of the line and an arbitrary graphic path? I know where all the lines and curves are in the way, and I use the HTML5 canvas element if that helps anyone. Basically, I have access to all canvas drawing commands and their arguments. For example, if the API was called using lineTo, then moveTo, then the arc I have all this information. Each API call is stored in an array. I have a path definition, I just want to find out where the line crosses the path. Below is an image showing an example of the points I need to find.

alt text http://cl.ly/3228b0e7ea32b172e960/content

Thanks for any help! Again, I would rather do it geometrically than a pixel if possible.

Answer 1

Perhaps you should take a look at the Kevin Lindsey Javascript geometry library - it probably contains all the search algorithms you are looking for: http://www.kevlindev.com/geometry/index.htm

Answer 2

Not knowing how your graphic path is determined, it is impossible to answer your question with a specific algorithm. There is a solution in this book about algorithms for straight line segments.

Answer 3

If you have equations for everything, then you can do it (theoretically). In practice, this is not so simple (especially not in the general case). There are some helpful tips on intersecting lines and bezier curves in this discussion.

Answer 4

You want to cross the line and the "spline" x (t), y (t), which should be no more than the 4th level of the polynomial for both x (t) and y (t). You have developed a solution to the equations, but you need to know all the parameters. If the solution is out of range (the line segment and the spline segment have a beginning and an end), discard it. Related q:

Intersection point between spline and line