Ellipse Collision Detection

 Prole
 Posts: 1
 Joined: Tue Jul 09, 2019 4:28 pm
Ellipse Collision Detection
I know how to do a normal circle collision, but how do you detect collisions between two axis aligned ellipses?
Re: Ellipse Collision Detection
I'll try to explain one way of approaching this problem.
Since you are working with axis aligned ellipses you could just "scale" their ratios and positions along an axis.
At that point you can treat the two as circles.
It gets complicated with nonaxis aligned ellipses.
Since you are working with axis aligned ellipses you could just "scale" their ratios and positions along an axis.
At that point you can treat the two as circles.
It gets complicated with nonaxis aligned ellipses.
Re: Ellipse Collision Detection
If ellpises are not axis aligned you can rotate the coordinate grid until they become axis aligned.
Using coordinate rotation and scaling, you can arrive at circletocircle or circletoellipse collision. Former is trivial, latter involves quite a bit of math. General case of ellipse to ellipse collision is extremely complicated. Usually people would use "close enough" approximations of the ellipses, using convex hulls or multiple overlapping circles.
Using coordinate rotation and scaling, you can arrive at circletocircle or circletoellipse collision. Former is trivial, latter involves quite a bit of math. General case of ellipse to ellipse collision is extremely complicated. Usually people would use "close enough" approximations of the ellipses, using convex hulls or multiple overlapping circles.
Re: Ellipse Collision Detection
If the AAEs have the same ratio between their diameters, then what ivan said. If they don't, things get uglier. Here are two approaches in the latter case: https://math.stackexchange.com/question ... oellipses
Both methods start by calculating whether the centre of one ellipse is inside the other ellipse. If it is, then they are colliding. To do that, you just need to check if (xx0)²/a² + (yy0)²/b² <= 1, where x,y is the centre of one ellipse and x0, y0, a, b are the centre and radii of the other ellipse. That's the easy part.
If the centre of one ellipse is not contained in the other, they can still intersect, and that's where the two methods come into play.
One method consists of calculating the points of intersection between the two ellipses (there can be up to 4). According to the source, this involves finding the roots of a cubic equation. Which sounds weird to me because there should be up to 4 solutions, while a cubic can't have more than 3, but I guess that the details will reveal the reasons. If there are any real intersection points, the ellipses intersect.
The other method consists of scaling the coordinates and parameters, to transform one of the ellipses into a circle, then checking the minimum distance between the centre of the circle and the ellipse. That involves finding the roots of a quartic equation. There must be at least two real solutions, the shortest of which should be the distance. If it's less than the radius of the circle, they intersect.
Edit: For the second approach, there is an iterative algorithm here to calculate the distance: http://www.spaceroots.org/documents/dis ... llipse.pdf
Edit 2 @raidho36:
Both methods start by calculating whether the centre of one ellipse is inside the other ellipse. If it is, then they are colliding. To do that, you just need to check if (xx0)²/a² + (yy0)²/b² <= 1, where x,y is the centre of one ellipse and x0, y0, a, b are the centre and radii of the other ellipse. That's the easy part.
If the centre of one ellipse is not contained in the other, they can still intersect, and that's where the two methods come into play.
One method consists of calculating the points of intersection between the two ellipses (there can be up to 4). According to the source, this involves finding the roots of a cubic equation. Which sounds weird to me because there should be up to 4 solutions, while a cubic can't have more than 3, but I guess that the details will reveal the reasons. If there are any real intersection points, the ellipses intersect.
The other method consists of scaling the coordinates and parameters, to transform one of the ellipses into a circle, then checking the minimum distance between the centre of the circle and the ellipse. That involves finding the roots of a quartic equation. There must be at least two real solutions, the shortest of which should be the distance. If it's less than the radius of the circle, they intersect.
Edit: For the second approach, there is an iterative algorithm here to calculate the distance: http://www.spaceroots.org/documents/dis ... llipse.pdf
Edit 2 @raidho36:
In general, no you can't. You can apply an affine transformation that converts one into a circle and the other into an axisaligned ellipse, though.
 NotARaptor
 Citizen
 Posts: 59
 Joined: Thu Feb 22, 2018 3:15 pm
Re: Ellipse Collision Detection
I wrote something a while ago on the forum for ellipsesegment intersection, could be easily modified for ellipseellipse:
https://love2d.org/forums/viewtopic.php ... 42#p218942
https://love2d.org/forums/viewtopic.php ... 42#p218942
Who is online
Users browsing this forum: Nelvin and 7 guests