三角形外心计算

问题引入

给定二维平面上三个不共线的点 , 求出他们形成的圆的圆心和半径。

问题分析

计算几何问题常用数形结合解决，不妨设圆心，则满足三个点到圆心的距离相同。我们可以用两个等价方程来描述：

$(x-x_0)^2+(y-y_0)^2=(x-x_1)^2+(y-y_1)^2\\\\(x-x_0)^2+(y-y_0)^2=(x-x_2)^2+(y-y_2)^2\tag1$

现在转换为两个方程解两个未知数的问题。上式化简后可得两个线性方程，使用克拉默法则可以容易解出答案。

公式推导

对公式分别移项展开消去二次项，得到：

$2(x_1-x_0)x+2(y_1-y_0)y=x_1^2-x_0^2+y_1^2-y_0^2\\\\2(x_2-x_0)x+2(y_2-y_0)y=x_2^2-x_0^2+y_2^2-y_0^2\tag2$

如此得到一组二元一次线性方程则，方程有解充要条件是系数矩阵行满秩，容易发现无解当且仅当三点共线，即行列式(同时也是三点形成两个向量的叉积)为0，即

$(x_1-x_0)\times(y_2-y_0)-(x_2-x_0)\times(y_1-y_0)=0\tag3$

其他情况下均有解。方便起见以a,b,c,d,e,f,g来代替原系数，即：

$ax+by=c\\\\dx+ey=f\tag4$

其中：

$a=2(x_1-x_0)\\\\b=2(y_1-y_0)\\\\c=x_1^2-x_0^2+y_1^2-y_0^2\\\\d=2(x_2-x_0)\\\\e=2(y_2-y_0)\\\\f=x_2^2-x_0^2+y_2^2-y_0^2\tag5$

在有解情况下，由克拉默法则可得

$x = \frac{D_x}{D} = \frac{ce-fb}{ae-db}$ $y = \frac{D_y}{D} = \frac{af-dc}{ae-bd}\tag6$

于是可在内求出圆心，从而计算可得半径。

代码实现

node findO(const node &p,const node &q,const node &r){
    //input should be nonlinear
    double a = 2 * (p.x - q.x);
    double b = 2 * (p.y - q.y);
    double c = p.x * p.x + p.y * p.y - q.x * q.x - q.y * q.y;
    double d = 2 * (p.x - r.x);
    double e = 2 * (p.y - r.y);
    double f = p.x * p.x + p.y * p.y - r.x * r.x - r.y * r.y;
    double g = a*e-b*d;
    return {(c*e-f*b)/g,(a*f-d*c)/g};
}

例题

Geometry Problem
其实本题并不是求圆心模板题，但是考虑到本题去掉思维部分可以被视为2-D版本三点共圆模板题，而且模板题确实难找，故当作模板题放在此处。

高维情况

三维三角形外心

给定三维空间上三个不共线的点 , , , 求出他们形成的圆的圆心和半径。

依据数形结合思路，仍要先把几何问题转化为代数问题：

$R = (x-x_0)^2+(y-y_0)^2+(z-z_0)^2\\\\\ \ \ \ = (x-x_1)^2+(y-y_1)^2+(z-z_1)^2\\\\\ \ \ = (x-x_2)^2+(y-y_2)^2+(z-z_2)^2$

其中为圆心坐标，于是得到三个未知数两个方程。要求解至少还需要一个方程。但是三个点可以确定一张平面，可以通过叉积得到法向量，构造平面方程，如此则转化为三元一次线性方程组，且方程系数比较容易求出。容易利用克拉默法则求三阶行列式分别求出的数值。

n维度三角形外心

给定n维空间上三个不共线的点 , , , 求出他们形成的圆的圆心和半径。

类推处理二维和三维情况下的方案，设圆心为。由等距性质得到两个线性方程。在n维空间下，表征一个二维平面平面，需要n-2个线性方程。于是综合上述两组方程得到n元一次线性方程组，高斯消元可以处理得到方程的解。