通过编程找到三个圆的交点

Question

如标题所述，我有三个圆。

每个圆的半径不同。我知道每个圆的半径。

我也知道每个圆的中心点。

现在我需要知道如何通过编程计算三个圆的相交点，是否有任何公式或其他东西？

它可能看起来像下面的图像：

- Alex Chengalan

---

这根本不是编程问题，只需在StackOverflow或Google上搜索即可获得许多好的结果。 - LionC

@Alex Chengalan 如果可能的话，尝试添加图片，这样更有助于理解。 - TheFlash

我已经找到了正确的解决方案...请查看http://sg.answers.yahoo.com/question/index?qid=20110127015240AA9RjyZ，但现在问题是如何在JAVA中实现。@Alex Chengalan - TheFlash

此问题似乎不适合本站，因为它与编程无关。 - Richard Tingle

@RichardTingle：信不信由你，编程不仅仅是敲代码。它涉及解决问题和偶尔需要实现的数学。这个问题显然是一个编程问题，要实现一个困难的数学问题，对于那些具有数学技能并在这个领域工作的人来说，这非常受欢迎。 - stackoverflowuser2010

Answer 1

您可以使用这个C代码来获取帮助。将其移植到Java上不应该是难事。解释在这里。搜索/滚动到：两个圆的交点 使用此方法，找到任意两个圆的交点，假设为(x,y)。现在第三个圆只有在它的center和点x,y之间的距离等于r时才会在点x,y处相交。

1. 如果distance(center,point) == r，那么x,y就是交点。

2. 如果distance(center,point) != r，则不存在这样的点。

代码（从这里移植；所有信用归原作者所有）：

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;
}

按照以下方式调用此方法：

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)

此外，定义EPSILON为一个适合您应用要求的小值。

private static final double EPSILON = 0.000001;

注意：也许有人应该测试并验证结果是否正确。我找不到任何简单的方法来做到这一点...但对于我尝试过的基本情况而言，它是有效的。

- Amulya Khare

---

谢谢你的努力，兄弟！我会检查并在这里发表评论。 - Alex Chengalan

运行完美！谢谢！ - Vinay W

我已经将上述内容翻译成了Python代码，但是使用您提供的数字后我得到了以下输出：$ INFO:log:INTERSECTION Circle1 AND Circle2: (0.0,0.0) AND (0.0,0.0) $ INFO:log:INTERSECTION Circle1 AND Circle2 AND Circle3: (0.0,0.0)。根据您的函数输入，我应该期望什么输出？ - AlienWebguy

Answer 2

您可以使用以下条件：

(x - x0) ^ 2 + (y - y0) ^ 2 <= R ^ 2

其中，x和y是你的点的坐标，x0和y0是圆心的坐标，R是圆的半径，^2表示平方。如果满足条件，则该点在圆内（或在左右两侧相等的情况下在圆周上）。如果不满足条件，则该点在圆外。

/ / Point, which hit the circle is necessary to determine
PointF p = ...;

/ / Center of the circle
PointF center = new PointF (10, 10);

/ / The radius of the circle
float r = 5F;

/ / "Normalize" the situation relative to the center point of the circle
float dx = p.x - center.x;
float dy = p.y - center.y;

/ / Compare the distance from the point to the center of a circle to its radius
boolean result =  ((r * r) <= (dx * dx + dy * dy))) ? true : false;

- user2558337