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.

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

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
}

Ohhh good method MrWizard, will have to remember that one for my math classes (BTW I hate graphing)

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.

It works, thanks.

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.

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

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.

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

You also forget the case where they touch at infinatly many points Dave (Ie same circle different formula)

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

Well, it's easy enuff in concept, innit?

Code:

if ((dist > rad1 + rad2) || (dist < abs(rad1 - rad2)))
   bIntersecting = false;
else
   bIntersecting = true;

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

I like that.

**runs off to grab a notepad**