二维点阵图形的周长估算

Corfton Formula

任给平面上的一条直线段$\gamma$，以及全体与之相交的直线构成的集合$L$。现将$L$中的每条直线$l$参数化为$l$到原点的距离$p$以及$l$与$+\mathbf{x}$的夹角$\varphi$，则容易证明：

$$\mathrm{length}(\gamma )=\frac{1}{4}{\iint }_L\mathrm{d}\varphi \mathrm{d}p$$

工程地说，我们可以随机采样一堆直线，利用这些直线和$\gamma$的交点数量以及$(p,\varphi )$的pdf来估算出$\gamma$的长度。

粗看起来这个结论并没有什么用，但我们知道，任意一条正常的曲线都可以被微元化，其弧长也可以被许多小直线段的长度之和近似，那么就可以推而广之——

$$\mathrm{length}(\gamma )=\frac{1}{4}\iint n(\gamma ,p,\varphi )\mathrm{d}\varphi \mathrm{d}p$$

其中$\gamma$是任意一条连续且弧长有限的平面曲线，$n(\gamma ,p,\varphi )$是曲线$\gamma$和直线$(p,\varphi )$的相交次数。

点阵图形周长

考虑一个形状比较复杂的二维封闭图形，我们以足够高的分辨率把它光栅化到二维均匀网格上。网格中位于图形内部或边缘上的点赋值为1，其他点赋值为0。所谓”足够高的分辨率“是指单个格子在尺度上比图形中最小的形状特征还要小许多，从而不会因混叠（aliasing）而看不出原本图形的样貌。

现在我们的任务是：根据光栅化结果估算图形的总周长，即边界曲线的总弧长。最容易想到的做法是：用类似marching squares的技术把图形的边界曲线重建出来，滤除光栅化过程带来的噪声，然后显式地计算曲线总长度。这方法虽然能跑，但效率捉鸡，搞不好还得带个超参。

平面网格天然地采样了大量穿过整数格点的直线。譬如，每行格点采样一条水平直线；每列格点采样一条水平竖线；沿朝右下方向的网格对角线，采样一条斜45°的直线；沿朝左下方向的网格对角线采样另一条斜45°的直线……

现对网格中某一行格点上的每个点，我们观察它和右侧相邻格点的取值，有四种可能：

• 0，0：两个点都在图形外
• 0，1：进入图形内部
• 1，0：离开图形内部
• 1，1：两个点都在图形外

其中第二种和第三种情况都可以被看作这条水平线和图形的交点。因此，只需要观察每个采样点的值是否和它右侧采样点的值相异，并统计这样的采样点数量，就能计算出水平线与图形的交点个数。

以此类推，我们也可以沿着竖直方向、两条对角线方向做同样的统计。对每一种方向，我们都得到了一族等间距的平行直线，并可以通过比较相邻格点的取值是否发生变化，来计算这些直线与图形边界的相交次数之和。

从Corfton公式的角度看，这正是在对角度参数$\varphi$和位移参数$p$做离散采样。方向的个数是有限的，而在每个方向上，$p$的采样间距则由网格间距决定。因此，连续积分

$$\frac{1}{4}\int \int n(\gamma ,p,\varphi )\mathrm{d}p\mathrm{d}\varphi$$

可以被加权求和所近似。以最简单的情形为例，取四个方向：水平、竖直，以及两条45°对角线。设在这四个方向上统计得到的交点总数分别为$N_0,N_{\pi /2},N_{\pi /4},N_{3\pi /4}$，则图形周长可以用下式近似：

$$\mathrm{Perimeter}\approx \frac{\pi }{8}\left(N_0+N_{\pi /2}-\frac{1}{\sqrt{2}}(N_{\pi /4}+N_{3\pi /4})\right),$$

其中系数$1/\sqrt{2}$来自对角线方向相邻扫描线之间的间距，常数$\pi /8$来自原公式中的$1/4$和对$\varphi$积分的归一化因子。 这里的“相交次数”并不需要真正地计算几何意义上的交点；在离散网格上，只要相邻网格的取值发生0、1之间的翻转，就可以被视为一次相交。

方向扩展

平面网格还隐式地包含了更多方向的直线，比如对网格点$(x,y)$，可以认为另一网格点$(x+1,y+2)$与其的异同描述了直线$(x,y)-(x+1,y+2)$在此处是否穿入或穿出了图形。以此类推，在网格精度足够高的情况下，我们有无穷多方向的直线朝向可以选择，也就可以不断提高Corfton公式中角度$\varphi$的离散化精度。

当然，类似$(1024,1)$这样的朝向会对网格精度提出过高的要求，实践意义不大。在我所遇到的应用中，选取4~16个方向就足以将误差控制得很好了。