Scaled circle to circle collision

Question

How do I make a scaled circle to circle collision? For example: example

I have 2 circles, one circle X and Y size are the same, the other is bigger in the x size.

How do I detect collisions between the two circles?

Answer 1

I must admit I only understand a tiny part of MBo's answer (which sounds solid (+1)).

This is my understanding of his formula:

 - adding x0 and y0 (the first ellipse centre) moves the origin (x0 + ... , y0 + ...)
 - a and b are the two radii of the ellipse (e.g. width / 2, height / 2)
 - t is the angle between the ellipse and the cirle on the right (I think)
 - using the polar to cartesian coordinate conversion formula(*) we get two "sides" of a triangle where the diagonal is the distance to the circle 
 - x = cos(angle) * width/2, y = sin(angle) * height/2, to which add the ellipse offset (x0, y0)
 - x^2 + y^2 = distance^2 (Pythagoras theorem)

  (x0+a*cos(t))^2+(y0+b*sin(t))^2 = D^2

cartesian coordinate conversion formula(*)

What I don't get is the derrivative/differentiation part (because I wasn't paying attention in school and I haven't gone back to learn those properly, yet)

Here's a basic sketch visualising the above and using the fact that we can use atan2(y, x) (where y = circle y - ellipse y and x = circle x - ellipse y) to calculate the angle between the ellipse. Then, using the polar coordinate convertion we can calculate the closest point on the ellipse towards the circle. If the distance between this closest point and the centre of the circle is smaller than the circle's radius then they must intersect.

// e1 - ellipse 1 with 2:1 width to height ratio
float e1x = 200;
float e1y = 200;
float e1w = 200;
float e1h = 100;
// e1 - ellipse 2 with 1:1 widht to height ratio (circle)
float e2x = 400;
float e2y = 200;
float e2w = 100;
float e2h = 100;

void setup(){
  size(600, 400);
  stroke(128);
  strokeWeight(3);
}

void draw(){
  background(32);
  
  fill(255);
  ellipse(e2x, e2y, e2w, e2h);
  
  boolean areE1E2Intersecting = isColliding();
  
  fill(areE1E2Intersecting ? color(0, 192, 0) : color(255));
  ellipse(e1x, e1y, e1w, e1h);
}

boolean isColliding(){
  boolean result = false;
  // calculate angle between e1 and e2
  float angleFromE1ToE2 = atan2(e2y - e1y, e2x - e1x);
  // calculate the point one e1 towards e2 (
  // 0.5 is beacause we want radius not diameter (w,h)
  float xE1ToE2 = e1x + (cos(angleFromE1ToE2) * e1w * 0.5);
  float yE1ToE2 = e1y + (sin(angleFromE1ToE2) * e1h * 0.5);
  // optional: visualise the point
  fill(255, 64);
  stroke(255);
  triangle(xE1ToE2, yE1ToE2,
           xE1ToE2, e2y,
           e2x, e2y);
  ellipse(xE1ToE2, yE1ToE2, 15, 15);
  fill(255);
  stroke(128);
  // if the distance between the closest point on the ellipse towards the circle
  // is smaller than the circle's radius then they're colliding
  result = dist(xE1ToE2, yE1ToE2, e2x, e2y) < e2w * 0.5;
  
  return result;
}

void mouseDragged(){
  e1x = mouseX;
  e1y = mouseY;
}

Drag the mouse to move the ellipse.

The code is a bit verbose, but commented: hopefully easy to follow. It could be refactored as needed for reuse(e.g. remove visualisation, change function so it takes arguments instead of global variables, etc.)

Update

As Mbo pointed out, t is not the angle. With my approach above, you can make minimal tweaks to from ellipse-circle to ellipse-ellipse. (Your question calls both elements circles, although the image shows an ellipse and a circle, hence my snippet above. Your comment clarifies you're after ellipse to ellipse intersection)

You can make minor tweaks to my approach for ellipse to ellipse intersection. Note that is is a rough approximation/not perfect. Notice the points marked as closest to the opposite ellipse. They don't line up with the line between the centres. (I suspect this because I'm using half the width/height the radius in the polar to cartesian conversion which is a bit off (especially at angles in between 90 degree increments)

// ellipse 1
float e1x = 200;
float e1y = 200;
float e1w = 200;
float e1h = 100;
// ellipse 2
float e2x = 400;
float e2y = 200;
float e2w = 200;
float e2h = 300;

void setup(){
  size(600, 400);
  stroke(128);
  strokeWeight(3);
  noFill();
}

void draw(){
  background(32);
  
  stroke(255);
  ellipse(e2x, e2y, e2w, e2h);
  
  boolean areE1E2Intersecting = isColliding();
  stroke(areE1E2Intersecting ? color(0, 192, 0) : color(255));
  ellipse(e1x, e1y, e1w, e1h);
}

boolean isColliding(){
  boolean result = false;
  // calculate angle between e1 and e2
  float angleFromE1ToE2 = atan2(e2y - e1y, e2x - e1x);
  // calculate the point one e1 towards e2 
  // 0.5 is beacause we want radius not diameter (w,h)
  float xE1ToE2 = e1x + (cos(angleFromE1ToE2) * e1w * 0.5);
  float yE1ToE2 = e1y + (sin(angleFromE1ToE2) * e1h * 0.5);
  float radiusFromE1ToE2 = dist(e1x, e1y, xE1ToE2, yE1ToE2);
  
  float angleFromE2ToE1 = PI + angleFromE1ToE2;
  float xE2ToE1 = e2x + (cos(angleFromE2ToE1) * e2w * 0.5);
  float yE2ToE1 = e2y + (sin(angleFromE2ToE1) * e2h * 0.5);
  float radiusFromE2ToE1 = dist(e2x, e2y, xE2ToE1, yE2ToE1);
  
  result = dist(e1x, e1y, e2x, e2y) < (radiusFromE1ToE2 + radiusFromE2ToE1);
  
  // optional: visual debugging
  ellipse(xE1ToE2, yE1ToE2, 15, 15);
  ellipse(xE2ToE1, yE2ToE1, 15, 15);
  line(e1x, e1y, e2x, e2y);
  
  return result;
}

void mouseDragged(){
  e1x = mouseX;
  e1y = mouseY;
}

Note that the above doesn't take into accounts aspect ratios that are very different or differnt ellipse orientations (and your question doesn't mention this at all in it's current form btw).

Doing a quick search I see the math is move involved but there are interesting approximations like Olli's.

There are probably other solutions too and I'd love to see more options in Processing. One brute force/hacky workaround I can think of is using the blendMode(DIFFERENCE) (which will highlight intersection between shapes) then use the loadPixels(); and pixels[] to search for the 1st pixel of the intersection color. If you need to optimise speed (especially for hi-res sketch), you can render a smaller offscreen buffer of your main sketch (via createGraphics()). (This will allow you use the blend mode and different colours from your main sketch graphics if you need to (otherwise calling get() will return a PImage "snapshot" of your sketch which you can resize() as required))

Here's a basic sketch to illustrate the idea:

// e1 - ellipse 1 with 2:1 width to height ratio
float e1x = 200;
float e1y = 200;
float e1w = 200;
float e1h = 100;
// e1 - ellipse 2 with 1:1 widht to height ratio (circle)
float e2x = 400;
float e2y = 200;
float e2w = 200;
float e2h = 300;

void setup(){
  size(600, 400);
  noStroke();
  blendMode(DIFFERENCE);
}

void draw(){
  background(0);
  
  fill(255, 0, 0);
  ellipse(e1x, e1y, e1w, e1h);
  fill(0, 255, 0);
  ellipse(e2x, e2y, e2w, e2h);
  
  
  fill(255);
  text("is colliding: " + isColliding(), 10, 15);
}

boolean isColliding(){
  boolean result = false;
  
  loadPixels();
  int numPixels = pixels.length;
  for(int i = 0 ; i < numPixels; i++){
    // because the ellipse colours are red and green, difference is yellow
    // so that's what we search for
    if(pixels[i] == color(255, 255, 0)){
      return true;
    }
  }
  
  return result;
}

void mouseDragged(){
  e1x = mouseX;
  e1y = mouseY;
}

Answer 2

Shift coordinate system to make origin in circle center. Let ellipse center now is x0, y0. Write squared distance from origin to ellipse

(x0+a*cos(t))^2+(y0+b*sin(t))^2 = D^2

and find minimum: differentiate by t, make derivative=0, solve for unknown t, get point closest to origin (seems quartic equation should be solved)

If distance is smaller than circle radius, intersection does exist.

Update. How it should work:
Distance from origin to ellipse is minimal distance to all ellipse points. It is known from math. analysis that in point of minimum of function F(t) it's derivative F'(t)==0 (when function reaches miminum or maximum, derivative changes it's sign). So we can get equation of function derivative, get it's zeros and find point where function has minumum (we must also check that it is not maximum, and the second derivative is not zero F''(t) != 0). Distance function is too complex for these purposes (sqrt's causes long derivative expression), but luckily squared distance has the same extrema as distance, so we can just write x^2+y^2 for points of ellipse, parametrized by some convenient way, get derivative, find munimum.

Axis-aligned ellipse with semi-axes a and b and center x0,y0 hase equation

x = x0+a*cos(t)
y = y0+b*sin(t)

and squared distance formula is given above. It's derivative (by variable t)

d(D2)/dt = -2*a^2*cos(t)*sin(t)+2*b^2*cos(t)*sin(t)-x0*a*sin(t)+y0*b*cos(t) = 0

To solve this equation, we can make substitution of cos and sin using half-angle tangent formulas, and result will be quartic (t-th degree) polynomial for unknown u=tan(t/2). I don't want to make these formulas here because they are quite long, and I'm not sure they are easy usable. Perhaps there are some libraries implementing point-ellipse distance. BTW, I found that here similar approach is described with code, bit also look at other answers - looks like numerical approach (like this one) is much simpler to implement.