"check" If two different geometric shapes objects collide

Question

I'm just trying to "check" If two different geometric shapes objects collide. One is a circle and the second one is a square. I have searched google to find a simple example and learn from it, because I don't know how to do that. I found this example, tried it, but nothing happened. There most be a bug in the code. Please help me to correct it in C or C++ language.

bool Collision(int circleX, int circleY, int radius, int squareX, int squareY, int width, int height)
{
    int distance = 0;

    if(circleX < squareX) 
        distance += pow(circleX - boxX,2); //x-axis
    else if (circleX > squareX + width)
        distance += pow(circleX - squareX - width, 2);

    if(circleY < squareY) 
        distance += pow(circleY - squareY,2); //y-axis
    else if (circleY > squareY + height) 
        distance += pow(circleY - squareY - height, 2);

    if( distance <= pow(radius, 2))
        return true; 
    else    
        return false;
}

Answer 1

Firstly, let's clear how to represent a circle and a square.

In convention, the square the represented as follows:

  squarexX, squareY + height  ------------ squareX+ width, squareY +height
  |                                               |
  |                                               |
   squareX, squareY          ------------- squareX + width, squareY

While circle is represented by coordinates of the circle (circleX, circleY) and radius value. With this in mind, you should be able to even code your own function. NOTE that there is not width or height for a circle.

So in their code:

 if(circleX < squareX) distance += pow(circleX - boxX,2); //x-axis

should be

 if(circleX < squareX) distance += pow(circleX - squareX,2); //x-axis

The idea for deciding whether a square has overlaps/collides with a circle is as follows:

1. assume that square is located at origin of 2D plane, if it is not, we can shift the origin to center of square
2. Next, find out the distance between the circle and the closest edge intersection point of the square, if this distance is larger than radius, no overlap, otherwise, overlap. A special case is that if circle is located inside square, then the so called intersection point is the center of the circle itself. In this case, testForCollision will return true.

complete function should look like the following:

//this function computes the distance between center of circle
//to closest point on one of the edges of square, that edge is on the
//same side as the circle
#include <algorithm>
bool testForCollision(int circleX, int circleY, int width, int height, int radius)
{   

    int dx = std::min(circleX, (int)(width  * 0.5));
    int dx1 = std::max(dx, (int)(-width *0.5));

    int dy = std::min(circleY, (int)(height * 0.5));
    int dy1 = std::max(dy, (int)(-height * 0.5));

    return (dx1 - circleX) * (dx1 - circleX) 
           + (dy1 - circleY) * (dy1 - circleY) <= radius * radius;
}


bool Collision(int circleX, int circleY, int radius, 
               int squareX, int squareY, int width, int height)
{

    //get center of square
    int center_of_square_x = squareX + width/2;
    int center_of_square_y = squareY + height/2;

    //if square is already at origin, test directly
    if ( center_of_square_x == 0 && center_of_square_y ==0)
    {
        return testForCollision(circleX, circleY, width, height, radius);
    }
    else
    {
        //shift center of square to origin and update coordinates of circle
        //only consider part of the situation, more to add about shifting
        circleX = circleX - center_of_square_x;
        circleY = circleY - center_of_square_y;
        return testForCollision(circleX, circleY, width, height, radius);
    }
}

This way, it should be able to identity whether the circle and square collide with each other.

EDIT: let us walk through one test case:

circleX = 60 circleY = 172 radius = 39
squareX = 120 squareY = 180 width = 72 height = 72 

We have coordinates for the square as follows (including center)

120, 252  -------- 192, 252
 |                   |
 |--------156,216----|
 |                   |
120,180   ---------192,180

We can see that (60,172) locates of the left of edge (120,252)-->(120,180), distance between (120,180) and (60,72) is larger than 39. distance between (120,252) and (60,72) is also larger than 39, no overlap. To understand it better, given center of circle (60,172) and radius 39, the range of x and y you can reach from the center of the circle is from (60-39,60 +39) = (21,99) and (172-39, 172+39) = (133,211). This should be no overlap with the square if you visualize it.

If you first transform the origin to (156,216), we have (-96,-44) for the center of the circle in new coordinates system. it is located on 3rd quadrant. if you run the testForCollision function, you will see that there is no overlap.

dx = min(-96,36) = -96
dx1 = max(dx, -36) = -36
dy = min(-44, 36) = -44
dy1 = max(dy,-36) = -36

distance = (-36 - (-96))^2 + (-36 - (-44))^2 = 60^2 + 8^2 > 39^2, so no overlap

Answer 2

There are 3 cases:

• the shapes overlap, and therefore an edge of one shape crosses the edge of the other shape
• the circle completely inside the square (e.g. imagine huge rectangle with a tiny circle in it somewhere)
• the rectangle completely inside the circle (e.g. imagine huge circle with a tiny rectangle in it)

First determine the distance between the centre of the circle and the centre of the rectangle. Let's call this distance D.

Then find the largest circle that is small enough to fit inside the rectangle. This will have a diameter that is equal to either the rectangle's height or the rectangle's width (whichever is smaller). If the radius of the new circle plus the radius of the original circle is less than the distance D then there's definitely a collision.

Then find the smallest circle that is large enough to contain the entire rectangle. The radius of this circle can be found with Pythagoras (distance from centre of rectangle to any corner of the rectangle). If the radius of this new circle plus the radius of the original circle is greater than the distance D then there can't be any collision.

If both of these tests don't give you an answer; then neither shape is completely inside the other but it is possible for them to be overlapping or not overlapping; and therefore you have to determine if an edge of one shape crosses the edge of the other shape. To do this, extend all the rectangle's edges so that they're infinite length (use the line segment to describe a line); and try to calculate where these infinite length lines intersect with the circumference of the circle by "plugging in" either the x or the y into the formula of a circle (note: You will either find no intersection, 1 intersection or 2 intersections). If there are 2 intersections you have to test if either is one the edge.

For example, if you rectangle's top edge is at y = 2 you'd plug y = 2 into your formala for a circle. If you find that this line intersects at x = 3 and at x = 6`, then test if both 3 and 6 are between the left edge of the rectangle and the right edge of the rectangle - if they are then the edge of the circle intersects with the top edge of the rectangle and you have a collision.

If you do the "edge intersection" test for all 4 edges of the rectangle without detecting a collision, then there's no collision to detect.