After writing a function to test intersections of a line to a polygon, another problem came up where I needed
to test an intersection of a line to a curve. I'm sure there is a library someone has wrote that could do this but there is some fun in figuring out puzzles.
There was a recent comment about curves and intersections so I decided to go ahead an post what I attempted.
I feel using a loop is expensive, but it's all I can think of doing for this, similar to the lineIntersectPoly function.


  1.  
  2.  
  3. /*---------------------------------------------------------------------------
  4. Returns Array of intersection Points on a quadratic curve.
  5. An empty Array is returned if no intersection is found.
  6.  
  7. Parameters:
  8. A -Start Point of a segment to make intersection.
  9. B -End Point of a segment to make intersection.
  10. sp -Start Point of curve.
  11. cp -Control Point of curve.
  12. ep -End Point of curve.
  13. rez -The resolution of curve tests
  14. Note: Uses another function for testing the intersections:
  15.  
  16. http://keith-hair.net/blog/2008/08/04/find-intersection-point-of-two-lines-in-as3/
  17.  
  18. ----------------------------------------------------------------------------*/
  19. function lineToQCurve_Intersect(A:Point,B:Point,sp:Point,cp:Point,ep:Point,rez:Number=80):Array
  20. {
  21. //rez less than 2 is almost "Pointless" LOL.
  22. var low:Number=2;
  23. var high:Number=99; //100 causes infinite loop.
  24. rez=Math.min(Math.max(Math.min(low,high),rez),high);
  25. var t:Number=0;
  26. var ft:Number=0;
  27. var n:Number=99/rez;
  28. var C:Point=new Point();
  29. var D:Point=new Point();
  30. var L:Point=new Point();
  31. var ip:Point;
  32. var a:Array=[];
  33. //test possible segment intersections in a loop.
  34. var z:int=100;
  35. while (z > -1)
  36. {
  37. t=z/100;
  38. C.x=Math.pow(1-t,2)*sp.x+2*(1-t)*t*cp.x+Math.pow(t,2)*ep.x;
  39. C.y=Math.pow(1-t,2)*sp.y+2*(1-t)*t*cp.y+Math.pow(t,2)*ep.y;
  40. D=L;//Connect start to last end point
  41. L=C.clone();
  42. if (z == 100) {
  43. D=ep.clone();
  44. }
  45. ip=lineIntersectLine(A,B,C,D);
  46. if (ip != null) {
  47. a.push(ip);
  48. if(a.length == 2){
  49. break;
  50. }
  51. }
  52. z-=n;
  53. }
  54. return a;
  55. }
  56.  
3 Responses to “Find intersection of a Line and Quadratic Curve”
  1. That is pretty impressive stuff :)

  2. You can find the intercept between a quadratic curve and a line analytically in 2D space by taking the dot product of the formula for the curve with a normal to the line and solving for zero — see http://groups.google.com/group/comp.graphics.algorithms/msg/1e4213d32937d37c

  3. i lold hard at //rez less than 2 is almost “Pointless” LOL.

Leave a Comment

Thanks for visiting www.keith-hair.net