Quel est l'algorithme pour trouver le centre d'un cercle à partir de trois points?

Question

J'ai trois points sur la circonférence d'un cercle:

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

Comment calculer le centre du cercle?

Implémentation dans Traitement (Java).

J'ai trouvé la réponse et mis en œuvre une solution de travail:

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

Il peut être plutôt dans le calcul profondeur. Il y a une étape par étape ici: http://paulbourke.net/geometry/circlesphere/. Une fois que vous avez l'équation du cercle, vous pouvez simplement le mettre sous une forme impliquant H et K. Le point (h, k) sera le centre.

(faites défiler un peu de moyens au lien pour obtenir les équations)

Answer 2

Voici mon port de Java, en esquivant la condition d'erreur lorsque le déterminant disparaît avec un IllegalArgumentException très élégant, mon approche pour faire face aux « points sont deux éloignés »ou« les points se trouvent sur une ligne ». En outre, cela calcule le rayon (et fait face à des conditions exceptionnelles) que votre approche intersection-pentes ne fera pas.

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

} 

Voir 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

Je cherchais un algorithme similaire quand je planait sur cette question. A pris votre code mais a trouvé que cela ne fonctionnera pas dans les cas où l'une ou l'autre de la pente est 0 ou infini (peut être vrai lorsque xDelta_a ou xDelta_b est 0). J'ai corrigé l'algorithme et voici mon code.

Note: J'ai utilisé le langage de programmation d'Objective-C et je change juste le code pour l'initialisation de valeur de point, donc si cela est faux, je suis sûr que le programmeur travaillant dans Java peut le corriger. La logique, cependant, est la même pour tous (Dieu bénisse algorithmes !! :))

Fonctionne parfaitement bien en ce qui concerne mes propres tests fonctionnels. S'il vous plaît laissez-moi savoir si la logique est fausse à tout moment.

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