May
19
2009

## Find intersection of a Line and Quadratic Curve

Posted by: Keith H in ActionScript 3, tags: Curves, Intersection, Line, Point, QuadraticAfter 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.

/*--------------------------------------------------------------------------- Returns Array of intersection Points on a quadratic curve. An empty Array is returned if no intersection is found. Parameters: A -Start Point of a segment to make intersection. B -End Point of a segment to make intersection. sp -Start Point of curve. cp -Control Point of curve. ep -End Point of curve. rez -The resolution of curve tests Note: Uses another function for testing the intersections: http://keith-hair.net/blog/2008/08/04/find-intersection-point-of-two-lines-in-as3/ ----------------------------------------------------------------------------*/ function lineToQCurve_Intersect(A:Point,B:Point,sp:Point,cp:Point,ep:Point,rez:Number=80):Array { //rez less than 2 is almost "Pointless" LOL. var low:Number=2; var high:Number=99; //100 causes infinite loop. rez=Math.min(Math.max(Math.min(low,high),rez),high); var t:Number=0; var ft:Number=0; var n:Number=99/rez; var C:Point=new Point(); var D:Point=new Point(); var L:Point=new Point(); var ip:Point; var a:Array=[]; //test possible segment intersections in a loop. var z:int=100; while (z > -1) { t=z/100; C.x=Math.pow(1-t,2)*sp.x+2*(1-t)*t*cp.x+Math.pow(t,2)*ep.x; C.y=Math.pow(1-t,2)*sp.y+2*(1-t)*t*cp.y+Math.pow(t,2)*ep.y; D=L;//Connect start to last end point L=C.clone(); if (z == 100) { D=ep.clone(); } ip=lineIntersectLine(A,B,C,D); if (ip != null) { a.push(ip); if(a.length == 2){ break; } } z-=n; } return a; }

That is pretty impressive stuff

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

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