Determine where two circles intersect (C++)

Given two circles in 2D by their centers and radiuses, we can easily and efficiently determine the intersection point(s), if any, without using trigonometric functions, which are a minus when it comes to performance.

The code below is based on the mathematical explanation here, except from one thing, which is wrong and Thomas Poulis corrected. The case that the one circle contains the other, is true, if the euclidean distance of the circles plus the radius of the smaller circle, is less than the radius of the bigger one.

iCircles.cpp

/* 
 * File:   main.cpp
 * Author: SAMARAS
 *
 * 13/10/13
 */

#include <cstdlib>
#include <iostream>
#include <cmath>

#ifndef max
  #define max(a,b) (((a) > (b)) ? (a) : (b))
#endif
#ifndef min
  #define min(a,b) (((a) < (b)) ? (a) : (b))
#endif

/*
 * Find the intersection point(s) of two circles,
 * when their centers and radiuses are given (2D).
 */

class Point2d{
public:
    Point2d() {}
    Point2d(double x, double y)
        : X(x), Y(y) {}
    
    double x() const { return X; }
    double y() const { return Y; }
    
    /**
     * Returns the norm of this vector.
     * @return the norm
    */
    double norm() const {
        return sqrt( X * X + Y * Y );
    }
    
    void setCoords(double x, double y) {
        X = x; Y = y;
    }
    
    // Print point
    friend std::ostream& operator << ( std::ostream& s, const Point2d& p )  {
      s << p.x() << " " << p.y();
      return s;
    }
private:
    double X;
    double Y;
};

class Circle{
public:
    /**
     * @param R - radius
     * @param C - center
     */
    Circle(double R, Point2d& C) 
        : r(R), c(C) {}
        
    /**
     * @param R - radius
     * @param X - center's x coordinate
     * @param Y - center's y coordinate
     */
    Circle(double R, double X, double Y) 
        : r(R), c(X, Y) {}    
    
    Point2d getC() const { return c; }
    double getR() const { return r; }
    
    size_t intersect(const Circle& C2, Point2d& i1, Point2d& i2) {
        // distance between the centers
        double d = Point2d(c.x() - C2.c.x(), 
                c.y() - C2.c.y()).norm();
        
        // find number of solutions
        if(d > r + C2.r) // circles are too far apart, no solution(s)
        {
            std::cout << "Circles are too far apart\n";
            return 0;
        }
        else if(d == 0 && r == C2.r) // circles coincide
        {
            std::cout << "Circles coincide\n";
            return 0;
        }
        // one circle contains the other
        else if(d + min(r, C2.r) < max(r, C2.r))
        {
            std::cout << "One circle contains the other\n";
            return 0;
        }
        else
        {
            double a = (r*r - C2.r*C2.r + d*d)/ (2.0*d);
            double h = sqrt(r*r - a*a);
            
            // find p2
            Point2d p2( c.x() + (a * (C2.c.x() - c.x())) / d,
                    c.y() + (a * (C2.c.y() - c.y())) / d);
            
            // find intersection points p3
            i1.setCoords( p2.x() + (h * (C2.c.y() - c.y())/ d),
                    p2.y() - (h * (C2.c.x() - c.x())/ d)
            );
            i2.setCoords( p2.x() - (h * (C2.c.y() - c.y())/ d),
                    p2.y() + (h * (C2.c.x() - c.x())/ d)
            );
            
            if(d == r + C2.r)
                return 1;
            return 2;
        }
    }
    
    // Print circle
    friend std::ostream& operator << ( std::ostream& s, const Circle& C )  {
      s << "Center: " << C.getC() << ", r = " << C.getR();
      return s;
    }
private:
    // radius
    double r;
    // center
    Point2d c;
    
};
int main(void)
{
    // radius and center of circles
    Circle c1(2, 0, 0);
    Circle c2(1, 0, 2);
    Point2d i1, i2;
    
    std::cout << c1 << "\n" << c2 << "\n";
    // intersections point(s)
    size_t i_points = c1.intersect(c2, i1, i2);
    
    std::cout << "Intersection point(s)\n";
    if(i_points == 2)
    {
        std::cout << i1 << "\n";
        std::cout << i2 << "\n";
    }
    else if(i_points)
        std::cout << i1 << "\n";
    
    return 0;
}

Have questions about this code? Comments? Did you find a bug? Let me know!😀
Page created by G. (George) Samaras (DIT)

3 thoughts on “Determine where two circles intersect (C++)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s