周报

求任意维度三角形外心

2020年3月24日

问题引入

给定二维平面上三个不共线的点 $A(x_0,y_0),B(x_1,y_1),C(x_2,y_2)$, 求出他们形成的圆的圆心和半径。

问题分析

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

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

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

公式推导

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

$$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$$

于是可在 $O(1)$ 内求出圆心，从而计算可得半径。

代码实现

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版本三点共圆模板题，而且模板题确实难找，故当作模板题放在此处。

高维情况

三维三角形外心

给定三维空间上三个不共线的点$A(x_0,y_0,z_0)$ , $B(x_1,y_1,z_1)$ , $C(x_2,y_2,z_2)$ , 求出他们形成的圆的圆心和半径。

依据数形结合思路，仍要先把几何问题转化为代数问题：
$$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\tag7$$

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

n维度三角形外心

给定n维空间上三个不共线的点$A(x_0,y_0,z_0,…)$ , $B(x_1,y_1,z_1,…)$ , $C(x_2,y_2,z_2,…)$ , 求出他们形成的圆的圆心和半径。

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

Views: 45

发表评论