Thread: How to check if two circles intersects each other?

  1. #1
    Registered User
    Join Date
    Feb 2002
    Posts
    37

    How to check if two circles intersects each other?

    How can you check if two circles intersects each other in one way or another? The intersect function in CCircle.cpp is the one that I am having trouble with.

    This is what I have done so far.

    Code:
    #ifndef _CPOINT_H_
    #define _CPOINT_H_
    
    class CPoint
    {
    public:
    	CPoint();
    	CPoint(int x, int y);
    	int getX() const;
    	int getY() const;
    private:
    	int m_x;
    	int m_y;
    };
    
    #endif
    ///////////////////////////////////////

    Code:
    #include "CPoint.h"
    
    CPoint::CPoint()
    {
    	m_x = 0;
    	m_y = 0;
    }
    
    CPoint::CPoint(int x, int y)
    {
    	m_x = x;
    	m_y = y;
    }
    
    int CPoint::getX() const
    {
    	return m_x;
    }
    
    int CPoint::getY() const
    {
    	return m_y;
    }
    ///////////////////////////////////////

    Code:
    #ifndef _CCIRCLE_H_
    #define _CCIRCLE_H_
    
    #include "CPoint.h"
    
    class CCircle : public CPoint
    {
    public:
    	CCircle();
    	CCircle(int x, int y, double r);
    	double getRadius() const;
    	bool instersect(CCircle & c);
    private:
    	double m_radius;
    };
    
    #endif
    ///////////////////////////////////////

    Code:
    #include "CCircle.h"
    
    CCircle::CCircle()
    {
    	CPoint(0, 0);
    	m_radius = 0.0;
    }
    
    CCircle::CCircle(int x, int y, double r) : CPoint(x, y)
    {
    	m_radius = r;
    }
    
    double CCircle::getRadius() const
    {
    	return m_radius;
    }
    
    bool CCircle::instersect(CCircle & c)
    {
    	bool intersected = false;
    
    	/* Insert more code!!! */
    
    	return intersected;
    }
    ///////////////////////////////////////

    Code:
    #include "CCircle.h"
    
    int main()
    {
    	CCircle a(2, 3, 5.5);
    	CCircle b(0, 1, 4.0);
    
    	a.instersect(b);
    
    	return 0;
    }
    ///////////////////////////////////////

    Thanks.

  2. #2
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Basic form of a circle:
    (x - h)^2 + (y - k)^2 = r^2

    So lets see if a circle centered at 0,0 with radius 3 and a circle centered at 4,5 with radius 2 intersect.

    x^2 + y^2 = 9
    (x-4)^2 + (y-5)^2 = 4

    Here you simply use your favorite method for solving two equations with two unknowns.

    If you get a valid point then they intersect. Just make sure you test for the both the + and the - for the sqareroots

  3. #3
    Registered User
    Join Date
    Apr 2002
    Posts
    1,571
    A fast method for determining circle-circle intersection is as follows:

    Compute the distance between the two circle's centers and then you simply reject if this distance is greater than the sum of the two spheres' radii.

    Pseudo code:
    Code:
    inline float DotProduct(Point &lhs, Point &rhs)
    {
      return lhs.x * rhs.x + lhs.y * rhs.y;
    }
    
    bool SphereIntersect(Point &c1, float r1, &Point c2, float r2)
    {
      Point dist = c1 - c2;
      float distSq = DotProduct(dist, dist);
      
      if(distSq > ((r1 + r2) * (r1 + r2)))
        return false; // no intersection
    
      return true; // intersection
    }
    "...the results are undefined, and we all know what "undefined" means: it means it works during development, it works during testing, and it blows up in your most important customers' faces." --Scott Meyers

  4. #4
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Ohhh good method MrWizard, will have to remember that one for my math classes (BTW I hate graphing)

  5. #5
    Registered User
    Join Date
    Apr 2002
    Posts
    1,571
    Yea, it's pretty fast and dirty. The obvious way to implement what I describe first is to use the standard method of calculating the magnitude of a vector between the circles and compare that result but that requires a square root which can be pretty slow. So if you square each side you can remove that and use the dot product instead.
    "...the results are undefined, and we all know what "undefined" means: it means it works during development, it works during testing, and it blows up in your most important customers' faces." --Scott Meyers

  6. #6
    Registered User
    Join Date
    Feb 2002
    Posts
    37
    It works, thanks.

  7. #7
    Registered User
    Join Date
    Feb 2004
    Posts
    35

    Smile

    Circles are great. They're real easy to calculate, and are the average shape of all objects at all angles.
    No wonder they're so popular in game physics.

  8. #8
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote Originally Posted by MrWizard
    A fast method for determining circle-circle intersection is as follows:

    Compute the distance between the two circle's centers and then you simply reject if this distance is greater than the sum of the two spheres' radii.
    What about the case where one circle is completely inside the other?


    Dave

  9. #9
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Quote Originally Posted by Dave Evans
    What about the case where one circle is completely inside the other?


    Dave
    then their area's are intersecting. To find perimeter intersection you need an approach like thantos described. The OPer should note that this is a good point though, if your looking for perimeter intersection the radii/distance method will fail in this case.

  10. #10
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote Originally Posted by Perspective
    then their area's are intersecting. To find perimeter intersection you need an approach like thantos described. The OPer should note that this is a good point though, if your looking for perimeter intersection the radii/distance method will fail in this case.
    The title of the original post was "How to check if two circles intersects each other?"

    A circle is the set of all points in a plane at a fixed distance, called the radius, from a fixed point, called the center. (The region enclosed by a circle in the real plane is called the interior of the circle.)

    Give two distinct circles in the real plane, the intersection of two distinct circles is one (and only one) of the following:

    Two real points.

    One degenerate real point. (The case where they touch at exactly one point).

    Two imaginary points. (I'm guessing he would be interested the previous cases, not this. But I put it here for completeness.)

    These are the only possible solutions of equations of the type that Thantos used in his example.

    Dave
    Last edited by Dave Evans; 08-31-2004 at 10:01 AM.

  11. #11
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    You also forget the case where they touch at infinatly many points Dave (Ie same circle different formula)

  12. #12
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote Originally Posted by Thantos
    You also forget the case where they touch at infinatly many points Dave (Ie same circle different formula)
    I did say distinct circles. (Just seeing if you were paying attention.)

    Regards,

    Dave

  13. #13
    Registered User
    Join Date
    Feb 2004
    Posts
    35
    Well, it's easy enuff in concept, innit?
    Code:
    if ((dist > rad1 + rad2) || (dist < abs(rad1 - rad2)))
       bIntersecting = false;
    else
       bIntersecting = true;

  14. #14
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Quote Originally Posted by MortalMonkey
    Well, it's easy enuff in concept, innit?
    Code:
    if ((dist > rad1 + rad2) || (dist < abs(rad1 - rad2)))
       bIntersecting = false;
    else
       bIntersecting = true;
    Looks good to me. You would use >= and <= to take care of the cases where they intersect at exactly one point, if those are supposed to be included.

    Dave


    (The opinions expressed here are not necessarily my own --- it's these dang voices in my head.)

  15. #15
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    I like that.

    **runs off to grab a notepad**
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. BN_CLICKED, change button style
    By bennyandthejets in forum Windows Programming
    Replies: 13
    Last Post: 07-05-2010, 11:42 PM
  2. How can i check a directory for certain files?
    By patrioticpar883 in forum C++ Programming
    Replies: 13
    Last Post: 02-01-2008, 05:27 PM
  3. how to check input is decimal or not?
    By kalamram in forum C Programming
    Replies: 3
    Last Post: 08-31-2007, 07:07 PM
  4. Please check this loop
    By Daesom in forum C++ Programming
    Replies: 13
    Last Post: 11-02-2006, 01:52 AM
  5. check my code ( if statement, file existance )
    By Shadow in forum C Programming
    Replies: 1
    Last Post: 10-04-2001, 11:13 AM