Find Intersecting Point Of Three Circles Programmatically

As the title says, I have 3 Circle. Each one have different radius. I know the radius of each circles. Also know the center points of each circle. Now I need to know how I can cal

Solution 1:

You could get help from this C code. Porting it to Java should not be challenging. Explanation is here. Search for/scroll to: intersection of two circles

Using this method, find the intersection of any two circles, let's say (x,y). Now the third circle will intersect at point x,y only if distance between its center and point x,y is equal to r.

1. If distance(center,point) == r, then x,y is the intersection point.

2. If distance(center,point) != r, then no such point exists.

Code (ported from here; all credit goes to original author):

private boolean calculateThreeCircleIntersection(double x0, double y0, double r0,
                                                 double x1, double y1, double r1,
                                                 double x2, double y2, double r2){
    double a, dx, dy, d, h, rx, ry;
    double point2_x, point2_y;

    /* dx and dy are the vertical and horizontal distances between
    * the circle centers.
    */
    dx = x1 - x0;
    dy = y1 - y0;

    /* Determine the straight-line distance between the centers. */
    d = Math.sqrt((dy*dy) + (dx*dx));

    /* Check for solvability. */if (d > (r0 + r1))
    {
        /* no solution. circles do not intersect. */returnfalse;
    }
    if (d < Math.abs(r0 - r1))
    {
        /* no solution. one circle is contained in the other */returnfalse;
    }

    /* 'point 2' is the point where the line through the circle
    * intersection points crosses the line between the circle
    * centers.
    *//* Determine the distance from point 0 to point 2. */
    a = ((r0*r0) - (r1*r1) + (d*d)) / (2.0 * d) ;

    /* Determine the coordinates of point 2. */
    point2_x = x0 + (dx * a/d);
    point2_y = y0 + (dy * a/d);

    /* Determine the distance from point 2 to either of the
    * intersection points.
    */
    h = Math.sqrt((r0*r0) - (a*a));

    /* Now determine the offsets of the intersection points from
    * point 2.
    */
    rx = -dy * (h/d);
    ry = dx * (h/d);

    /* Determine the absolute intersection points. */double intersectionPoint1_x = point2_x + rx;
    double intersectionPoint2_x = point2_x - rx;
    double intersectionPoint1_y = point2_y + ry;
    double intersectionPoint2_y = point2_y - ry;

    Log.d("INTERSECTION Circle1 AND Circle2:", "(" + intersectionPoint1_x + "," + intersectionPoint1_y + ")" + " AND (" + intersectionPoint2_x + "," + intersectionPoint2_y + ")");

    /* Lets determine if circle 3 intersects at either of the above intersection points. */
    dx = intersectionPoint1_x - x2;
    dy = intersectionPoint1_y - y2;
    double d1 = Math.sqrt((dy*dy) + (dx*dx));

    dx = intersectionPoint2_x - x2;
    dy = intersectionPoint2_y - y2;
    double d2 = Math.sqrt((dy*dy) + (dx*dx));

    if(Math.abs(d1 - r2) < EPSILON) {
        Log.d("INTERSECTION Circle1 AND Circle2 AND Circle3:", "(" + intersectionPoint1_x + "," + intersectionPoint1_y + ")");
    }
    elseif(Math.abs(d2 - r2) < EPSILON) {
        Log.d("INTERSECTION Circle1 AND Circle2 AND Circle3:", "(" + intersectionPoint2_x + "," + intersectionPoint2_y + ")"); //here was an error
    }
    else {
        Log.d("INTERSECTION Circle1 AND Circle2 AND Circle3:", "NONE");
    }
    returntrue;
}

Call this method as follows:

calculateThreeCircleIntersection(-2.0, 0.0, 2.0, // circle 1 (center_x, center_y, radius)
                                  1.0, 0.0, 1.0, // circle 2 (center_x, center_y, radius)0.0, 4.0, 4.0);// circle 3 (center_x, center_y, radius)

Also, define EPSILON to a small value that is acceptable for your application requirements

privatestaticfinaldouble EPSILON = 0.000001;

Note: Maybe some one should test and verify if the results are correct. I can't find any easy way to do so..works for the basic cases that I have tried.