Ellipse Collision Detection

General discussion about LÖVE, Lua, game development, puns, and unicorns.
Post Reply
shalinrox123
Prole
Posts: 1
Joined: Tue Jul 09, 2019 4:28 pm

Ellipse Collision Detection

Post by shalinrox123 »

I know how to do a normal circle collision, but how do you detect collisions between two axis aligned ellipses?
User avatar
ivan
Party member
Posts: 1911
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: Ellipse Collision Detection

Post 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.
User avatar
raidho36
Party member
Posts: 2063
Joined: Mon Jun 17, 2013 12:00 pm

Re: Ellipse Collision Detection

Post 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.
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: Ellipse Collision Detection

Post 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 amIf 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.
User avatar
NotARaptor
Citizen
Posts: 59
Joined: Thu Feb 22, 2018 3:15 pm

Re: Ellipse Collision Detection

Post 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
Post Reply

Who is online

Users browsing this forum: Ahrefs [Bot], Google [Bot] and 50 guests