Thuật toán để tìm trung tâm của một vòng tròn từ ba điểm là gì?

Question

Tôi có ba điểm trên chu vi của một vòng tròn:

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

Làm cách nào để tính trung tâm của vòng kết nối?

Triển khai trong Xử lý (Java).

Tôi tìm thấy câu trả lời và thực hiện một giải pháp làm việc:

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

Answer 1

Nó có thể là một thay sâu tính toán. Có một bước theo bước đơn giản tại đây: http://paulbourke.net/geometry/circlesphere/. Một khi bạn có phương trình của vòng tròn, bạn có thể chỉ cần đặt nó trong một hình thức liên quan đến H và K. Điểm (h, k) sẽ là trung tâm.

(di chuyển xuống một cách ít tại liên kết để có được các phương trình)

Answer 2

Dưới đây là cổng Java của tôi, luồn lách qua những tình trạng lỗi khi yếu tố quyết định sẽ biến mất với rất thanh lịch IllegalArgumentException, cách tiếp cận của tôi để đối phó với những "điểm hai điều kiện cách xa nhau "hoặc" nằm trên một đường ". Ngoài ra, điều này tính toán bán kính (và đối phó với các điều kiện đặc biệt) mà cách tiếp cận giao nhau-sườn của bạn sẽ không làm.

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

} 

Xem algorithm from here:

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

Answer 3

tôi đang tìm kiếm một thuật toán tương tự như khi tôi quét qua câu hỏi này. Lấy mã của bạn nhưng thấy rằng điều này sẽ không hoạt động trong trường hợp khi độ dốc là 0 hoặc vô cùng (có thể đúng khi xDelta_a hoặc xDelta_b là 0).

Tôi đã sửa thuật toán và đây là mã của tôi. Lưu ý: Tôi đã sử dụng ngôn ngữ lập trình mục tiêu-c và chỉ thay đổi mã để khởi tạo giá trị điểm, vì vậy nếu điều đó sai, tôi chắc chắn rằng lập trình viên làm việc trong java có thể sửa nó. Logic, tuy nhiên, là như nhau cho tất cả (Thiên Chúa chúc lành cho các thuật toán !! :))

Hoạt động hoàn toàn tốt như xa như thử nghiệm chức năng của riêng tôi là có liên quan. Vui lòng cho tôi biết nếu logic sai tại bất kỳ thời điểm nào.

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

Answer 4

public Vector2 CarculateCircleCenter(Vector2 p1, Vector2 p2, Vector2 p3) 
{ 
    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; 
}