¿Cuál es el algoritmo para encontrar el centro de un círculo a partir de tres puntos?

Question

Tengo tres puntos en la circunferencia de un círculo:

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

¿Cómo calculo el centro del círculo?

Implementándolo en Processing (Java).

he encontrado la respuesta e implementado una solución de trabajo:

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

Puede ser un cálculo más bien en profundidad. Aquí hay un simple paso a paso: http://paulbourke.net/geometry/circlesphere/. Una vez que tenga la ecuación del círculo, simplemente puede ponerlo en una forma que involucre a H y K. El punto (h, k) será el centro.

(desplácese hacia abajo un poco retirado en el enlace para llegar a las ecuaciones)

Answer 2

Aquí está mi puerto de Java, esquivando la condición de error cuando el determinante desaparece con un muy elegante IllegalArgumentException, mi acercamiento a hacer frente a los "puntos son dos condiciones muy separadas "o" puntos mienten en una línea ". Además, esto calcula el radio (y hace frente a condiciones excepcionales) que su enfoque de intersección de pendientes no hará.

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

} 

Ver 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

que estaba buscando un algoritmo similar cuando se movía sobre esta cuestión. Tomó su código pero encontró que esto no funcionará en los casos en que cualquiera de las pendientes es 0 o infinito (puede ser cierto cuando xDelta_a o xDelta_b es 0).

Corregí el algoritmo y aquí está mi código. Nota: utilicé el lenguaje de programación objetivo-c y estoy cambiando el código para la inicialización del valor de punto, así que si eso es incorrecto, estoy seguro de que el programador que trabaja en Java puede corregirlo. La lógica, sin embargo, es la misma para todos (God bless algorithms !! :))

Funciona perfectamente bien en lo que se refiere a mis propias pruebas funcionales. Por favor, hágame saber si la lógica es incorrecta en algún momento.

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