Ellipse Collision Detection

General discussion about LÖVE, Lua, game development, puns, and unicorns.
shalinrox123
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?

ivan
Party member
Posts: 1606
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

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 non-axis aligned ellipses.

raidho36
Party member
Posts: 2063
Joined: Mon Jun 17, 2013 12:00 pm

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

pgimeno
Party member
Posts: 2283
Joined: Sun Oct 18, 2015 2:58 pm

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

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 ellipse-segment intersection, could be easily modified for ellipse-ellipse:

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

Who is online

Users browsing this forum: Bing [Bot] and 21 guests