What could a function look like that receives three locations and three radius and outputs one coordinate showing the overlapping?

Question

I have three gps locations as double lat and lng. I have three radius that correspond to each of the lat and lng values. The radius form circles around the locations. I want to determine the one point where all three circles overlap.

My starting point:

(x−lat_1)^2+(y−lng_1)^2=r_1^2
(x−lat_2)^2+(y−lng_2)^2=r_2^2
(x−lat_3)^2+(y−lng_3)^2=r_3^2

But here I am stuck - not only is that system of equations over-determined, it is also unclear, how to mix up degrees, minutes and seconds with a radius in meters.

What could a function(pseudocode is enough) look like that receives three locations and three radius and outputs one coordinate showing the overlapping.

Speaking of which, there needs to be some tolerance, as neither the radius nor the locations are too precise.

Did you at least find this SO post: http://stackoverflow.com/questions/19723641/find-intersecting-point-of-three-circles-programmatically — Morrison Chang, Jun 21 '16 at 06:20

score 0 · Accepted Answer · edited May 23 '17 at 10:34

Take a look at this question: Find intersecting point of three circles programmatically

I'm posting here the code that does what you need:

private static final double EPSILON = 0.000001;

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. */
        return false;
    }
    if (d < Math.abs(r0 - r1))
    {
        /* no solution. one circle is contained in the other */
        return false;
    }

    /* '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 + ")");
    }
    else if(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");
    }
    return true;
}

Usage:

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)

As you said, you probably need to do some unit conversion here. There is some complicated formula that calculates distance between two geolocations, so you need to reverse it to get meters from radian based distance.

Here you may find implementations of this calculation and try to reverse it:

Calculate distance between two latitude-longitude points? (Haversine formula)

What could a function look like that receives three locations and three radius and outputs one coordinate showing the overlapping?

1 Answers1