iki.fi/o

Ellipse–circle and ellipse–ellipse collision detection

Created by Olli Niemitalo on 2012-07-25, last modified 2016-11-29

Closed-form solution

To detect ellipse–circle collision (intersection or one being inside another), the point on the ellipse can be found from which a line perpendicular to the ellipse tangent at that point goes through the circle center. The point on the side closer to the circle center should be taken, not the point on the opposite side of the ellipse. If the point lies inside the circle, there is a collision. If the center of the circle is inside the ellipse, there is always a collision, and this should be tested for before making things more complicated. The same calculations could be used to detect any ellipse–ellipse collision by first using an affine transformation to stretch either of the ellipses into a circle; the other will remain an ellipse.

The closed form solution for the point on the ellipse is a gargantuan equation:

x = c*b^2/(2*(b^2 - 1)) - 1/2*sqrt(c^2*b^4/(b^2 - 1)^2 + (c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)/(3*(b^4 - 2*b^2 + 1)) - (c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)/(b^2 - 1)^2 + (- 108*c^2*(b^4*c - b^2*c)^2*b^4 + 72*(b^4 - 2*b^2 + 1)*c^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)*b^4 + 2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)^3 + 108*(b^4 - 2*b^2 + 1)*(b^4*c - b^2*c)^2 + 36*(b^4*c - b^2*c)^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1) + sqrt((- 108*c^2*(b^4*c - b^2*c)^2*b^4 + 72*(b^4 - 2*b^2 + 1)*c^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)*b^4 + 2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)^3 + 108*(b^4 - 2*b^2 + 1)*(b^4*c - b^2*c)^2 + 36*(b^4*c - b^2*c)^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1))^2 - 4*(- 12*(b^4 - 2*b^2 + 1)*c^2*b^4 + 12*(b^4*c - b^2*c)^2 + (c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)^2)^3))^(1/3)/(3*2^(1/3)*(b^2 - 1)^2) + 2^(1/3)*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)^2/(3*(b^2 - 1)^2*(- 108*c^2*(b^4*c - b^2*c)^2*b^4 + 72*(b^4 - 2*b^2 + 1)*c^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)*b^4 + 2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)^3 + 108*(b^4 - 2*b^2 + 1)*(b^4*c - b^2*c)^2 + 36*(b^4*c - b^2*c)^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1) + sqrt((- 108*c^2*(b^4*c - b^2*c)^2*b^4 + 72*(b^4 - 2*b^2 + 1)*c^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)*b^4 + 2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)^3 + 108*(b^4 - 2*b^2 + 1)*(b^4*c - b^2*c)^2 + 36*(b^4*c - b^2*c)^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1))^2 - 4*(- 12*(b^4 - 2*b^2 + 1)*c^2*b^4 + 12*(b^4*c - b^2*c)^2 + (c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)^2)^3))^(1/3))) + 1/2*sqrt(2*c^2*b^4/(b^2 - 1)^2 - (c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)/(3*(b^4 - 2*b^2 + 1)) - (c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)/(b^2 - 1)^2 - (- 108*c^2*(b^4*c - b^2*c)^2*b^4 + 72*(b^4 - 2*b^2 + 1)*c^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)*b^4 + 2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)^3 + 108*(b^4 - 2*b^2 + 1)*(b^4*c - b^2*c)^2 + 36*(b^4*c - b^2*c)^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1) + sqrt((- 108*c^2*(b^4*c - b^2*c)^2*b^4 + 72*(b^4 - 2*b^2 + 1)*c^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)*b^4 + 2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)^3 + 108*(b^4 - 2*b^2 + 1)*(b^4*c - b^2*c)^2 + 36*(b^4*c - b^2*c)^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1))^2 - 4*(- 12*(b^4 - 2*b^2 + 1)*c^2*b^4 + 12*(b^4*c - b^2*c)^2 + (c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)^2)^3))^(1/3)/(3*2^(1/3)*(b^2 - 1)^2) - 2^(1/3)*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)^2/(3*(b^2 - 1)^2*(- 108*c^2*(b^4*c - b^2*c)^2*b^4 + 72*(b^4 - 2*b^2 + 1)*c^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)*b^4 + 2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)^3 + 108*(b^4 - 2*b^2 + 1)*(b^4*c - b^2*c)^2 + 36*(b^4*c - b^2*c)^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1) + sqrt((- 108*c^2*(b^4*c - b^2*c)^2*b^4 + 72*(b^4 - 2*b^2 + 1)*c^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)*b^4 + 2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)^3 + 108*(b^4 - 2*b^2 + 1)*(b^4*c - b^2*c)^2 + 36*(b^4*c - b^2*c)^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1))^2 - 4*(- 12*(b^4 - 2*b^2 + 1)*c^2*b^4 + 12*(b^4*c - b^2*c)^2 + (c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)^2)^3))^(1/3)) - (8*c^3*b^6/(b^2 - 1)^3 - 16*c*b^2/(b^2 - 1) - 8*c*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)*b^2/(b^2 - 1)^3)/(4*sqrt(c^2*b^4/(b^2 - 1)^2 + (c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)/(3*(b^4 - 2*b^2 + 1)) - (c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)/(b^2 - 1)^2 + (- 108*c^2*(b^4*c - b^2*c)^2*b^4 + 72*(b^4 - 2*b^2 + 1)*c^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)*b^4 + 2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)^3 + 108*(b^4 - 2*b^2 + 1)*(b^4*c - b^2*c)^2 + 36*(b^4*c - b^2*c)^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1) + sqrt((- 108*c^2*(b^4*c - b^2*c)^2*b^4 + 72*(b^4 - 2*b^2 + 1)*c^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)*b^4 + 2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)^3 + 108*(b^4 - 2*b^2 + 1)*(b^4*c - b^2*c)^2 + 36*(b^4*c - b^2*c)^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1))^2 - 4*(- 12*(b^4 - 2*b^2 + 1)*c^2*b^4 + 12*(b^4*c - b^2*c)^2 + (c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)^2)^3))^(1/3)/(3*2^(1/3)*(b^2 - 1)^2) + 2^(1/3)*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)^2/(3*(b^2 - 1)^2*(- 108*c^2*(b^4*c - b^2*c)^2*b^4 + 72*(b^4 - 2*b^2 + 1)*c^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)*b^4 + 2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)^3 + 108*(b^4 - 2*b^2 + 1)*(b^4*c - b^2*c)^2 + 36*(b^4*c - b^2*c)^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1) + sqrt((- 108*c^2*(b^4*c - b^2*c)^2*b^4 + 72*(b^4 - 2*b^2 + 1)*c^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)*b^4 + 2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)^3 + 108*(b^4 - 2*b^2 + 1)*(b^4*c - b^2*c)^2 + 36*(b^4*c - b^2*c)^2*(c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1))^2 - 4*(- 12*(b^4 - 2*b^2 + 1)*c^2*b^4 + 12*(b^4*c - b^2*c)^2 + (c^2*b^4 - b^4 + d^2*b^2 + 2*b^2 - 1)^2)^3))^(1/3)))))

y = sqrt(1 - x^2)/b

In the equation, the ellipse is presumed to have a horizontal radius of 1 and to be centered at (0, 0), $b$ is the reciprocal of the vertical radius of the ellipse flipped such that $b\gt 1$, circle center is at $(c, d)$. Fortunately, the equation has reoccurring subexpressions and can be simplified using additional variables ($e$, $f$, $g$, $h$, $i$, $j$, $k$, $s$, $q$, $m$, $n$, $o$, $s3$, $p$, $s2$):

e = b^4*c^2 f = b^4 - 2*b^2 + 1 g = e - f + d^2*b^2 h = b^2*c i = b^2*h - h j = 72*f*e*g + 2*g^3 + (108*(f - e) + 36*g)*i^2 k = 12*i^2 + g^2 - 12*f*e s = j^2 - 4*k^3 q = (j + sqrt(s))^(1/3) m = b^2 - 1 n = 1/m o = g/(3*f) + g^2*n^2*2^(1/3)/(3*q) + (n^2*q*4^(1/3))/6 s3 = (e - g)*n^2 + o p = sqrt(s3) s2 = (2*e - g)*n^2 - o - (2*h*((e - g)*n^3 - 2/m))/p x = h/(2*m) - p/2 + sqrt(s2)/2 y = sqrt(1 - x^2)/b

Unfortunately, the implementation using limited floating point precision suffers from numerical instability and does not work for all mathematically valid input variable combinations. The highest power of $b$ in the expanded formula is 22, which is the likely cause of the instability. Combined with several early-out checks and other stability fixes, the formula appears to work. It has not been exhaustively tested, so stability is not guaranteed. You can try it out yourself below:

Usage: Drag to resize ellipse. A red dot indicates collision detected using the equation, and the circle and the ellipse turning red indicates collision detected by an early-out check.

Polygonal approximation

A circle can be sandwiched between an inscribed and a circumscribed regular polygon. If the other polygon is rotated by $\frac{\pi}{n}$, where $n$ is the number of corners in each polygon, then the two polygons meet at the corner points of the inscribed polygon, which coincide with the center point of each side of the circumscribed polygon. This forms triangles that enclose the rim of the circle in sections. If new inscribed and circumscribed polygons are drawn that have twice number of corners, then the triangles from these will be inside the old triangles and again enclose the rim of the circle.

Enclosing sections of a circle within regular polygons that meet to create triangles. Doubling the number of corners in the regular polygon creates smaller triangles that fit inside the bigger triangles.

The same works for ellipses, by stretching the polygons along the axes of the ellipse. The triangles that enclose segments of the ellipse can be tested for collision with the circle. If the collision takes place at either of the corner points of the inscribed polygon or along the line segment that connects them, or if the ellipse center is inside the inscribed polygon, then the ellipse and circle have collided. If the collision takes place elsewhere in the triangle, then the triangle can be bisected into two smaller triangles, and the above checks can be repeated. Othewise, there is no collision.

So, one needs first a method to detect collisions of line segments and circles.

Line segment–circle collision detection

First, translate everything so that line start point is (0, 0). This is actually optional, but simplifies the expressions of the resulting coordinates. The translated coordinates are $(a, b)$ for the line segment end point and $(c, d)$ for the circle center, and $r$ is the circle radius. Then do a scaling and rotating transformation akin to complex multiplication:

Considering the (x, y) coordinates as complex numbers x + i y, multiplication of all points belonging to the curves (the circle and the line segment) by (a, -b), the complex conjugate of the line end point (a, b), results in scaling and rotation that conveniently places the line segment on the horizontal axis.

The scaling changes the circle radius from $r$ to $r \sqrt(a^2 + b^2)$, by the rules of complex multiplication. The sign of the new circle vertical coordinate, $d*a - c*b$, tells us on which side of the line the circle center resides. This is not needed for collision detection but may be useful information for something else, and it comes without extra cost as that term will be required anyhow. If the absolute value of the circle center vertical coordinate is greater than the radius, there can be no collision. The squares of those numbers can be more cheaply compared: There can only be a collision if $(da - cb)^2 \le r^2(a^2 + b^2)$, otherwise the algorithm terminates with a negative result. If either of the line segment end points is inside the circle, then there is a collision. This is easy to check for by comparing the squared circle radius to the squared distance between the circle center and each line segment end point: $c^2 + d^2 \le r^2$ for the start or $(a-c)^2 + (b-d)^2 \le r^2$ for the end indicates collision. If neither end point is inside the circle, the circle may still intersect with the middle part of the line segment. This is tested for by comparing the circle horizontal coordinate to the line segment end point coordinates. If the circle is in-between, then there is an intersection: $ca + db \ge 0$ and $ca + db \le a^2 + b^2$ must both be satisfied. Otherwise there is no collision, because that would already have been detected as either of the end points being inside the circle.

Usage: Drag to resize the line segment. Red indicates collision.

Ellipse–circle collision

The line segment–circle intersection test does not require the computation of a division or a square root; neither does an ellipse–circle collision test that employs it, using the enclosing triangle bisection scheme. The algorithm presented here is early-out in the sense that it does not calculate where exactly the collision took place, but terminates when it detects collision or as soon as the possibility of a collision vanishes. Usually, only one or two iterations (bisections) are needed. The algorithm could be modified to calculate also the intersection points, but this would require a great number of iterations in case of a collision. The following application demonstrates the algorithm.

Usage: Drag to resize the ellipse. Red indicates collision.

Approximation error

The maximum number of iterations in the algorithm can be limited to $n$. This gives a polygon with $2^{2+n}$ sides. The shortest distance between the ellipse and any point of the polygon is always less than $2^{0.303-2n}\text{max}(w, h)$, where $w$ and $h$ are the major and minor radii of the ellipse.

Ellipse–ellipse collision

Ellipse–ellipse collision test can be implemented using the polygonal ellipse-circle collision test after stretching of the ellipses so that the other becomes a circle. The calculation will be easier if the ellipses have parallel axes.

a) The ellipses have parallel axes, b) the axes are not parallel

Parallel axes

If the axes are parallel (horizontal and vertical), it suffices to multiply all horizontal coordinates and horizontal radii by the vertical radius of the second ellipse, and all vertical coordinates and vertical radii by the (original) horizontal radius of the second ellipse. This makes the second ellipse a circle.

Non-parallel axes

If the ellipses do not have parallel axes, one could create a transformation matrix $A$ that does a rotation, stretching, and rotation back to make the second ellipse a circle and a rotation to align the major and minor axes of the first ellipse with the horizontal and vertical axes. Unfortunately, the equation needed in the last step for finding the major and minor axes of the first ellipse is very very complicated. It is better to only include the first three transformations in the matrix, and to transform the initial coordinates used in the polygonal algorithm using it. This suffices, because successive iterations of the algorithm use linear combination of coordinates to create coordinates for the smaller polygons; the properties of matrix multiplication are such that $A(aV + bW) = aAV + bAW$ where $A$ is a matrix, $a$ and $b$ are scalars, and $V$ and $W$ are vectors. An appropriate rotation–stretching–back-rotation matrix is:

$A = \left[\begin{array}{cc}hw1\ wx1^2 + wy1^2 & hw1\ wx1\ wy1 - wx1\ wy1\\ hw1\ wx1\ wy1 - wx1\ wy1& hw1\ wy1^2 + wx1^2\end{array}\right]$

where $(wx1, wy1)$ is the major or minor radius vector of the second ellipse and $hw1$ is the ratio between the other radius and that radius. The transformation of coordinates $(x, y)$ is done as:

$\left[\begin{array}{c}x\\ y\end{array}\right] \longmapsto A \left[\begin{array}{c}x\\ y\end{array}\right] = \left[\begin{array}{c}hw1\ wx1\ (wy1\ y + wx1\ x) - wy1\ (wx1\ y - wy1\ x)\\ hw1\ wy1\ (wy1\ y + wx1\ x) + wx1\ (wx1\ y - wy1\ x)\end{array}\right]$

The transformed squared radius of the second ellipse (now circle) is $hw1^2\ (wx1^2 + wy1^2)^3$. The polygonal algorithm can be modified so that it needs only the squared radius. Calculation of the square root is not necessary. The algorithm also remains free of the division operator.

Circle approximation

The segments circumscribing the ellipse in the polygonal algorithm could be replaced by circle segments. This would work at least in the case of ellipse–circle collision.

Iterative subdivision of circles circumscribing an ellipse. The outer boundary of the combined area of the circles circumscribes the ellipse. Either circles or line segments could be used for the inscribing shape.

Source code

You can find the source code for the interactive visualizations written in the Processing language in my openprocessing.org portfolio, or by viewing the source code of this web page.

Ellipse–circle and Ellipse–ellipse collision test, polygonal approximation (C++)

3 Comments »

  1. The problem can be formulated as an eigenvalue problem to achieve an efficient numerical algorithm. Also, you may find this interesting: http://books.google.fi/books?id=8CGj9_ZlFKoC&pg=PA72&lpg=PA72&dq=hill+conic+sections+graphics+gems&source=bl&ots=yAgrQD0rBF&sig=C0lOQy5NHp0ybs1uZU40QJbWkig&hl=en&sa=X&ei=PRHTUfPhJ-bx4QT7oIGICA&redir_esc=y#v=onepage&q=hill%20conic%20sections%20graphics%20gems&f=false

    Comment by sm — 2013-07-02 @ 20:46

  2. sm, can you tell more about the eigenvalue-based algorithm?

    Comment by Olli Niemitalo — 2013-07-13 @ 09:18

  3. Something here:

    @article{ROB:80017,
    author = {Ju,Ming-Yi and Ju,Ming-Yi and Liu,Jing-Sin and Shiang,Shen-Po and Chien,Yuh-Ren and Hwang,Kao-Shing and Lee,Wan-Chi },
    title = {Fast and accurate collision detection based on enclosed ellipsoid},
    journal = {Robotica},
    volume = {19},
    issue = {04},
    month = {7},
    year = {2001},
    issn = {1469-8668},
    pages = {381–394},
    numpages = {14},
    doi = {10.1017/S0263574700003295},
    URL = {http://journals.cambridge.org/article_S0263574700003295},
    }
    http://www.iis.sinica.edu.tw/papers/liu/637-F.pdf

    @MISC{Rimon97obstaclecollision,
    author = {Elon Rimon and Stephen P. Boyd},
    title = { Obstacle Collision Detection Using Best Ellipsoid Fit},
    year = {1997}
    }
    https://www.stanford.edu/~boyd/papers/pdf/obst-coll-det.pdf

    Comment by Olli Niemitalo — 2013-07-17 @ 11:57

RSS feed for comments on this post. TrackBack URL

Leave a comment

Powered by WordPress