瓜豆原理学习笔记

· · 算法·理论

瓜豆原理

一个图形经过任意旋转、缩放、平移、对称之后，与原图形保持相似，且相似比等于缩放比。

非常强大而泛用的定理。可以用来解决一整类初中的几何题。

这篇文章的目的是证明它，从地基开始重构这整套工具箱。所以默认读者已经会了这些东西，主要进行推式子。

定义 1：线性变换与仿射变换

线性变换

我们常常听说，“某某变换（比如缩放，旋转）是线性变换”。那么什么是“线性变换”？

我们称一个对 n 维点的变换是线性变换，当且仅当存在一组 \R^n \to \R 的线性变换 \{g_i\}(1\le i \le n) 使得：

f((x_1, x_2, \cdots x_n)) = (g_1((x_1, x_2, \cdots x_n)), g_2((x_1, x_2, \cdots x_n)), \cdots g_n((x_1, x_2, \cdots x_n)))

这里的“\R^n\to \R 的线性变换”指满足以下两条性质的变换：

  1. 可加性。对于变换 f，当且仅当 \forall x\in \R^n, y\in \R^n\; f(x + y) = f(x)+f(y) 时它满足这条性质。
  2. 齐性。对于变换 f，当且仅当 \forall x\in \R^n, c\in \R\; f(cx) = cf(x) 时它满足这条性质。

容易发现，这样的变换一定是形如 f((x_1, \cdots x_n)) = \sum_{i = 1}^n a_ix_i 的变换，其中 a_i 是常数。

仿射变换

很简单。一个变换 f(x) 是仿射变换当且仅当它可以写成 g(x)+c 的形式，其中 g(x) 是一个线性变换，而 c 是常数。

证明 1：旋转是线性变换

考虑点 P(x, y)，将它旋转 \theta 这个角。

自然的方法是使用极坐标。我们设 P = (r, \phi)，其中 r = \sqrt{x^2+y^2}，\phi 是 P 到原点连线与 x 轴的夹角。

进而有 x = r\cos \phi, y = r\sin \phi。

旋转 \theta 之后，P' = (r, \phi + \theta)，可以算出 x'=r\cos(\phi+\theta), y'=r\sin(\phi+\theta)。

用和角公式拆开：

x'=r(\cos \phi\cos \theta-\sin\phi\sin\theta),\\y'=r(\sin \phi\cos \theta+\sin \theta\cos \phi)

拆开括号。

x'=r\cos \phi\cos \theta-r\sin\phi\sin\theta,\\y'=r\sin \phi\cos \theta+r\sin \theta\cos \phi

代回 x = r\cos \phi, y = r\sin \phi。

x'=x\cos \theta-y\sin\theta,\\y'=y\cos \theta+x\sin \theta

于是不难发现旋转是线性变换。设 a = \cos \theta, b = \sin \theta（此时由于旋转角是常数，它们都是常数），只需选取 \{g_i\}=\{(x, y) \to ax-by,(x, y)\to bx+ay\} 即可。

你甚至可以写成矩阵的形式：

f\left(\begin{pmatrix} x \\ y \end{pmatrix}\right) = \begin{pmatrix} a & -b \\ b & a \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix}

定义 2：缩放

点（或向量）\bold{v} 的缩放是 s\bold{v}，其中 s 是一个常数。如果点的缩放不关于原点，平移坐标系使得缩放中心为原点即可。

注意我们这里的缩放特指均匀缩放。

显然，缩放是一个线性变换。

证明 2：对一条直线上的每个点进行仿射变换，得到的新图形依然是直线

设一条直线 l: Ax+By+C=0。对于它上面的任一点 (x_1, y_1)，我们进行仿射变换，得到点 (k_1x_1+k_2y_1+c_1, k_3x_1+k_4y_1+c_2) = (a, b)。

我们需要证明的是，存在一组常数 A',B',C'，使得对于任意这样产生的 (a, b)，都有 A'a+B'b+C'=0。

这显然是存在的。我们首先考虑一次项的系数 A', B'，考虑调整它们使得 x_1,y_1 的系数分别是 A 和 B 的倍数，这样，我们就可以利用 Ax+By+C=0 的性质确保整个式子的值是常数。并且溢出的常数项可以被 C' 吸收掉。

这是可以做到的，具体而言考虑方程组：

\begin{cases} A'k_1+B'k_3=nA\\ A'k_2+B'k_4=nB \end{cases}

（其中 n 是任意非零常数）

这样就能使得 x_1,y_1 的系数分别是 A 和 B 的倍数。并且两个未知数，两个方程，刚好有解（除非仿射变换本身是奇异的，行列式的值 k_1k_4-k_2k_3 等于 0）。常数项可以用 C' 全部吸收。

于是证毕，直线经过仿射变换之后依然是直线。

这样，我们就证明了瓜豆原理的一种基础情形：被变换的对象是直线。

证明 3：对一个图形进行旋转，对称或平移，新图形与原图形全等

证明框架

设 T 是一个变换（平移、旋转或反射）。\ 取任意两个点 P_1 = (x_1, y_1) 和 P_2 = (x_2, y_2)。

它们之间的向量是 \vec{v} = P_2 - P_1 = (x_2-x_1, y_2-y_1)。

它们之间的距离的平方是 d^2 = |\vec{v}|^2 = (x_2-x_1)^2 + (y_2-y_1)^2。

经过变换后，得到新点 P'_1 = T(P_1) 和 P'_2 = T(P_2)。

它们之间的新向量是 \vec{v}' = P'_2 - P'_1。

新距离的平方是 (d')^2 = |\vec{v}'|^2。

我们要证明的就是，对于平移、旋转和反射，始终有 (d')^2 = d^2。

1. 平移（Translation）

设平移向量为 \vec{b} = (c, d)。

$P'_1 = P_1 + \vec{b} = (x_1+c, y_1+d) P'_2 = P_2 + \vec{b} = (x_2+c, y_2+d)

计算新向量 \vec{v}'：

\vec{v}' = P'_2 - P'_1 = ((x_2+c)-(x_1+c), (y_2+d)-(y_1+d)) \vec{v}' = (x_2-x_1, y_2-y_1) = \vec{v}

结论： 平移变换不改变点对之间的向量。\ 所以，距离显然不变：|\vec{v}'|^2 = |\vec{v}|^2。\ 因为向量本身都没变，夹角自然也不可能变。

平移保持全等，证毕。

2. 旋转（Rotation）

设绕原点逆时针旋转 \theta 角。

对于线性变换，有一个极好的性质：$T(P_2 - P_1) = T(P_2) - T(P_1)$。 所以，$\vec{v}' = P'_2 - P'_1 = R_\theta P_2 - R_\theta P_1 = R_\theta(P_2-P_1) = R_\theta \vec{v}$。 这意味着，**原图中的任意向量 $\vec{v}$，在旋转后变成了 $R_\theta \vec{v}$**。 现在我们来证明距离不变。设 $\vec{v}=(x, y)$。 $R_\theta \vec{v} = (x\cos\theta - y\sin\theta, x\sin\theta + y\cos\theta) |\vec{v}'|^2 = |R_\theta \vec{v}|^2 = (x\cos\theta - y\sin\theta)^2 + (x\sin\theta + y\cos\theta)^2

展开它：

= (x^2\cos^2\theta - 2xy\cos\theta\sin\theta + y^2\sin^2\theta) + (x^2\sin^2\theta + 2xy\sin\theta\cos\theta + y^2\cos^2\theta)

合并同类项：

= x^2(\cos^2\theta+\sin^2\theta) + y^2(\sin^2\theta+\cos^2\theta) = x^2(1) + y^2(1) = x^2+y^2 = |\vec{v}|^2

结论： 旋转变换保持距离不变（保距性）。

接下来证明保角性。\ 设有两个向量 \vec{u} 和 \vec{v}。它们夹角的余弦值由点积公式给出：\cos\alpha = \frac{\vec{u} \cdot \vec{v}}{|\vec{u}||\vec{v}|}。

变换后的向量是 \vec{u}'=R_\theta\vec{u} 和 \vec{v}'=R_\theta\vec{v}。

我们已经证明了 |\vec{u}'|=|\vec{u}| 和 |\vec{v}'|=|\vec{v}|。

所以，要证明夹角不变，我们只需要证明点积不变，即 \vec{u}' \cdot \vec{v}' = \vec{u} \cdot \vec{v}。

设 \vec{u}=(u_x, u_y), \vec{v}=(v_x, v_y)。

\vec{u}' = (u_x c - u_y s, u_x s + u_y c) \vec{v}' = (v_x c - v_y s, v_x s + v_y c)

(其中 c=\cos\theta, s=\sin\theta)

\vec{u}' \cdot \vec{v}' = (u_x c - u_y s)(v_x c - v_y s) + (u_x s + u_y c)(v_x s + v_y c) = (u_x v_x c^2 - u_x v_y cs - u_y v_x cs + u_y v_y s^2) + (u_x v_x s^2 + u_x v_y sc + u_y v_x sc + u_y v_y c^2)

中间的四项 cs 项两两抵消！

= u_x v_x (c^2+s^2) + u_y v_y (s^2+c^2) = u_x v_x + u_y v_y = \vec{u} \cdot \vec{v}

点积确实不变！所以角度也不变。

旋转保持全等，证毕。

3. 对称/反射（Reflection）

以关于 x 轴的反射为例。变换矩阵是 F = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}。

这也是一个线性变换，所以 \vec{v}' = F\vec{v}。

设 \vec{v}=(x, y)，则 \vec{v}'=(x, -y)。

保距性：

**保角性（点积不变性）：** 设 $\vec{u}=(u_x, u_y), \vec{v}=(v_x, v_y)$。 $\vec{u}'=(u_x, -u_y), \vec{v}'=(v_x, -v_y)$。 $\vec{u}' \cdot \vec{v}' = (u_x)(v_x) + (-u_y)(-v_y) = u_x v_x + u_y v_y = \vec{u} \cdot \vec{v}$。 点积依然不变！所以角度大小也不变。 **对称保持全等，证毕。** --- 这样我们就证明了瓜豆原理的大部分。剩下的是证明缩放保持相似，且相似比等于缩放比。这几乎是相似的定义（缩放，大小不同形状相同），所以不加证明。读者也可将其作为习题。 ## 应用与工具 瓜豆原理常用于求一个点的轨迹。在一些最值问题中很常用。尤其是与点到直线距离公式搭配： 点到直线距离公式： $P(x_0,y_0)$ 到 $l:Ax+By+C$ 的距离等于： $$\frac{|Ax_0+By_0+C|}{\sqrt{A^2+B^2}}$$。 证明思路非常简单：我们首先考虑 $A$ 和 $B$ 均不为零的直线，再考虑对于特例验证其正确性。 对于一般情况，我们使用面积法。在 $l$ 上取两点 $M, N$，求出三角形 $PMN$ 的面积和 $MN$ 的长度，然后就可以求出 $P$ 到 $l$ 的高也即距离。 为了简化计算，我们选取 $M$ 的纵坐标与 $P$ 相同，$N$ 的横坐标与 $P$ 相同。 那么有 $M = (-\frac{By_0+C}{A}, y_0), N = (x_0, -\frac{Ax_0+C}{B})$。 设 $V_p = Ax_0+By_0+C$。\ 我们有 $MN$ 等于 $$ \sqrt{(\frac{V_p}{A})^2+(\frac{V_p}{B})^2} $$ 而三角形 $PMN$ 的面积则等于： $$ |\frac{V_p^2}{2AB}| $$ $P$ 到 $l$ 的距离则是： $$ \frac{|\frac{V_p^2}{AB}|}{\sqrt{(\frac{V_p}{A})^2+(\frac{V_p}{B})^2}} $$ （注意分子是面积的二倍，也就是两直角边的乘积） 把分子上的 $AB$ 乘下去，并且上下同时约去一个 $|V_p|$，就得到 $$ \frac{|V_p|}{\sqrt{A^2+B^2}} $$ 也就是我们一开始的公式。