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

Question

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

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

Answer 1

Without knowing how your graphics path is defined, it's impossible to answer your question with a concrete algorithm. There is a solution in this book on algorithms for straight line segments.

Answer 2

If you have the equations for everything, then you can do it (in theory). In practice, it's not so easy (especially not in the general case). This discussion has some good advice on intersecting lines and bezier curves.

Answer 3

You want to intersect a line and a "spline" x(t), y(t) which should be at most 4-th degree polynomial for both x(t) and y(t). You ed up solving equations, but yo do need to know all of the parameters. If solution is out of either range (line segment and spline segment have start and end) - discard it. Related q:

http://stackoverflow.com/questions/234261/the-intersection-point-between-a-spline-and-a-line

Answer 4

You might want to have a look at Kevin Lindsey's Javascript geometry library - it contains probably all the interesection algorithms you are looking for: http://www.kevlindev.com/geometry/index.htm