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