7

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.

alt text

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

Glorfindel
  • 21,988
  • 13
  • 81
  • 109
devongovett
  • 4,850
  • 5
  • 34
  • 35

4 Answers4

9

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

Quasimondo
  • 2,485
  • 1
  • 22
  • 30
0

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.

  • 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. – devongovett Jun 19 '10 at 23:31
  • @devongovett: My suggestion is that you add that information to the question. – Alceu Costa Jun 20 '10 at 00:41
  • So your problem is to find the intersection between lines defined by javascript canvas drawing commands and a straight line. –  Jun 20 '10 at 00:56
0

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.

Seth
  • 45,033
  • 10
  • 85
  • 120
0

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:

The intersection point between a spline and a line

Community
  • 1
  • 1
Hamish Grubijan
  • 10,562
  • 23
  • 99
  • 147