Ellipse–circle and ellipse–ellipse collision detection

Created by Olli Niemitalo on 2012-07-25, last modified 2013-03-07

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.

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:

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.

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.

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++)