Search code examples
javageometryprocessingcollision

Scaled circle to circle collision

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?

Solution

  • 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.

    ellipse to circle intersection visualisation: a white ellipse is dragged towards a white circle on a dark gray background. A triangle is drawn from the closest point on the ellipse towards the circle as the diagonal (and x, y axes as the sides). When the ellipse and circles collide the background of the ellipse turns green.

    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;
}

    enter image description here

    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;
}

    enter image description here