# 距离场计算：维度诱导法（dimension-induction）的基本原理

# 介绍
三维空间下计算最短距离场，或者叫欧氏距离变换（Euclidean distance transformation, EDT），其目的是找到空间中任一个点到空间中的一个物体上距离该点最近的那个点，计算这两点之间的距离。
是一个计算密集型问题，应用非常广泛（图形分析、Level Set等等），这里不再废话。今天读论文发现一种很好的思路，整理出来。
除了暴力穷举这类$O(N^2)$复杂度的无脑算法，一般求解最短距离场有三类成系统的算法：
1. 波前演化类算法 wavefront propagation, 沿径向扫描计算，典型的如快速推进法 fast marching method。
2. Voronoi 图类算法，由Voronoi图/Delaunay三角剖分出发，得到最短距离场。之后按部就班的$O(N)$复杂度出结果。
3. 维度诱导法 dimension-induction（我自己翻译的，没找到中文），也就是这篇文章要说的。  
 
# 算法
## 流程
设想一个三维空间，其中有一物体，需要计算最短距离场。Dimension-induction 方法的操作步骤是：
1. 画网格，离散物体与空间。
2. 沿z轴将网格切片成一层一层的（想像连城诀中老和尚教的“劈纸削腐”），对于每一层的二维网格，分别计算每个网格到物体最短距离场。二维的即使穷举也容易计算，看完这一段之后，可以用同样的方法将此二维问题简化为一维。计算结果表示为$D(x,y;z)$。
3. 求解最终距离场：对于$z_1$层上的网格点$(x_1,y_1,z_1)$，遍历所有的$(x,y,z_1)$，计算：
$$D(x_1,y_1,z_1) = \min_{0<i<z_max}{\sqrt{{D(x_1,y_1;z_i)}^2+(z_i-z_1)^2}} $$
即，对于每一个点，保持$x,y$坐标不变，遍历$z$计算上面公式中中的最小值，得到的值即为整个三维场中的最短距离，也就是我们想要的最短距离场。
## 证明
### 设想
设有点$A(x^*,y^*,z_1)$与$A'(x^*,y^*,z_2)$，即A'点处于A点正上方（或者正下方）。如果在$z=z_2$这一层网格中（二维空间），离$A'$点最近的物体上点是$X(x,y,z_2)$。那么，在三维空间中，对于处在该层网格上的物体的所有点，距离$A$点最近的点仍然是$X$点。
### 证明
显然
$$AX=\sqrt{AA'^2+A'X^2}$$
$$AX'=\sqrt{AA'^2+A'X'^2}$$
假设在$z=z_2$这一层网格中的物体上，存在距离$A$点比$X$点更近的点$X'$，使得$A'X'$<$A'X$，那么，必然有$A'X'$<$A'X$，这与前面假设的$X$点是这一层二维网格中物体上距离$A'$点最近的点相矛盾。故不存在更近的$X'$点。