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
03.06.2010 — 12:38 am
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?
03.06.2010 — 6:10 pm
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 :)
03.06.2010 — 8:24 pm
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?
03.06.2010 — 8:34 pm
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;
}
03.06.2010 — 8:42 pm
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.
03.06.2010 — 10:46 pm
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. :)
03.06.2010 — 10:51 pm
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. :)
03.06.2010 — 11:16 pm
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?
03.06.2010 — 11:26 pm
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.
04.06.2010 — 12:55 am
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! :)
06.04.2013 — 10:33 pm
I know this post is pretty old, but I thought I’d point out a bug I found.
If p1 and p2 have the same x coordinate (so it is a vertical line), then none of the functions will work.
12.08.2014 — 4:03 am
I saw Michael’s comment about the flaw in the ellipse code. He is right, this post is pretty old, but it is good to have the solution to when the slope approaches infinity. Here is a rework of the intersection code:
// returns array of intersection points, will return null if there is no intersection
// will return 2 points (usually) in the array, or one if the line is a tangent
// set extend to true if you want the line to extend indefinitely, false if only between the 2 points
// setting sort to true will will put the intersection point closer to p1 in the first index of the array, handy
// if you’re doing line of sight between an enemy (p1) and a target (p2) and need to know which intersection point would
// be the enemy’s collision point…
public function getIntersections(p1:Point,p2:Point,extend:Boolean=false,sort:Boolean=false):Array{
var ar:Array = new Array();
// normailze points (ie, make everything relative to (0,0))
var p1Norm:Point = new Point(p1.x-center.x,-(p1.y-center.y));
var p2Norm:Point = new Point(p2.x-center.x,-(p2.y-center.y));
// get the slope – y = mx+b
var m:Number = MathUtil.truncate( (p2Norm.y-p1Norm.y)/(p2Norm.x-p1Norm.x), SS.PRECISION );
//is line slope too close to infinity?
//use approximation of infinity, this can occur when p2Norm.x and p1Norm.x are really close or equal
//we limit it at int.MAX_VALUE so that we don’t end up with Infinity in the calculations below
if (m == Number.POSITIVE_INFINITY || m > int.MAX_VALUE){
m = int.MAX_VALUE;
}
if ( m == Number.NEGATIVE_INFINITY || m = 0){
// solve for x values – using the quadratic equation
p3.x = (-B-Math.sqrt(radicand))/(2*A);
p4.x = (-B+Math.sqrt(radicand))/(2*A);
// calculate y, since we know it’s on the line at that point (otherwise there would be no intersection)
p3.y = m*p3.x+si;
p4.y = m*p4.x+si;
// revert to flash coordinate system
p3.x += center.x;
p3.y = -p3.y+center.y;
p4.x += center.x;
p4.y = -p4.y+center.y;
//if slope was infinity we will need to recalculate the values to be precise
if (p1Norm.x == p2Norm.x){
yPoints = this.getInersectionsFromX(p1.x);
if ( isNaN(Point(yPoints[0]).y) || isNaN(Point(yPoints[1]).y) ){
//no intersection
return [null, null];
} else {
p3 = yPoints[0];
p4 = yPoints[1];
}
}
// add to array of points
if(!extend){
// only return points of the intersection that exist on the line between p1 and p2
if (isBetweenPoints(p1,p2,p3)) ar.push(p3);
if (isBetweenPoints(p1,p2,p4)) ar.push(p4);
} else {
// return points of intersection on the infinitly extending line defined by p1 and p2
ar.push(p3);
ar.push(p4);
}
if(sort && ar.length > 1){
// make sure that index 0 contains the closer point
if(distanceBetweenPoints(p1,ar[0]) > distanceBetweenPoints(p1,ar[1])){
ar.reverse();
}
}
}else 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);
p3.y = m*p3.x+si;
//if slope was infinity we will need to recalculate the values to be precise
if (p1Norm.x == p2Norm.x){
if (p1Norm.x a){
//no intersection
return [null,null];
} else {
p3.x = p1Norm.x;
p3.y = 0;
}
}
// revert to flash coordinate system
p3.x += center.x;
p3.y = -p3.y+center.y;
// add to array of points
if(!extend){
if (isBetweenPoints(p1,p2,p3)) ar.push(p3);
} else {
ar.push(p3);
}
}
// cleanup the array
if(ar.length == 0){
ar = [null,null];
}else if(ar.length == 1){
ar[1] = null;
}
return ar;
}
12.08.2014 — 2:58 pm
I keep forgetting to update the files on this site. I’ve finally done so. Thanks for the reminder. I fixed this ages ago but never updated the site. Thanks for the code and the reminders!
17.01.2017 — 10:58 pm
Thanks for the source on how this is done. However, I’m also seeing the problem with the slope reaching infinity. The source files that were provided in the link above do not address this issue. Is there a newer version? You mentioned that you fixed this ages ago but I’m still seeing the problem in the source link.
17.01.2017 — 11:02 pm
I think the comment from Nico fixes the issue you’re describing. I feel like it was a divide by zero issue that I missed, but it’s been ages :)
18.01.2017 — 2:46 pm
Thanks for the reply back. However, looking at Nico’s post there are items such as MathUtil that are not included in your script. It also looks like some of the formatting of Nico’s reply was lost in translating certain characters to html.
18.01.2017 — 3:01 pm
Yep, I realize that. His code provides the corrections to mine. You will need to move his changes into my code. It’s a pretty straight forward swap, just replace the methods in my code that he’s written with his. I’m sure you can do it :)