一些簡單的幾何關(guān)系

已知兩點求直線方程

有不同兩點 $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}$
如果在極坐標(biāo)系下，兩點為 $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)$ ，現(xiàn)需要求解圓心位置 $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)$ 捧弃，兩者組成線段，現(xiàn)有點 $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}$
根據(jù)點 $O$ 和點 $P_0$ 到原點的距離可以選擇一個合適的點

直線段上的垂直點

目前有點 $P_0(x_0, y_0, z_0)$ 和 $P_1(x_1, y_1, z_1)$ 买鸽，兩者組成線段涧郊，現(xiàn)有點 $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}$

當(dāng) $k \in [0, 1]$ ，點 $Q$ 在線段 $P_0P_1$ 上弹砚，否則在線段外
現(xiàn)在找到點 $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}$

平面上的垂直點

假設(shè)平面上四邊形由四個點 $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)$ （四個點按照順時針或者逆時針）組成茅诱，現(xiàn)有點 $O(a, b, c)$ 逗物，求解垂直點 $Q(x, y, z)$ 位置，并且判斷是否在矩形內(nèi)
考慮到垂直點 $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}$

當(dāng) $k_1,k_2 \in [0, 1]$ 翎卓，點 $Q$ 在四邊形 $P_0P_1P_2P_3$ 上，否則在四邊形外
現(xiàn)在找到點 $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$ 逗扒，則方程變?yōu)?br> $\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}$

根據(jù)拉格朗日乘子法，相當(dāng)于求解下式
$\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$ 求解偏導(dǎo)可以得到
$\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}$ 矩肩，取較小那個為結(jié)果得到
$\begin{aligned} a^2 + b^2 =& 1 \\ \frac{a} =& \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$ 來表達，因為該方程為面方程始锚，高維空間中的線建炫，則需要多個平面求交來得到，求解較為復(fù)雜疼蛾。一個可行的方式是將直線用“點 + 向量”方式來表達肛跌，即 $\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}$

利用拉格朗日乘子法，上式變?yōu)?br> $\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$ 求導(dǎo)可以得到
$\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$ 求導(dǎo)转唉，可以得到
$\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$ 最大特征值對應(yīng)的特征向量，該結(jié)果和二維的結(jié)果可以保持一致
注：二維結(jié)果中 $[a,b]^T$ 不是直線的方向向量稳捆，而是直線的垂直向量赠法，因此前一節(jié)中最小特征值對應(yīng)的特征向量和這里物理意義一致

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

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

上式可以繼續(xù)變形得到
$\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$ 求導(dǎo)可以得到
$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}$ 求導(dǎo)可以得到
$\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}$ 為對應(yīng)的特征向量

最后編輯于：2023.07.07 18:17:04

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市块请，隨后出現(xiàn)的幾起案子娜氏，更是在濱河造成了極大的恐慌，老刑警劉巖墩新，帶你破解...
沈念sama閱讀 216,402評論 6贊 499
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件贸弥，死亡現(xiàn)場離奇詭異，居然都是意外死亡海渊，警方通過查閱死者的電腦和手機茂腥，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,377評論 3贊 392
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來切省，“玉大人，你說我怎么就攤上這事帕胆〕Γ” “怎么了？”我有些...
開封第一講書人閱讀 162,483評論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵懒豹，是天一觀的道長芙盘。經(jīng)常有香客問我，道長脸秽，這世上最難降的妖魔是什么儒老？我笑而不...
開封第一講書人閱讀 58,165評論 1贊 292
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮记餐，結(jié)果婚禮上驮樊，老公的妹妹穿的比我還像新娘。我一直安慰自己，他們只是感情好囚衔，可當(dāng)我...
茶點故事閱讀 67,176評論 6贊 388
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布挖腰。她就那樣靜靜地躺著，像睡著了一般练湿。火紅的嫁衣襯著肌膚如雪猴仑。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,146評論 1贊 297
城市分裂傳說
那天肥哎，我揣著相機與錄音辽俗，去河邊找鬼。笑死篡诽，一個胖子當(dāng)著我的面吹牛崖飘，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播霞捡，決...
沈念sama閱讀 40,032評論 3贊 417
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼坐漏，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了碧信？” 一聲冷哼從身側(cè)響起赊琳，我...
開封第一講書人閱讀 38,896評論 0贊 274
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎砰碴，沒想到半個月后躏筏，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,311評論 1贊 310
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡呈枉，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,536評論 2贊 332
?白月光啟示錄
正文我和宋清朗相戀三年趁尼，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片猖辫。...
茶點故事閱讀 39,696評論 1贊 348
活死人
序言：一個原本活蹦亂跳的男人離奇死亡酥泞，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出啃憎，到底是詐尸還是另有隱情芝囤，我是刑警寧澤，帶...
沈念sama閱讀 35,413評論 5贊 343
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布辛萍，位于F島的核電站悯姊，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏贩毕。R本人自食惡果不足惜悯许，卻給世界環(huán)境...
茶點故事閱讀 41,008評論 3贊 325
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望辉阶。院中可真熱鬧先壕，春花似錦瘩扼、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,659評論 0贊 22
一樁弒父案邢隧，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至冈在，卻和暖如春倒慧，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背包券。一陣腳步聲響...
開封第一講書人閱讀 32,815評論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工纫谅，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人溅固。一個月前我還...
沈念sama閱讀 47,698評論 2贊 368
代替公主和親
正文我出身青樓付秕，卻偏偏與公主長得像，于是被迫代替她去往敵國和親侍郭。傳聞我的和親對象是個殘疾皇子询吴，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 44,592評論 2贊 353