一些简单的几何关系

已知两点求直线方程

有不同两点 $P_0(x_0, y_0)$ 和 $P_1(x_1, y_1)$ ，通过求解以下方程
$\frac{y - y_0}{x - x_0} = \frac{y - y_1}{x - x_1}$

可以得到
$y = \frac{(x - x_0)y_1 + (x1 - x)y_0}{x_1 - x_0}$
如果在极坐标系下，两点为 $P_0(\alpha_0, d_0)$ 和 $P_1(\alpha_1, d_1)$ ，则直线方程为
$\frac{d\sin\alpha - d_0\sin\alpha_0}{d\cos\alpha - d_0\cos\alpha_0} = \frac{d\sin\alpha - d_1\sin\alpha_1}{d\cos\alpha - d_1\cos\alpha_1}$

可以得到
$d = \frac{d_0d_1\sin(\alpha_1 - \alpha_0)}{d_0\sin(\alpha - \alpha_0) + d_1\sin(\alpha_1 - \alpha)}$

过两点的半径为 $r$ 的圆

有点 $P_0(x_0, y_0)$ 和 $P_1(x_1, y_1)$ ，现需要求解圆心位置 $O(a, b)$ ，使得半径为 $r$ 的圆通过两点
可以简单列出方程为
$\begin{aligned} (a - x_0)^2 + (b - y_0)^2 =& r^2 \\ (a - x_1)^2 + (b - y_1)^2 =& r^2 \end{aligned}$
求解得到
$\begin{aligned} a &= \frac{x_0 + x_1}{2} \pm \frac{|y_0 - y_1|}{2} \sqrt{\frac{4r^2}{(x_0 - x_1)^2 + (y_0 - y_1)^2} - 1} \\ b &= \frac{y_0 + y_1}{2} \mp \frac{x_0 - x_1}{2} \frac{|y_0 - y_1|}{y_0 - y_1} \sqrt{\frac{4r^2}{(x_0 - x_1)^2 + (y_0 - y_1)^2} - 1} \\ \end{aligned}$

点到直线的距离

目前有点 $P_0(x_0, y_0)$ 和 $P_1(x_1, y_1)$ ，两者组成线段，现有点 $O(a, b)$ ，求解点 $O$ 到直线的距离
首先求解点 $P_0$ 和点 $P_1$ 组成的直线方程为
$(y_0 - y_1)x + (x_1 - x_0)y + x_0y_1 - x_1y_0 = 0$
点 $O$ 到直线的距离为
$\begin{aligned} d &= \frac{|(y_0 - y_1)a + (x_1 - x_0)b + x_0y_1 - x_1y_0|}{\sqrt{(x_1 - x_0)^2 + (y_0 - y_1)^2}} \\ &= \frac{|(x_1 - x_0)(b - y_0) - (y_1 - y_0)(a - x_0)|}{\sqrt{(x_1 - x_0)^2 + (y_0 - y_1)^2}} \end{aligned}$

到直线距离为d的点

目前有点 $P_0(x_0, y_0)$ 和 $P_1(x_1, y_1)$ ，两者组成线段，求解到直线距离为 $d$ 的点 $O(a, b)$ ，使得 $OP_0 \bot P_0P_1$
$\begin{aligned} (a - x_0)(x_1 - x_0) + (b - y_0)(y_1 - y_0) =& 0 \\ (a - x_0)^2 + (b - y_0)^2 =& d^2 \end{aligned}$
可以求解得到
$\begin{aligned} a &= x_0 \pm\frac{(y_1 - y_0)}{\sqrt{(x_1 - x_0)^2 + (y_1 - y_0)^2}}d \\ b &= y_0 \mp\frac{(x_1 - x_0)}{\sqrt{(x_1 - x_0)^2 + (y_1 - y_0)^2}}d \end{aligned}$
根据点 $O$ 和点 $P_0$ 到原点的距离可以选择一个合适的点

直线段上的垂直点

目前有点 $P_0(x_0, y_0, z_0)$ 和 $P_1(x_1, y_1, z_1)$ ，两者组成线段，现有点 $O(a, b, c)$ ，求解垂直点 $Q(x, y, z)$ 位置，并且判断是否在线段 $P_0P_1$ 上
考虑到垂直点 $Q$ 和 $P_0P_1$ 共线，因此可以表达成
$\begin{aligned} x &= kx_0 + (1 - k)x_1 = x_1 - k(x_1 - x_0) \\ y &= ky_0 + (1 - k)y_1 = y_1 - k(y_1 - y_0) \\ z &= kz_0 + (1 - k)z_1 = z_1 - k(z_1 - z_0) \end{aligned}$

当 $k \in [0, 1]$ ，点 $Q$ 在线段 $P_0P_1$ 上，否则在线段外
现在找到点 $Q$ 使得 $OQ \bot P_0P_1$ ，即
$(x - a)(x_1 - x_0) + (y - b)(y_1 - y_0) + (z - c)(z_1 - z_0) = 0$

展开后可以得到
$k = \frac{(x_1 - x_0)(x_1 - a) + (y_1 - y_0)(y_1 - b) + (z_1 - z_0)(z_1 - c) }{(x_1 - x_0)^2 + (y_1 - y_0)^2 + (z_1 - z_0)^2}$

如果寻求原点 $(0, 0, 0)$ 到线段的垂直点，那么公式将会变成
$k = \frac{(x_1 - x_0)x_1 + (y_1 - y_0)y_1 + (z_1 - z_0)z_1 }{(x_1 - x_0)^2 + (y_1 - y_0)^2 + (z_1 - z_0)^2}$

平面上的垂直点

假设平面上四边形由四个点 $P_0(x_0, y_0, z_0)$ 、 $P_1(x_1, y_1, z_1)$ 、 $P_2(x_2, y_2, z_2)$ 、 $P_3(x_3, y_3, z_3)$ （四个点按照顺时针或者逆时针）组成，现有点 $O(a, b, c)$ ，求解垂直点 $Q(x, y, z)$ 位置，并且判断是否在矩形内
考虑到垂直点 $Q$ 和 $P_0P_1P_2P_3$ 共面，因此可以表达成
$\begin{aligned} x &= k_2[x_1 + k_1(x_0 - x_1)] + (1 - k_2)[x_2 + k_1(x_3 - x_2)] \\ y &= k_2[y_1 + k_1(y_0 - y_1)] + (1 - k_2)[y_2 + k_1(y_3 - y_2)] \\ z &= k_2[z_1 + k_1(z_0 - z_1)] + (1 - k_2)[z_2 + k_1(z_3 - z_2)] \end{aligned}$

如果限制四边形为矩形那么有
$\begin{aligned} x &= k_2[x_1 + k_1(x_0 - x_1)] + (1 - k_2)[x_2 + k_1(x_0 - x_1)]\\ &= x_2 - k_1(x_1 - x_0) + k_2(x_1 - x_2) \\ y &= k_2[y_1 + k_1(y_0 - y_1)] + (1 - k_2)[y_2 + k_1(y_0 - y_1)]\\ &= y_2 - k_1(y_1 - y_0) + k_2(y_1 - y_2) \\ z &= k_2[z_1 + k_1(z_0 - z_1)] + (1 - k_2)[z_2 + k_1(z_0 - z_1)]\\ &= z_2 - k_1(z_1 - z_0) + k_2(z_1 - z_2) \end{aligned}$

当 $k_1,k_2 \in [0, 1]$ ，点 $Q$ 在四边形 $P_0P_1P_2P_3$ 上，否则在四边形外
现在找到点 $Q$ 使得 $OQ \bot P_0P_1, OQ \bot P_1P_2$ ，即
$\begin{aligned} (x - a)(x_1 - x_0) + (y - b)(y_1 - y_0) + (z - c)(z_1 - z_0) = 0 \\ (x - a)(x_1 - x_2) + (y - b)(y_1 - y_2) + (z - c)(z_1 - z_2) = 0 \end{aligned}$

展开后可以得到
$\begin{aligned} k_1 &= \frac{A_2C_1 - A_1C_2}{C_1B_2 - C_2B_1} \\ k_2 &= \frac{A_2B_1 - A_1B_2}{C_1B_2 - C_2B_1} \end{aligned}$

其中
$\begin{aligned} A_1 &= (x_2 - a)(x_1 - x_0) + (y_2 - b)(y_1 - y_0) + (z_2 - c)(z_1 - z_0) \\ A_2 &= (x_2 - a)(x_1 - x_2) + (y_2 - b)(y_1 - y_2) + (z_2 - c)(z_1 - z_2) \\ B_1 &= (x_1 - x_0)^2 + (y_1 - y_0)^2 + (z_1 - z_0)^2 \\ B_2 &= (x_1 - x_0)(x_1 - x_2) + (y_1 - y_0)(y_1 - y_2) + (z_1 - z_0)(z_1 - z_2) \\ C_1 &= B_2 \\ C_2 &= (x_1 - x_2)^2 + (y_1 - y_2)^2 + (z_1 - z_2)^2 \end{aligned}$

二维散点直线拟合

目前有一系列 $2$ 维散点 $(x_i,y_i), i = 1, \cdots, n$ ，想用直线 $ax + by + c = 0$ 去拟合这一系列点，取点到直线的距离和最短作为约束，如下所示
$\begin{aligned} \min \sum_{i=1}^n \frac{(ax_i + by_i + c)^2}{a^2 + b^2} \end{aligned}$

如果约束 $a^2 + b^2 = 1$ ，则方程变为
$\begin{aligned} \min \quad&\sum_{i=1}^n (ax_i + by_i + c)^2 \\ \text{subject to} \quad& a^2 + b^2 = 1 \end{aligned}$

根据拉格朗日乘子法，相当于求解下式
$\begin{aligned} \min \quad&\sum_{i=1}^n (ax_i + by_i + c)^2 + \lambda(1 - a^2 - b^2) \end{aligned}$

分别对 $a,b,c$ 求解偏导可以得到
$\begin{aligned} a\sum_{i= 1}^nx_i^2 + b\sum_{i=1}^n x_iy_i + c \sum_{i=1}^n x_i &= \lambda a \\ a\sum_{i= 1}^nx_iy_i + b\sum_{i=1}^n y_i^2 + c \sum_{i=1}^n y_i &= \lambda b \\ a\sum_{i= 1}^nx_i + b\sum_{i=1}^n y_i + nc &= 0 \end{aligned}$

求解可以得到
$\begin{aligned} c &= -a\frac{1}{n}\sum_{i=1}^nx_i - b\frac{1}{n}\sum_{i=1}^n y_i \\ \lambda a &= a \bigg[\sum_{i = 1}^n x_i^2 - \frac{1}{n} \big(\sum_{i = 1}^n x_i \big)^2 \bigg] + b \bigg[\sum_{i = 1}^n x_iy_i - \frac{1}{n}\sum_{i = 1}^n x_i \sum_{i = 1}^n y_i \bigg] \\ \lambda b &= a \bigg[\sum_{i = 1}^n x_iy_i - \frac{1}{n}\sum_{i = 1}^n x_i \sum_{i = 1}^n y_i \bigg] + b \bigg[\sum_{i = 1}^n y_i^2 - \frac{1}{n} \big(\sum_{i = 1}^n y_i \big)^2 \bigg] \end{aligned}$

令 $x_i' = x_i - \frac{1}{n} \sum_{i = 1}^n x_i,y_i' = y_i - \frac{1}{n} \sum_{i = 1}^n y_i$ ，上式等价于
$\begin{aligned} \begin{bmatrix} \sum_{i = 1}^n x_i'^2 & \sum_{i = 1}^n x_i'y_i' \\ \sum_{i = 1}^n x_i'y_i' & \sum_{i = 1}^n y_i'^2 \end{bmatrix} \begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} u & w \\ w & v \end{bmatrix} \begin{bmatrix} a \\ b \end{bmatrix} = \lambda \begin{bmatrix} a \\ b \end{bmatrix} \end{aligned}$

求解可以得到 $\lambda = \frac{u + v \pm \sqrt{(u - v)^2 + 4w^2}}{2}$ ，取较小那个为结果得到
$\begin{aligned} a^2 + b^2 =& 1 \\ \frac{a}{b} =& \frac{-2w}{u - v+ \sqrt{(u - v)^2 + 4w^2}} \end{aligned}$

k维散点直线拟合

有一系列 $k$ 维散点 $\boldsymbol x_i=[x_{i0}, x_{i1},\cdots,x_{ik-1}]^T, i = 1, \cdots, n$ ，希望用直线去拟合，高维空间中的直线拟合无法用类似 $a_0x_0 + a_1x_1 + \cdots +a_{k-1}x_{k-1} = 0$ 来表达，因为该方程为面方程，高维空间中的线，则需要多个平面求交来得到，求解较为复杂。一个可行的方式是将直线用“点 + 向量”方式来表达，即 $\boldsymbol x=\boldsymbol a + \eta \boldsymbol d$ ，约束条件依然为各个点到直线的距离最小
$\begin{aligned} \min \quad &\sum_{i=1}^n \|(\boldsymbol x - \boldsymbol a) - [\boldsymbol d^T(\boldsymbol x - \boldsymbol a)]\boldsymbol d\|^2\\ \text{subject to} \quad &\boldsymbol d^T\boldsymbol d = 1 \end{aligned}$

利用拉格朗日乘子法，上式变为
$\min \quad \sum_{i=1}^n \|(\boldsymbol x - \boldsymbol a) - [\boldsymbol d^T(\boldsymbol x - \boldsymbol a)]\boldsymbol d\|^2 +\lambda(\boldsymbol d^T\boldsymbol d - 1)$

再次变形得到
$\begin{aligned} &\min \quad \sum_{i=1}^n \|(\boldsymbol x - \boldsymbol a)-\boldsymbol d[\boldsymbol d^T(\boldsymbol x - \boldsymbol a)]\|^2 +\lambda(\boldsymbol d^T\boldsymbol d - 1) \\ \Rightarrow &\min \quad \sum_{i=1}^n \|(\boldsymbol I - \boldsymbol d\boldsymbol d^T)(\boldsymbol x - \boldsymbol a)\|^2 +\lambda(\boldsymbol d^T\boldsymbol d - 1) \\ \Rightarrow &\min \quad \sum_{i=1}^n (\boldsymbol x - \boldsymbol a)^T(\boldsymbol I - \boldsymbol d\boldsymbol d^T)(\boldsymbol x - \boldsymbol a) +\lambda(\boldsymbol d^T\boldsymbol d - 1) \end{aligned}$

对 $\boldsymbol a$ 求导可以得到
$\sum_{i=1}^n(\boldsymbol I - \boldsymbol d\boldsymbol d^T)(\boldsymbol x - \boldsymbol a)=0$

考虑到 $\boldsymbol I \ne \boldsymbol d \boldsymbol d^T$ ，因此有
$\boldsymbol a = \frac{1}{n} \sum_{i=1}^n \boldsymbol x$

对 $\boldsymbol d$ 求导，可以得到
$\begin{aligned} -\sum_{i=1}^n (\boldsymbol x - \boldsymbol a)(\boldsymbol x - \boldsymbol a)^T \boldsymbol d+\lambda\boldsymbol d \end{aligned}=0$

可以得到 $\boldsymbol d$ 为矩阵 $\sum_{i=1}^n (\boldsymbol x - \boldsymbol a)(\boldsymbol x - \boldsymbol a)^T$ 最大特征值对应的特征向量，该结果和二维的结果可以保持一致
注：二维结果中 $[a,b]^T$ 不是直线的方向向量，而是直线的垂直向量，因此前一节中最小特征值对应的特征向量和这里物理意义一致

k维平面拟合

有一系列 k 维散点 $\boldsymbol{x}_i = [x_{i0}, x_{i1}, \cdots, x_{ik-1}]^T, i = 1, \cdots, n$ ，希望用平面 $\boldsymbol{a}^T\boldsymbol{x} + b = 0$ 去拟合，其中 $\boldsymbol{a} = [a_0, a_1, \cdots, a_{k-1}]^T$ 为平面的法向量，拟合要求所有点到平面的距离平方和最小，即
$\min \sum_{i = 1}^n\frac{\|\boldsymbol{a}^T\boldsymbol{x}_i + b\|^2}{\|\boldsymbol{a}\|^2}$

如果约束法向量 $\boldsymbol{a}^T \boldsymbol{a} = 1$ ，为单位向量，则有
$\begin{aligned} \min \quad &\sum_{i = 1}^n \|\boldsymbol{a}^T\boldsymbol{x}_i + b\|^2 \\ \text{subject to} \quad &\boldsymbol{a}^T \boldsymbol{a} = 1 \end{aligned}$

利用拉格朗日乘子法，上式变为
$\min \sum_{i = 1}^n \|\boldsymbol{a}^T\boldsymbol{x}_i + b\|^2 + \lambda(\boldsymbol{a}^T \boldsymbol{a} - 1)$

上式可以继续变形得到
$\min \boldsymbol{a}^T \bigg(\sum_{i=1}^n \boldsymbol{x}_i \boldsymbol{x}_i^T \bigg) \boldsymbol{a} + 2b \boldsymbol{a}^T \sum_{i=1}^n \boldsymbol{x}_i + nb^2 + \lambda(\boldsymbol{a}^T \boldsymbol{a} - 1)$

上式对 $b$ 求导可以得到
$b = - \boldsymbol{a}^T \frac{1}{n} \sum_{i = 1}^n \boldsymbol{x}_i$

带入后可以得到
$\min \boldsymbol{a}^T \bigg(\sum_{i=1}^n \boldsymbol{x}_i \boldsymbol{x}_i^T - \frac{1}{n} \sum_{i=1}^n \boldsymbol{x}_i \sum_{i=1}^n \boldsymbol{x}_i^T \bigg) \boldsymbol{a} + \lambda(\boldsymbol{a}^T \boldsymbol{a} - 1)$

再对 $\boldsymbol{a}$ 求导可以得到
$\bigg(\sum_{i=1}^n \boldsymbol{x}_i \boldsymbol{x}_i^T - \frac{1}{n} \sum_{i=1}^n \boldsymbol{x}_i \sum_{i=1}^n \boldsymbol{x}_i^T \bigg) \boldsymbol{a} = -\lambda \boldsymbol{a}$

为了保证原式最小， $-\lambda$ 为矩阵 $\sum_{i=1}^n \boldsymbol{x}_i \boldsymbol{x}_i^T - \frac{1}{n} \sum_{i=1}^n \boldsymbol{x}_i \sum_{i=1}^n \boldsymbol{x}_i^T$ 的最小特征值，归一化法向量 $\boldsymbol{a}$ 为对应的特征向量