Circle-Rectangle collision detection finished exampe

Question

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

EDIT:

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

There is a complete implementation of circle/rectangle collision detection in the question you linked to. Beyond that, I doubt anyone will be willing to help unless you make an earnest effort and show your attempts. — patros, Oct 15 '09 at 18:53

score 1 · Answer 1 · answered Oct 15 '09 at 19:23

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

Thank you very much :) I am trying to put this in my code, and also implement the missing "pointInRectangle" function, but I do not understand the description of the "pointInRectangle": 0 ≤ AP·AB ≤ AB·AB and 0 ≤ AP·AD ≤ AD·AD I guess "AP" is the line "rectangle.a to p" right? But how can I multiply a point that consists of two variables to anything? Thank you — Neigaard, Oct 16 '09 at 10:59
Hi Jerry, do you have time to look at my attempt and help me out? — Neigaard, Oct 17 '09 at 05:29

score 1 · Answer 2 · answered Oct 18 '09 at 06:43

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.

Circle-Rectangle collision detection finished exampe

2 Answers2

Linked