How do I check for collision between an ellipse and a rectangle?

I’m going to tell you how to do it with a computationally cheap way in terms of CPU usage.

First, let’s say that the calculation of seking if a point is “inside the ellipse or not” is not computationally cheap, while comparing just rectangles with mere “greater than” or “less than” comparisons are ultra cheap.

Definition 1) Ellipse and its quadrants

If the perspective is isometric I’m going to assume that the axes of the ellipse E are always horizontal and vertical.

The axes define 4 quadrants Q around the center of the ellipse E as seen in the following picture. Let’s name them like this:

• QTL = Quadrant Top Left
• QTR = Quadrant Top Right
• QBL = Quadrant Bottom Left
• QBR = Quadrant Bottom Right

Note that the quadrant is all the area defined by the axes, like for example, the blue area for QBR, which comprises the area inside the ellipse and the area outside it, despite of where the labels are set in the image.

Definition 2) Ellipse and its bounding box

Now let’s define a bounding box B around the ellipse E, like in this image:

Now let’s focus in the areas of the quadrants that belong to the inside of the bounding box. Let me give the Exx names for the areas inside the ellipse and the Dxx names for the “diff” of the bounding box less the ellipse (so the bounding box area that is not inside the ellipse).

Those are the names for the areas inside the ellipse:

• ETL = Ellipse Top Left
• ETR = Ellipse Top Right
• EBL = Ellipse Bottom Left
• EBR = Ellipse Bottom Right

And these for the “diff areas” (the ones inside B but outside E):

• DTL = Diff Top Left
• DTR = Diff Top Right
• DBL = Diff Bottom Left
• DBR = Diff Bottom Right

Definition 3) Enemy rectangles

Additionally, watching your images, I’m going to imagine that the enemies are always bound with a rectangle R whose sides are exactly horizontal and vertical.

Also, I am going to use only the 4 vertexes V of the rectagle and forget about the intermediate points you used.

Algorithm

Step 1. Check the bounding box

If the enemy rectangle R is outside the bounding box B then for sure it is outside the ellipse E.

Checking this first saves a lot of calculation as you forget expensive calculations to discard a lot of rectangles (and most of the time enemies shall be far).

You can check if R is outside B by checking each 4 sides:

R is outside B if and only if:

• The bottom side of R is higher than the top side of B OR
• The top side of R is lower than the bottom side of B OR
• The left side of R is more to the right than the right side of B OR
• The right side of R is more to the left than the left side of B.

In other words: If any of those conditions are met, then the enemy R is outside the bounding box B. This is the same than saying than if all those conditions are false, then R shares some area with B.

If the enemy R is outside the bounding box B set collision to false and end the algorithm here.

Note that checking the bounding box is a cheap operation.

Step 2. Quadrant check

If you are here, it means that your enemy R shares at least one small area with the bounding box B, and we require further analysis to see if the enemy collides or not with the ellipse E.

Look at this image:

I have painted rectangles of 3 types here. The green and yellow rectangles share a common characteristic: All the 4 vertexes of the rectangle R fall in the very same quadrant. And this does not ensure if the enemy R collides with the ellipse E or not.

Instead, all the red rectangles also share not only one characteristic, but two:

• Feature 1: All the red rectangles have vertexes that do not fall in
  the same quadrant.
• Feature 2: All the red rectangles collide with the
  ellipse.

Why this happens? Because the red rectangles all cross, at least, one axis. And the axis points that are crossed are necessary inside the ellipse, as if R crossed an axis outside the ellipse we would have catched that R while checking the bounding box, as the bounding box is precisely the limit where the axes change from “inside the ellipse” to the “outside of it”.

So if one rectangle not catched in step 1, then, in step 2, has vertexes in different quadrants, then necessarily it happens that some points of some axis that are also contained in the ellipse E are shared with the rectangle R. This means that the rectangle R for sure collides with E at least on those axis points and for sure all non-axis points surrounding the points mentioned before, to the extent of the limit of R or E whichever comes first.

So… if a rectangle has vertexes in any different quadrant than the other vertexes of itself, just mark collision = true and exit the algorithm.

Note that checking if all vertexes fall in the same quadrant is merely checking coordinates with “greater than” or “less than” comparisons, so it’s a cheap operation.

Step 3. Ellipse check.

So, finally, we enter step 3 only with green and yellow rectangles. Ie: it’s a pre-requisite we may assume. Enemies R here shall match that:

• They collide with the bounding box.
• All the vertexes of R fall in a single quadrant.

We can then conclude that:

• ‘At least one vertex’ shall lie in the part of the area of the quadrant that is within the bounding box.
• Which is the same to say that ‘at least one vertex’ shall lie either in the Exx area or the Dxx area.
• And which is that vertex? This happens at least to the ‘nearest vertex to the center of the ellipse’.

So we can reformualte the conclussion as:

• The vertex V of the rectangle R which is nearest to the center of the ellipse E must fall necessarily in the ellipse area Exx or the diff area Dxx.

But it also happens that, by Reductio ad absurdum we can say that:

• If the nearest vertex defined above falls in in the diff area Dxx (ie: does not fall inside the ellipse) then no other point P in the enemy R can be touching the ellipse. The demonstration is that if with this hypotheses we could find another point P that was touching the ellipse E then the tested vertex V could not be the nearest to the center of the ellipse which contradicts the hypotheses.

We don’t care if “the other vertexes” are inside or outside the box. And you don’t have to do complex maths to select the nearest vertex… just it is straight forward:

• For the Top Left quadrant, choose the Bottom Right vertex of R.
• For the Top Right quadrant, choose the Bottom Left vertex of R.
• For the Bottom Left quadrant, choose the Top Right vertex of R.
• For the Bottom Right quadrant, choose the Top Left vertex of R.

Those vertexes are highlighted in the green and yellow rectangles of the picture.

Just then test one single selected vertex with the expensive maths. Test that vertex against the ellipse.

Set the collision flag if the selected vertex is in the ellipse area Exx, otherwise the vertex shall lie in Dxx and leave collision clear.

Computationally the cost of this 3rd step is just one single complex calculation at most. Never more than 1 vertex per rectangle.

End of the algorithm.

I hope I have helped! Cheers.