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.
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 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!