Intersection of an Ellipse and a Line in AS3
A few months back I was working on a game for which I needed to be able to calculate the points of intersection between a line and an ellipse. I wanted enemies and the hero to be able to collide with and avoid an elliptical obstruction in the middle of the game. I also wanted to be able to calculate whether enemies had a line-of-sight to their targets, given this elliptical obstruction. I did some searching to see if anyone had written a class to handle this. Keith Hair wrote a very nice class that does this with a circle. Aaron Clinger and Mike Creighton wrote a a very nice Ellipse class, but it didn’t deal with ellipse-line intersections, only ellipse-point intersection and general ellipse calculations such as area and circumference. Both of these are great finds, but neither of them did what I was looking for.
Since I couldn’t find what I was looking for I decided I would write it myself and since Aaron and Mike’s Ellipse class had so many useful features I though I’d have my class extend theirs. Here is a demo of my EllipseExt class which has all the bells and whistles of Aaron and Mikes Ellipse class plus some intersection calculation methods added:
You will notice that by dragging one of the nodes inside the ellipse you lose a point of intersection. However if you switch on the “extend line indefinitely” option the nodes will no longer act as start->end points but rather 2 points that define an infinite line. This is a feature I found helpful for game programming, so I decided to build it in as an optional argument of the getIntersections() method. There is another optional argument that came out thinking about game logic; the sort option. With sort set to true, the getIntersections() method will sort the points by proximity to the first node used to define the line (i.e. the first required argument). This can be very helpful if one of the line’s nodes is a hero or enemy approaching the ellipse and you need to know which of the returned points represents the potential point of impact.
Examples:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | // generic form public function getIntersections(p1:Point,p2:Point,extend:Boolean=false,sort:Boolean=false):Array // define points that make up our line var A = new Point(mouseX,mouseY); var B = new Point(0,0); // create an ellipse 200x100 at (50,50) var ellipse:EllipseExt(50,50,200,100); // Example 1: // find intersections of line AB and ellipse BETWEEN points A and B var ar:Array = ellipse.getIntersections(A,B); // Example 2: // find intersections of line AB and ellipse DEFINED BY points A and B var ar:Array = ellipse.getIntersections(A,B,true); // Example 3: // find intersections of line AB and ellipse BETWEEN points A and B // ar[0] will contain the point of intersection that is closest to point A var ar:Array = ellipse.getIntersections(A,B,false,true); |
There are a few other available methods, which I’ll refer to as shortcut methods because each of these can be achieved through the getIntersections method. However, these 4 methods either handle some of the logic you’d otherwise need to build around the getIntersections() method OR they’re acceptably lighter options depending on what you need to know about the line and the ellipse interaction. These are commented further in the EllipseExt class itself, but here’s a preview:
1 2 3 4 5 6 7 8 | // simply determines if there is an intersection point at all (line-of-sight) checkForIntersection(p1:Point,p2:Point):Boolean // returns the point of intersection between the center of the ellipse and pt getPointCenterIntersection(pt:Point):Point // returns points of intersection on the ellipse at the given y coordinate getInersectionsFromY(y:Number):Array // returns points of intersection on the ellipse at the given x coordinate getInersectionsFromX(x:Number):Array |
The classes and source code for the above demo can be downloaded here.
I’d like to add some additional methods to this class, specifically for calculating tangent lines/points, which would be useful for pathfinding routes around an ellipse. But I figured that this was far along enough that it was worth sharing. If you have questions or find a bug, please feel free to contact me and I’ll be happy to do what I can to help. I hope you’ll find this useful. Enjoy!
Additional stuff on ellipses for those who need to brush up:
Ellipse Equation Visualizer
Ellipse-Line Intersection
Quadratic Equation
Thanks for this post. It has been a real life saver. I have a question. @param x: The horizontal position of the ellipse.
@param y: The vertical position of the ellipse.
in the constructor of Ellipse is this the center of the ellipse or the top left hand corner?
The x and y params are the center of the ellipse. Give me a shout if you have any other questions about or problems with the code. Thanks for reading :)
line 83 EllipseExt
if(radicand == 0){
// in this case both points will result in the same, so we only need to calculate one point
p3.x = (-B-Math.sqrt(radicand))/(2*A);
why are you calculating the square root of 0?
Ok so there is something not matching up between mc.graphics.drawEllipse(x, y, 10, 10); and when I run the following function. My intersection points are not lining up.
function isEllipseIntersectingLineSeg(linePoint1:Point, linePoint2:Point, x:Number, y:Number, width:Number, height:Number):Boolean{
width = MathUtil.truncate(width, SS.PRECISION);
height = MathUtil.truncate(height, SS.PRECISION);
var ellipse:Ellipse = new Ellipse(x, y, width, height);
var resultsArray:Array = ellipse.getIntersections(linePoint1, linePoint2);
var isIntersecting:Boolean;
var angle1 : Number;
var angle2 : Number;
if (resultsArray[0] != null){
Render._debugVis.graphics.beginFill(0xff0000, .5);
Render._debugVis.graphics.drawCircle(Point(resultsArray[0]).x, Point(resultsArray[0]).y, .5);
Render._debugVis.graphics.endFill();
isIntersecting = true;
}
if (resultsArray[1] != null){
Render._debugVis.graphics.beginFill(0xff0000, .5);
Render._debugVis.graphics.drawCircle(Point(resultsArray[1]).x, Point(resultsArray[1]).y, .5);
Render._debugVis.graphics.endFill();
isIntersecting = true;
}
return isIntersecting;
}
In response to your question about line 83, when the radicand is zero we know the points of intersections are going to be the same, so we can just pick on and do one less set of calculations.
I’ll have to spend some time looking at the code from your 3rd comment and get back to you.
My point is more around the subject of optimization:
if(radicand == 0){
trace( Math.sqrt(radicand) )
}
is redundant inside of an if statement that checks to make sure radicand is 0. There is no need for the Math.sqrt since the answer will always be 0. No need to run a function call if there is no need for it. :)
Oh, duh. You know what I probably did some copying in pasting when I was putting that line together. I believe I copied that from the other situation where you’d be calculating 2 intersections with varying values for radicand and then never went back and never swapped that out for a constant value of Math.sqrt(0).
You are correct. That was an oversight on my part. Good call. :)
Here is a better description of why I posted that large block of code before:
I see in your demo fla that everything seems to work.
ellipseClip.graphics.lineStyle(1,0×000000,.2);
ellipseClip.graphics.drawEllipse(0,0,ELLIPSE_WIDTH,ELLIPSE_HEIGHT);
ellipseClip.x = (STAGE_WIDTH-ELLIPSE_WIDTH)/2;
ellipseClip.y = (STAGE_HEIGHT-ELLIPSE_HEIGHT)/2;
Because you adjust the graphics drawing API to work with your data model.
The drawEllipse x and y parameters are not to be confused with your EllipseExt x and y parameters. Flash does use x and y as the top left hand corner of the bounding box, where as you use the x and y as the center. In short the view and model are not the same. You make sure they line up by transposing the ellipseClip. But, if you are doing a visualization without transposing the outer movie clip you have to adjust drawEllipse directly so that it looks like the following:
ellipseClip.graphics.drawEllipse(x-(ELLIPSE_WIDTH/2), y-(ELLIPSE_WIDTH/2), ELLIPSE_WIDTH, ELLIPSE_HEIGHT);
However in my code I get some weird stuff going on: To make the above work I have to use:
EllipseExt(ELLIPSE_CENTER.x-(ELLIPSE_WIDTH/2), ELLIPSE_CENTER.y-(ELLIPSE_HEIGHT/2), ELLIPSE_WIDTH, ELLIPSE_HEIGHT);
Otherwise the intersection points do not match up to the ellipse. Which means there is a difference if you are doing everything in one graphics object versus transposing outer movies like you are doing. But I’m a bit confuse why it would be any different. Anyways its not a problem for me. I just adjust the EllipseExt constructor accordingly. It’s just peculiar observation.
Anyone else run into this?
Well said. I remember running into those issues while I was trying to get all of this to work. You comment about the “view and model” being off is correct. I probably should have spent a little more time on this one to iron that out. Perhaps I’ll revisit this one day and clean that up. Frankly I was excited to get this damn thing working that I pretty much stopped messing with it once it was working.
I’m sorry if that confused anyone else who might have tried to use this class. Hopefully even with the adjustment you had to make the class still saved you some time.
No problem, any future users will know of this in advance from our comments. I can imagine you would kill your self creating this class. Thanks so much for saving me the hours. If you want to see an example of how I used your code check out this article:
http://www.actionscript-flash-guru.com/blog/33-scale-around-a-point-transform-multiple-objects-actionscript-3-as3
at the bottom of the page there is a drawing program that uses your program to detect line selections.
Take care, Nico out! :)