Page 1 of 1

Ellipse Collision Detection

Posted: Sat Jul 20, 2019 5:17 am
by shalinrox123
I know how to do a normal circle collision, but how do you detect collisions between two axis aligned ellipses?

Re: Ellipse Collision Detection

Posted: Sat Jul 20, 2019 10:21 pm
by ivan
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 non-axis aligned ellipses.

Re: Ellipse Collision Detection

Posted: Sun Jul 21, 2019 5:35 am
by raidho36
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 circle-to-circle or circle-to-ellipse 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

Posted: Sun Jul 21, 2019 11:11 am
by pgimeno
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 ... o-ellipses

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 (x-x0)²/a² + (y-y0)²/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:
raidho36 wrote:
Sun Jul 21, 2019 5:35 am
If ellpises are not axis aligned you can rotate the coordinate grid until they become axis aligned.
In general, no you can't. You can apply an affine transformation that converts one into a circle and the other into an axis-aligned ellipse, though.

Re: Ellipse Collision Detection

Posted: Sun Jul 21, 2019 3:39 pm
by NotARaptor
I wrote something a while ago on the forum for ellipse-segment intersection, could be easily modified for ellipse-ellipse:

https://love2d.org/forums/viewtopic.php ... 42#p218942