格点多边形的面积——皮克定理

单位长度为 \( 1 \) ，请问下面的这个多边形的面积是多少？

直接分割计算稍显困难，那有没有简单的算法呢？——当然有√
这就是我们今天的主角——皮克定理

所谓格点多边形，即是如图中那样，所有顶点都是格点的多边形

如果将格点多边形边界上的格点数目记作 \( E \)
将其内部的格点数目记作 \( I \)

那么皮克定理表明，面积 \( S \) 可以表示为

$$ S=I+\frac{E}{2}-1 $$

在这个例子中，\( I=3,E=8 \) ，因此可以计算出面积 \( S=6 \)

注意，问题中的多边形要求是一整个，如果是两个多边形共用一个顶点的情况，这个顶点应当计数两次

定理的证明：

(以下“多边形”均省略格点二字)

首先，如果我们对两个多边形分别证明了结论成立，可以证明对于他们的拼接(将若干条边接在一起)结论也成立

假设两个多边形内部和边界的格点分别为 \( I_1,I_2,E_1,E_2 \) ，面积为 \( S_1,S_2 \)
公用边界上的格点数目是 \( C \)

那么拼接得到的新多边形的内部格点为 $$ I=I_1+I_2+C-2 $$

当作为新多边形看时，公用边界除两端外就变成了内部
我们假设只有一条公用边界，那么内部格点就需要加上 \( C-2 \)

新多边形的边界格点数为 $$ E=E_1+E_2-2C+2 $$

验证等式 $$ I+\frac{E}{2}-1=I_1+\frac{E_1}{2}-1+I_2+\frac{E_2}{2}-1=S_1+S_2=S $$
其中的 \( C \) 恰好抵消掉

用同样的讨论也可以证明我们能做到从一个多边形中切除另一个多边形

由于每个多边形一定可以拆分成若干个格点三角形，那么我们只需要对三角形证明结论

接下来，对于每个格点三角形，我们可以将它拆分为一个矩形中去掉若干个直角三角形(或矩形)，而矩形显然可以拆分为两个直角三角形，因此我们只需要对直角三角形证明结论

对于一个直角三角形而言，设它两条直角边上的格点数分别为 \( a,b \) ，斜边上的格点数为 \( c \)，( \( c \) 实际上等于 \( a-1 \) 和 \( b-1 \) 的最大公约数加上 \( 1 \) )

那么
$$ \begin{split}
S&=\frac{(a-1)(b-1)}{2}\\
I&=\frac{ab-c}{2}-(a-2)-(b-2)-1\\
E&=a+b+c-3
\end{split} $$

其中 \( I \) 的计算方法用一个全等的直角三角形将图形补成一个矩形，那么一个直角三角形中的格点就是 (总格点数目 – 公共斜边)/2 再减去两条直角边

容易验证恒等式 \( S=I+\frac{E}{2}-1 \)

至此，结论证毕

这个结论还有相当美妙的证明
参见matrix67的博客