logo标签列表

如何从三个点找到圆的中心算法？

javaalgorithmgeometrycomputational-geometry
37

我在一个圆的周围有三个点：

pt A = (A.x, A.y);
pt B = (B.x, B.y);
pt C = (C.x, C.y);

如何计算圆的中心？

在Processing（Java）中实现。

我找到了答案并实现了一个可行的解决方案：

 pt circleCenter(pt A, pt B, pt C) {

    float yDelta_a = B.y - A.y;
    float xDelta_a = B.x - A.x;
    float yDelta_b = C.y - B.y;
    float xDelta_b = C.x - B.x;
    pt center = P(0,0);

    float aSlope = yDelta_a/xDelta_a;
    float bSlope = yDelta_b/xDelta_b;  
    center.x = (aSlope*bSlope*(A.y - C.y) + bSlope*(A.x + B.x)
        - aSlope*(B.x+C.x) )/(2* (bSlope-aSlope) );
    center.y = -1*(center.x - (A.x+B.x)/2)/aSlope +  (A.y+B.y)/2;

    return center;
  }
http://mathforum.org/library/drmath/view/55233.html - John C Earls
2
非常感谢您发布了对您问题的答案。 - SpoiledTechie.com
3
如果 B.x - A.x 或 C.x - B.x 等于零，你的解决方案会产生奇怪的结果，因为此时你会除以零。请检查代码。 - gexicide
6个回答
22

这是我的Java端口，通过一个非常优雅的IllegalArgumentException来避免行列式消失时出现的错误条件，我的方法应对“点太远”或“点在一条直线上”的情况。此外，这个计算半径（并处理异常情况），而您的相交斜率方法将不会这样做。

public class CircleThree
{ 
  static final double TOL = 0.0000001;
  
  public static Circle circleFromPoints(final Point p1, final Point p2, final Point p3)
  {
    final double offset = Math.pow(p2.x,2) + Math.pow(p2.y,2);
    final double bc =   ( Math.pow(p1.x,2) + Math.pow(p1.y,2) - offset )/2.0;
    final double cd =   (offset - Math.pow(p3.x, 2) - Math.pow(p3.y, 2))/2.0;
    final double det =  (p1.x - p2.x) * (p2.y - p3.y) - (p2.x - p3.x)* (p1.y - p2.y); 
    
    if (Math.abs(det) < TOL) { throw new IllegalArgumentException("Yeah, lazy."); }

    final double idet = 1/det;
     
    final double centerx =  (bc * (p2.y - p3.y) - cd * (p1.y - p2.y)) * idet;
    final double centery =  (cd * (p1.x - p2.x) - bc * (p2.x - p3.x)) * idet;
    final double radius = 
       Math.sqrt( Math.pow(p2.x - centerx,2) + Math.pow(p2.y-centery,2));
    
    return new Circle(new Point(centerx,centery),radius);
  }
  
  static class Circle
  {
    final Point center;
    final double radius;
    public Circle(Point center, double radius)
    {
      this.center = center; this.radius = radius;
    }
    @Override 
    public String toString()
    {
      return new StringBuilder().append("Center= ").append(center).append(", r=").append(radius).toString();
    }
  }
  
  static class Point
  {
    final double x,y;

    public Point(double x, double y)
    {
      this.x = x; this.y = y;
    }
    @Override
    public String toString()
    {
      return "("+x+","+y+")";
    }
    
  }

  public static void main(String[] args)
  {
    Point p1 = new Point(0.0,1.0);
    Point p2 = new Point(1.0,0.0);
    Point p3 = new Point(2.0,1.0);
    Circle c = circleFromPoints(p1, p2, p3);
    System.out.println(c);
  }
  
}

请参考数学论坛的算法：

void circle_vvv(circle *c)
{
    c->center.w = 1.0;
    vertex *v1 = (vertex *)c->c.p1;
    vertex *v2 = (vertex *)c->c.p2;
    vertex *v3 = (vertex *)c->c.p3;
    float bx = v1->xw; float by = v1->yw;
    float cx = v2->xw; float cy = v2->yw;
    float dx = v3->xw; float dy = v3->yw;
    float temp = cx*cx+cy*cy;
    float bc = (bx*bx + by*by - temp)/2.0;
    float cd = (temp - dx*dx - dy*dy)/2.0;
    float det = (bx-cx)*(cy-dy)-(cx-dx)*(by-cy);
    if (fabs(det) < 1.0e-6) {
        c->center.xw = c->center.yw = 1.0;
        c->center.w = 0.0;
        c->v1 = *v1;
        c->v2 = *v2;
        c->v3 = *v3;
        return;
        }
    det = 1/det;
    c->center.xw = (bc*(cy-dy)-cd*(by-cy))*det;
    c->center.yw = ((bx-cx)*cd-(cx-dx)*bc)*det;
    cx = c->center.xw; cy = c->center.yw;
    c->radius = sqrt((cx-bx)*(cx-bx)+(cy-by)*(cy-by));
}
我不太确定哪三个顶点是原始的。v1、v2 和 v3？ - Russell Strauss
是的，这不是很好的代码；我抄袭了它。v1、v2、v3是原始顶点。(bx,by)、(cx,cy)、(dx,dy)是坐标。 - andersoj
@Russell Strauss：我提供了这段代码的Java版本，使得流程更加清晰。 - andersoj
17

这可能需要进行深入的计算。你可以按照这里提供的简单步骤操作。一旦你得到了圆的方程，就可以将其转换为涉及 H 和 K 的形式。点 (h,k) 将是圆心。

(在链接中向下滚动一小段以获取方程)

这是带领我找到答案的页面。我自己实现了它： - Russell Strauss
1
pt circleCenter(pt A, pt B, pt C) { // 计算两个中垂线的斜率 float yDelta_a = B.y - A.y; float xDelta_a = B.x - A.x; float yDelta_b = C.y - B.y; float xDelta_b = C.x - B.x; pt center = P(0,0); float aSlope = yDelta_a/xDelta_a; float bSlope = yDelta_b/xDelta_b; // 求出圆心的坐标 center.x = (aSlopebSlope(A.y - C.y) + bSlope*(A.x + B.x) - aSlope*(B.x+C.x) )/(2* (bSlope-aSlope) ); center.y = -1*(center.x - (A.x+B.x)/2)/aSlope + (A.y+B.y)/2; return center; } - Russell Strauss
7
当我悬停在这个问题上时，我正在寻找一个类似的算法。我使用了你的代码，但是发现当其中一条线段的斜率为0或无穷大（当xDelta_a或xDelta_b为0时可能为真）时，代码会出现问题。
我更正了这个算法，下面是我的代码。 注意：我使用的是Objective-C编程语言，并只更改了点值的初始化代码，因此如果有程序员在Java中工作并且认为这个初始化方法不对，请自行更改。然而，逻辑对所有人来说都是相同的（上帝保佑算法！！：））
在我的功能测试方面，这个算法完全正常。如果任何地方的逻辑有误，请告诉我。
pt circleCenter(pt A, pt B, pt C) {

float yDelta_a = B.y - A.y;
float xDelta_a = B.x - A.x;
float yDelta_b = C.y - B.y;
float xDelta_b = C.x - B.x;
pt center = P(0,0);

float aSlope = yDelta_a/xDelta_a;
float bSlope = yDelta_b/xDelta_b;

pt AB_Mid = P((A.x+B.x)/2, (A.y+B.y)/2);
pt BC_Mid = P((B.x+C.x)/2, (B.y+C.y)/2);

if(yDelta_a == 0)         //aSlope == 0
{
    center.x = AB_Mid.x;
    if (xDelta_b == 0)         //bSlope == INFINITY
    {
        center.y = BC_Mid.y;
    }
    else
    {
        center.y = BC_Mid.y + (BC_Mid.x-center.x)/bSlope;
    }
}
else if (yDelta_b == 0)               //bSlope == 0
{
    center.x = BC_Mid.x;
    if (xDelta_a == 0)             //aSlope == INFINITY
    {
        center.y = AB_Mid.y;
    }
    else
    {
        center.y = AB_Mid.y + (AB_Mid.x-center.x)/aSlope;
    }
}
else if (xDelta_a == 0)        //aSlope == INFINITY
{
    center.y = AB_Mid.y;
    center.x = bSlope*(BC_Mid.y-center.y) + BC_Mid.x;
}
else if (xDelta_b == 0)        //bSlope == INFINITY
{
    center.y = BC_Mid.y;
    center.x = aSlope*(AB_Mid.y-center.y) + AB_Mid.x;
}
else
{
    center.x = (aSlope*bSlope*(AB_Mid.y-BC_Mid.y) - aSlope*BC_Mid.x + bSlope*AB_Mid.x)/(bSlope-aSlope);
    center.y = AB_Mid.y - (center.x - AB_Mid.x)/aSlope;
}

return center;
}
5

很抱歉我的回答晚了。任何使用“斜率”的解决方案都会在两个点形成垂直线时失败，因为斜率将是无限的。

以下是一个简单而健壮的解决方案，适用于2019年以后的所有情况：

"最初的回答"

public static boolean circleCenter(double[] p1, double[] p2, double[] p3, double[] center) {
    double ax = (p1[0] + p2[0]) / 2;
    double ay = (p1[1] + p2[1]) / 2;
    double ux = (p1[1] - p2[1]);
    double uy = (p2[0] - p1[0]);
    double bx = (p2[0] + p3[0]) / 2;
    double by = (p2[1] + p3[1]) / 2;
    double vx = (p2[1] - p3[1]);
    double vy = (p3[0] - p2[0]);
    double dx = ax - bx;
    double dy = ay - by;
    double vu = vx * uy - vy * ux;
    if (vu == 0)
        return false; // Points are collinear, so no unique solution
    double g = (dx * uy - dy * ux) / vu;
    center[0] = bx + g * vx;
    center[1] = by + g * vy;
    return true;
}

上述代码仅在三点共线时返回"false"。最初的回答。
为什么要使用“y”(p1[1]，p2[1])来设置ux，并使用“x”(p1[0]，p2[0])来设置uy？同样的问题也适用于vx和vy。 - trans
圆的中心是线段（p1，p2）和（p2，p3）的垂直平分线相交的地方。线段（p1，p2）的垂直平分线通过（ax，ay），方向为（ux，uy）。线段（p2，p3）的垂直平分线通过（bx，by），方向为（vx，vy）。为了回答问题，交换X和Y并改变一个向量的符号可以得到一个垂直向量。 - Adam Gawne-Cain
1
我明白了。谢谢！顺便说一下，你的解决方案非常有用，为我节省了很多时间。唯一能让这个解决方案更好的是一个图表。 - trans
2
public Vector2 CarculateCircleCenter(Vector2 p1, Vector2 p2, Vector2 p3)
{
    if (
        p2.x - p1.x == 0 ||
        p3.x - p2.x == 0 ||
        p2.y - p1.y == 0 ||
        p3.y - p2.y == 0
    ) return null;

    Vector2 center = new Vector2();
    float ma = (p2.y - p1.y) / (p2.x - p1.x);
    float mb = (p3.y - p2.y) / (p3.x - p2.x);
    center.x = (ma * mb * (p1.y - p3.y) + mb * (p1.x - p2.x) - ma * (p2.x + p3.x)) / (2 * (mb - ma));
    center.y = (-1 / ma) * (center.x - (p1.x + p2.x) * 0.5) + (p1.y + p2.y) * 0.5;
    return center;
}
1
笔误：mb * (p1.x - p2.x) 应该是 mb * (p1.x + p2.x)。 - tim_hutton
1
如果两个点具有相同的X坐标，则此解决方案会出现零除错误。 - Adam Gawne-Cain
是的，你说得对，那是需要考虑的特殊情况。 - Ernesto Alfonso
0
def circle_mid_point(list_b):
list_k = []
for i in range(3):
    for j in range(1,4):
        if i+j <=3:
            midpoint_x1 =  (list_b[i][0] + list_b[i+j][0])/2
            midpoint_y1 = (list_b[i][1] + list_b[i + j][1]) / 2
            list_k.append([midpoint_x1,midpoint_y1]) # list of all the midpoints of the lines

for k in range(len(list_k)):
    for j in range(1,len(list_k)-1):
        if list_k[k] == list_k[k+j]: #at centre only two midpoints will have the same value
            return list_k[k]

k = circle_mid_point([[0,1],[1,0],[-1,0],[0,-1]])
print(k)
使用给定圆周上所有点的中点。只有一对匹配，那就是圆的中点。 - Nitin Jindal
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接