Circle-Rectangle collision detection finished exampe

Question

Hi

I need a algorithm for detecting if a circle has hit a square, and I saw this post: Circle-Rectangle collision detection (intersection)

It looks like I should go for ShreevatsaR's answer, but I am a math fool, and I have no idea how to finish the algorithm. Could anyone find the time to make a complete example for me please, I have searched the net for this, and have yet found no working example.

Thank you very much
Soeren

Answer 1

The primary part he seems to have left is the InteresectsCircle(line, circle).

#include <math.h>

typedef struct {
    double x;
    double y;
} point;

typedef struct {
    point one;
    point two;
} segment;

typedef struct { 
    point center;
    double radius;
} circle;

double slope(point &one, point &two) {
    return (double)(one.y-two.y)/(one.x-two.x);
}

double distance(point &p, segment &s) {
// Line one is the original line that was specified, and line two is 
// the line we're constructing that runs through the specified point, 
// at a right angle to line one.
//

    // if it's a vertical line return the horizontal distance
    if ( s.one.x == s.two.x)    
      return fabs(s.one.x - p.x);

    // if it's a horizontal line return the vertical distance
    if ( s.one.y == s.two.y )  
      return fabs(s.one.y - p.y); 

    // otherwise, find the slope of the line
    double m_one = slope(s.one, s.two); 

    // the other slope is at a right angle.
    double m_two = -1.0 / m_one;  

    // find the y-intercepts.
    double b_one = s.one.y - s.one.x * m_one; 
    double b_two = p.y - p.x * m_two;

    // find the point of intersection
    double x = (b_two - b_one) / (m_one - m_two); 
    double y = m_one * x + b_one;

    // find the x and y distances
    double x_dist = x - p.x;  
    double y_dist = y - p.y;

    // and return the total distance.
    return sqrt(x_dist * x_dist + y_dist * y_dist); 
}

bool IntersectsCircle(segment s, circle c) { 
    return distance(circle.center, s) <= circle.radius;
}

Answer 2

Ok here is my attempt. It is not working, it never detects any collisions.

typedef struct {
    double x;
    double y;
} point;

typedef struct {
    point one;
    point two;
} segment;

typedef struct { 
    point center;
    double radius;
} circle;

typedef struct {
    point p;
    int width;
    int height;
    point a;
    point b;
    point c;
    point d;
} rectangle;

double slope(point one, point two) {
    return (double)(one.y-two.y)/(one.x-two.x);
}

double distance(point p, segment s) {
    // Line one is the original line that was specified, and line two is 
    // the line we're constructing that runs through the specified point, 
    // at a right angle to line one.
    //

    // if it's a vertical line return the horizontal distance
    if ( s.one.x == s.two.x)    
     return fabs(s.one.x - p.x);

    // if it's a horizontal line return the vertical distance
    if ( s.one.y == s.two.y )  
     return fabs(s.one.y - p.y); 

    // otherwise, find the slope of the line
    double m_one = slope(s.one, s.two); 

    // the other slope is at a right angle.
    double m_two = -1.0 / m_one;  

    // find the y-intercepts.
    double b_one = s.one.y - s.one.x * m_one; 
    double b_two = p.y - p.x * m_two;

    // find the point of intersection
    double x = (b_two - b_one) / (m_one - m_two); 
    double y = m_one * x + b_one;

    // find the x and y distances
    double x_dist = x - p.x;  
    double y_dist = y - p.y;

    // and return the total distance.
    return sqrt(x_dist * x_dist + y_dist * y_dist); 
}

bool intersectsCircle(segment s, circle c) { 
    return distance(c.center, s) <= c.radius;
}

bool pointInRectangle(point p, rectangle r)
{
    float right = r.p.x + r.width;
    float left = r.p.x - r.width;
    float top = r.p.y + r.height;
    float bottom = r.p.y - r.height;
    return ((left <= p.x && p.x <= right) && (top <= p.y && p.y <= bottom));
}

bool intersect(circle c, rectangle r) {
    segment ab;
    ab.one = r.a;
    ab.two = r.b;
    segment bc;
    ab.one = r.b;
    ab.two = r.c;
    segment cd;
    ab.one = r.c;
    ab.two = r.d;
    segment da;
    ab.one = r.d;
    ab.two = r.a;
    return pointInRectangle(c.center, r) ||
          intersectsCircle(ab, c) ||
          intersectsCircle(bc, c) ||
          intersectsCircle(cd, c) ||
          intersectsCircle(da, c);
}

Answer 3

I have some code in C++ (lightly templated) that should do these intersection tests, but I haven't had time to test them yet. In particular, I have the segment-circle intersection test as well as parallelogram-circle intersection, which is supposed to compute the intersection area and intersection points. Again, this is completely untested as of the writing of this comment, so you will need to test/adapt them to your needs.