Was ist der Algorithmus zum Finden des Mittelpunkts eines Kreises von drei Punkten?

Question

Ich habe drei Punkte auf dem Umfang eines Kreises:

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

Wie berechne ich das Zentrum des Kreises?

Implementierung in der Verarbeitung (Java).

fand ich die Antwort und implementiert, um eine Arbeitslösung:

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

Es kann eine eher in Tiefenberechnung sein. Hier gibt es eine einfache Schritt-für-Schritt-Anleitung: http://paulbourke.net/geometry/circlesphere/. Sobald Sie die Gleichung des Kreises haben, können Sie es einfach in eine Form bringen, die H und K einschließt. Der Punkt (h, k) wird das Zentrum sein.

(scrollen ein kleines Stück auf dem Link unten, um die Gleichungen zu erhalten)

Answer 2

Hier ist mein Java-Port, um den Fehlerzustand ausweichen, wenn die Determinante mit einer sehr eleganten IllegalArgumentException verschwindet, mein Ansatz mit den „Punkten zu bewältigen sind zwei weit auseinander liegende "oder" Punkte auf einer Linie "liegen. Außerdem berechnet dies den Radius (und kommt mit außergewöhnlichen Bedingungen zurecht), was mit der Methode der Überschneidung und Steigung nicht möglich ist.

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

} 

Siehe 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

ich nach einem ähnlichen Algorithmus suchen, wenn ich über diese Frage schwebte. Hat Ihren Code genommen, aber festgestellt, dass dies nicht in Fällen funktioniert, in denen eine der Steigungen 0 oder unendlich ist (dies kann der Fall sein, wenn xDelta_a oder xDelta_b 0 ist).

Ich habe den Algorithmus korrigiert und hier ist mein Code. Hinweis: Ich habe objective-c-Programmiersprache verwendet und ändere nur den Code für die Initialisierung des Punktwerts. Wenn das also falsch ist, bin ich mir sicher, dass Programmierer, die in Java arbeiten, den Fehler korrigieren können. Die Logik ist jedoch für alle gleich (Gott segne Algorithmen !! :))

Funktioniert einwandfrei, soweit meine eigenen Funktionstests betrifft. Bitte lassen Sie mich wissen, wenn Logik an irgendeinem Punkt falsch ist.

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