Do Axis-Aligned Ellipses Intersect?
Author
As the title says, given two 2D ellipses each having a x/y position and x/y radius, how would I go about finding if they intersect? I have googled it and found answers for rotated ellipses but because they're axis-aligned, there must be a faster way to calculate this.
If it helps, this could be simplifed to a unit circle + ellipse intersection by scaling one of the ellipse's position and radius by the other's inverse radius and than translating both so the circle is centered around the origin.
Any suggestions?
I will be brief. Here is an idea, if you find the angle between the two centres then based on what quadrant this angle is in store the solved angle for the appropriate ellipse and a π radians adjustment to the other. Since x = a cos φ and y = b sinθ if a_ellipse1 * cos stored_angle1 = a_ellipse2 * cos stored_angle2 and b_ellipse1 *sin stored_angle1 ... you have an intersection. If needed I will explain in detail later when i have more time.
I'm not sure exactly what you've seen so far on google, but I sat down with a paper and pencil for this one for a little while, and I think it's fairly clear that there's one real answer to this problem. Just like how for detecting circle collision you compare the distance between their centers between the sum of their radii, you'll need to do an analogous test here. Because ellipses don't have uniform radii though, you'll need to do something on the order of getting a vector pointing from the center of one to the center of the other, and clipping it by the boundary of the one -- so that you end up with a vector pointing exactly from the center to the outer edge. You can then take the length of this vector and that's one "radius"; just do it again for the other and you're ready to compare.
As for how you do that, well, think from the one ellipse's orientation (so it's all conveniently axis-aligned for now) -- which means translating/rotating the other ellipse as appropriate to fit into the one's frame of reference. Once there, get a vector pointing from the center (now the origin) of the one out to the center of the other. Get the angle of this vector. From that you can build an appropriate vector (a*cos(angle), b*sin(angle)) where a and b are the lengths of the semimajor and semiminor axes. Now that you have this you don't need to worry about translating this back, and of course you can take its length.
Now, for optimizations. For fast 2D rotations, I advise looking into complex vectors -- they're extremely convenient, and not especially complicated. Then just start representing rotations as orientation vectors, and you can multiply these vectors to combine rotations. Besides that, you can minimize how many square roots you have to take when you're combining sums of lengths; just work it out algebraically. You could also do the scaling you mentioned; that would make it so you'd only need to deduce the "radius" of one of them, and for the other you'd stretch it into place to a constant, known radius. And one more thing, always remember you can use a simpler, less computationally expensive bounding test before you even enter into this one -- I suggest testing for collision between bounding circles, which would have radii equal to the length of the ellipses' semimajor axes. If that test passes, then go for your more accurate test.
Good luck with everything, hope this helps.
As for how you do that, well, think from the one ellipse's orientation (so it's all conveniently axis-aligned for now) -- which means translating/rotating the other ellipse as appropriate to fit into the one's frame of reference. Once there, get a vector pointing from the center (now the origin) of the one out to the center of the other. Get the angle of this vector. From that you can build an appropriate vector (a*cos(angle), b*sin(angle)) where a and b are the lengths of the semimajor and semiminor axes. Now that you have this you don't need to worry about translating this back, and of course you can take its length.
Now, for optimizations. For fast 2D rotations, I advise looking into complex vectors -- they're extremely convenient, and not especially complicated. Then just start representing rotations as orientation vectors, and you can multiply these vectors to combine rotations. Besides that, you can minimize how many square roots you have to take when you're combining sums of lengths; just work it out algebraically. You could also do the scaling you mentioned; that would make it so you'd only need to deduce the "radius" of one of them, and for the other you'd stretch it into place to a constant, known radius. And one more thing, always remember you can use a simpler, less computationally expensive bounding test before you even enter into this one -- I suggest testing for collision between bounding circles, which would have radii equal to the length of the ellipses' semimajor axes. If that test passes, then go for your more accurate test.
Good luck with everything, hope this helps.
Author
Daerax, thanks for answering. However, I'm slightly confused about your method since you're doing equality tests and there's not too much equal in ellipse intersections :P. I know your busy, but if you get the chance I would love to hear from you again.
Bucket_Head, thanks for giving this question a serious thought. I appreciate that. Your method reminds very much of circle intersection tests. Looking over it, I see some problems but I really appreciate your post since the answer may be right along those lines.
If anyone has even a slight inclination, don't hesitate to post. I will be on vacation until tuesday but hopefully there will be internet in our hotel. Otherwise, talk to everyone on tuesday. Again, everyone has been wonderful here. Your help is very much appreciated.
[Edited by - vnillabrent on August 18, 2004 7:05:23 PM]
Bucket_Head, thanks for giving this question a serious thought. I appreciate that. Your method reminds very much of circle intersection tests. Looking over it, I see some problems but I really appreciate your post since the answer may be right along those lines.
If anyone has even a slight inclination, don't hesitate to post. I will be on vacation until tuesday but hopefully there will be internet in our hotel. Otherwise, talk to everyone on tuesday. Again, everyone has been wonderful here. Your help is very much appreciated.
[Edited by - vnillabrent on August 18, 2004 7:05:23 PM]
Sorry for my last post, it was so terse and muddled that it is little more than jibberish. I was in a hurry to type it and thus jumbled many ideas together.
What I was trying to say is that if you were to draw a line from the centre of one ellipse to the other and the lines were to touch each other then there is an intersection..at least thats my theory. So what you want to do is get a vector whose origin is in one ellipse and points to the centre of the other ellipse. You can then use the vector angle with the horizontal to do some tests. A similar method I prefer is that based on the definition of cosine.
This method, limited from angles 0 to π radians is based on the idea of creating a segment whose endpoints are defined by the two ellipse centres. Then the inverse cosine of the quotient of the horizontal length and the magnitude of this line will give an angle we can use.
Δx = x2 - x1
Δy = y2 - y1
length = √(Δx2 + Δy2)
φ = cos-1Δx/length
θ = φ + π (5)
(5) works because of course, the sinusodial functions are periodic.
To extend the range of identifiable angles beyond π all one needs to do is to realize that when Δy is negative a simple axis flip will give us a range of 2π
if( Δy < 0 ) φ = 2π - φ* (5) still applies ofcourse.
Then returning to the ellipse:
if( a_1 * cos(φ) + centre1_x == a_2 * cos(θ) + centre2_x && a_1 * sin(φ) + centre1_y == a_2 * sin(θ) + centre2_y) then the ellipses are touching. It is easy to extend this so that if they are more than touching there is an intersection. So thats the general idea..
*Note that choice of y1 and fact that monitor axises are inverted will result in modification in axis flip parameter, this is just a general guide.
[Edited by - Daerax on August 18, 2004 10:32:17 PM]
What I was trying to say is that if you were to draw a line from the centre of one ellipse to the other and the lines were to touch each other then there is an intersection..at least thats my theory. So what you want to do is get a vector whose origin is in one ellipse and points to the centre of the other ellipse. You can then use the vector angle with the horizontal to do some tests. A similar method I prefer is that based on the definition of cosine.
This method, limited from angles 0 to π radians is based on the idea of creating a segment whose endpoints are defined by the two ellipse centres. Then the inverse cosine of the quotient of the horizontal length and the magnitude of this line will give an angle we can use.
Δx = x2 - x1
Δy = y2 - y1
length = √(Δx2 + Δy2)
φ = cos-1Δx/length
θ = φ + π (5)
(5) works because of course, the sinusodial functions are periodic.
To extend the range of identifiable angles beyond π all one needs to do is to realize that when Δy is negative a simple axis flip will give us a range of 2π
if( Δy < 0 ) φ = 2π - φ* (5) still applies ofcourse.
Then returning to the ellipse:
if( a_1 * cos(φ) + centre1_x == a_2 * cos(θ) + centre2_x && a_1 * sin(φ) + centre1_y == a_2 * sin(θ) + centre2_y) then the ellipses are touching. It is easy to extend this so that if they are more than touching there is an intersection. So thats the general idea..
*Note that choice of y1 and fact that monitor axises are inverted will result in modification in axis flip parameter, this is just a general guide.
[Edited by - Daerax on August 18, 2004 10:32:17 PM]
I don't think you're going to do better than the general case because it also can be transformed to the circle and ellipse case by scaling along one of the axes of one of the ellipses.
If you want to do it analytically it's not hard to find a quartic equation that gives the solution(s). Put the centre of the circle at (0, 0) so it's equation is x^2 + y^2 = r^2. Use this to replace the y^2 term in the ellipse equation. Then rearange the equation so y is on one side, square again, and replace again with r^2 - x^2.
You should then have a quartic in x. Unfortunately the analytic solution to this very complex. It is easier to solve numerically but even this is tricky, and then you have to interpret the up to four real or complex solutions.
If you want to do it analytically it's not hard to find a quartic equation that gives the solution(s). Put the centre of the circle at (0, 0) so it's equation is x^2 + y^2 = r^2. Use this to replace the y^2 term in the ellipse equation. Then rearange the equation so y is on one side, square again, and replace again with r^2 - x^2.
You should then have a quartic in x. Unfortunately the analytic solution to this very complex. It is easier to solve numerically but even this is tricky, and then you have to interpret the up to four real or complex solutions.
@Daerax
Sorry but your supposition that the nearest points belong to the segment that joins the centers is false. These are ellipses, not circles.
@John B
Right. This shows that getting the nearest points is necessarilly done through a recursion. Which means the best is to rely on early rejections, no need for the exact nearest points, they'll only be found within a metric tolerance anyway, never analytically. The ellipses being convex shapes, the separating axis theorem brings help.
Once a separating line is found and once the min distance is positive and higher than an error threshold, you can reject the test as non colliding.
The math required are :
- line to axis aligned ellipse minimum distance. That's ez to find, take the parametric definition. The nearest point is when the tangent is parallel to the said line.
- a recursion to find a separating axis. It starts by comparing the bounding boxes (<=> x aligned and y aligned axes) and then seeks the line tangent to the first ellipse for which the second ellipse is the most distant. (maximum of min distances).
I can detail the computations if required, they are pretty simple. In the end it's a quick algo. I suppose in many cases, it will stop after one loop.
EDIT : Reedited to clarify things a bit. In particular I have replaced plane (general 3D) by (straight) line (2D). In linear or affine algebra, an hyperplane is a plane in 3D and a line in 2D. That's why I used this misleading terminology.
Note : This method is meant to stop whenever a minoration of the distance between the ellipses is found greater than the collision or penetration distance tolerance. If the two ellipses are exactly in contact then it finds the contact points. This means that in this case it is equivalent to the quartic method. In both cases an iteration is necessary. No direct analytical solution equivalent to the disc/disc case.
[Edited by - Charles B on August 24, 2004 6:08:55 AM]
Sorry but your supposition that the nearest points belong to the segment that joins the centers is false. These are ellipses, not circles.
@John B
Right. This shows that getting the nearest points is necessarilly done through a recursion. Which means the best is to rely on early rejections, no need for the exact nearest points, they'll only be found within a metric tolerance anyway, never analytically. The ellipses being convex shapes, the separating axis theorem brings help.
Once a separating line is found and once the min distance is positive and higher than an error threshold, you can reject the test as non colliding.
The math required are :
- line to axis aligned ellipse minimum distance. That's ez to find, take the parametric definition. The nearest point is when the tangent is parallel to the said line.
- a recursion to find a separating axis. It starts by comparing the bounding boxes (<=> x aligned and y aligned axes) and then seeks the line tangent to the first ellipse for which the second ellipse is the most distant. (maximum of min distances).
I can detail the computations if required, they are pretty simple. In the end it's a quick algo. I suppose in many cases, it will stop after one loop.
EDIT : Reedited to clarify things a bit. In particular I have replaced plane (general 3D) by (straight) line (2D). In linear or affine algebra, an hyperplane is a plane in 3D and a line in 2D. That's why I used this misleading terminology.
Note : This method is meant to stop whenever a minoration of the distance between the ellipses is found greater than the collision or penetration distance tolerance. If the two ellipses are exactly in contact then it finds the contact points. This means that in this case it is equivalent to the quartic method. In both cases an iteration is necessary. No direct analytical solution equivalent to the disc/disc case.
[Edited by - Charles B on August 24, 2004 6:08:55 AM]
It's very simple to instantly see it's at least quartic equation(fourth power) There's max. 4 intersection points.
I completely agree with Johnb...
i derived that quartic and don't see ways simpler than general quartic or numeric.
edit:
But it may be simpler to find if there's intersection or not , than to find intersection points.
I completely agree with Johnb...
i derived that quartic and don't see ways simpler than general quartic or numeric.
edit:
But it may be simpler to find if there's intersection or not , than to find intersection points.
Quote:Original post by Charles B
@Daerax
Sorry but your supposition that the nearest points belong to the segment that joins the centers is false. These are ellipses, not circles.
I worked under the premise that if you can connect the lines of the centres of the two ellipses then they are intersecting. If you cannot, then because the ellipses are axially aligned the chances of there being an intersection are quite unlikely. It then follows that this method would be a very good estimation for an intersection as it does not require the solving of quadratics for an intersection test.
Thhis is How I do it....
To test whether 2 axis-aligned ellipses intersect.
First, we define the condition by saying the ellipses intersect either if they touch or if they overlap.
Just testing if the boundaries intersect (by solving simultaneous equations from their formulae) will give an incorrect result if one ellipse is fully enclosed within the other.
This method establishes the distance between the centres and then computes the lengths of the radii of the two ellipses along the line joining the centres. If the sum of the radii => the distance to the centres, they must overlap.
We simplify the question by centering one ellipse at the origin, and the other at Cx.Cy.
Then the distance between the centres is L where L^2 = Cx^2 + Cy^2
Now we define the ellipses using the standard formulae:-
Ellipse 1, centred at the origin has the equation (x/a)^2 + (y/b)^2 =1
Ellipse 2, centred at Cx,Cy has the equation ((x-Cx)/d)^2 + ((y-Cy)/e)^2 = 1
which can be simplified by letting X= x-Cx and Y = y - Cy to (X/d)^2 + (Y/e)^2 = 1
The line joining the centres has the equation y = m*x where m = Cy/Cx
The tests start by eliminating trivial cases.
1. We ignore the cases where a, b, d or e =0 as these are not ellipses.
2. Orthogonal Overlap. If the ellipses don’t overlap orthogonally, then they don’t overlap at all.
Horizontal overlap is established if a + (d - ABS(Cx)) => L
Vertical overlap occurs if b + (e - ABS(Cy)) => L
If either test fails, the ellipses do not overlap.
2. Cx or Cy (or both) = 0. If this is so the Orthogonal Overlap tests are sufficient.
Which leaves the general case.
We find where the line y = m*x crosses the ellipses.
For ellipse 1 we find radius R1 by means of the simultaneous equations
Ry^2 = (m*x)^2 and
Ry^2 = -(x*b/a)^2 + b^2
which solves for Rx^2 = (b^2)/(m^2 +(b/a)^2) and
Ry^2 = ((m*b)^2)/(m^2 +(b/a)^2)
The radius is R1 where R1^2 = Rx^2 + Ry^2 so
R1^2 = ((1 + m^2)*b^2)/(m^2 + (b/a)^2)
Similarly, for ellipse 2, we find the radius R2
RX^2 = (e^2)/(m^2 + (e/d)^2) and
RY^2 = ((m*e)^2)/(m^2 + (e/d)^2)
So R2^2 = ((1 + m^2)*e^2)/(m^2 + (e/d)^2)
And, if R1 + R2 => L, the ellipses overlap.
Hope this helps.
To test whether 2 axis-aligned ellipses intersect.
First, we define the condition by saying the ellipses intersect either if they touch or if they overlap.
Just testing if the boundaries intersect (by solving simultaneous equations from their formulae) will give an incorrect result if one ellipse is fully enclosed within the other.
This method establishes the distance between the centres and then computes the lengths of the radii of the two ellipses along the line joining the centres. If the sum of the radii => the distance to the centres, they must overlap.
We simplify the question by centering one ellipse at the origin, and the other at Cx.Cy.
Then the distance between the centres is L where L^2 = Cx^2 + Cy^2
Now we define the ellipses using the standard formulae:-
Ellipse 1, centred at the origin has the equation (x/a)^2 + (y/b)^2 =1
Ellipse 2, centred at Cx,Cy has the equation ((x-Cx)/d)^2 + ((y-Cy)/e)^2 = 1
which can be simplified by letting X= x-Cx and Y = y - Cy to (X/d)^2 + (Y/e)^2 = 1
The line joining the centres has the equation y = m*x where m = Cy/Cx
The tests start by eliminating trivial cases.
1. We ignore the cases where a, b, d or e =0 as these are not ellipses.
2. Orthogonal Overlap. If the ellipses don’t overlap orthogonally, then they don’t overlap at all.
Horizontal overlap is established if a + (d - ABS(Cx)) => L
Vertical overlap occurs if b + (e - ABS(Cy)) => L
If either test fails, the ellipses do not overlap.
2. Cx or Cy (or both) = 0. If this is so the Orthogonal Overlap tests are sufficient.
Which leaves the general case.
We find where the line y = m*x crosses the ellipses.
For ellipse 1 we find radius R1 by means of the simultaneous equations
Ry^2 = (m*x)^2 and
Ry^2 = -(x*b/a)^2 + b^2
which solves for Rx^2 = (b^2)/(m^2 +(b/a)^2) and
Ry^2 = ((m*b)^2)/(m^2 +(b/a)^2)
The radius is R1 where R1^2 = Rx^2 + Ry^2 so
R1^2 = ((1 + m^2)*b^2)/(m^2 + (b/a)^2)
Similarly, for ellipse 2, we find the radius R2
RX^2 = (e^2)/(m^2 + (e/d)^2) and
RY^2 = ((m*e)^2)/(m^2 + (e/d)^2)
So R2^2 = ((1 + m^2)*e^2)/(m^2 + (e/d)^2)
And, if R1 + R2 => L, the ellipses overlap.
Hope this helps.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
