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)
Thank you soo much dude !!! You saved me on this one !
Thank you so much dude ! You saved me with this code !!
That’s good news!
Thanks a lot, works great!