5.6 中轴
(Medial Axis)

维诺图有几个推广方向，其中一些推广具有相当大的实际意义。在本节中，我们仅涉及其中最简单的一种推广——允许站点集合为无限点集，特别是多边形的连续边界。

在 5.2 节中，我们将维诺图定义为最近站点不唯一的点集，即，这些点与两个或多个站点的距离相等且最近。 对于多边形 \(P\) 内部的点集，该集合中的点到多边形的边界 \(\partial P\) 上有不止一个最近点，我们称这个点集为多边形的中轴。非常相似的定义可用于任意的点集， 但在这里我们将仅研究构成多边形边界的情况。

图 5.20 描述了矩形的中轴。矩形内部水平线段上的每一点到矩形上下两边的距离相等。对角线段上的每一点到矩形的两条相邻边距离相等。 并且水平线段的两个端点到矩形的三条边距离相等。

图 5.21 给出了一个更复杂的例子，这是一个有八个顶点的凸多边形。从这个例子中人们可能会猜，凸多边形 \(P\) 的中轴是一棵以 \(P\) 的顶点为叶子的树。 确实是这样的，甚至对于非凸多边形也是如此。中轴上的每一点都是一个与边界至少在两点处相切的圆的圆心。正如维诺图的顶点是与三个站点相切的圆的圆心一样， 中轴的顶点是与三个不同边界点相切的圆的圆心，如图 5.22 所示。

Figure5.20, Figure5.21 有些糊，影响排版美观，默认折叠了，点击展开>>>

有时多边形 \(P\) 的中轴被定义为最大圆(maximal circles)圆心的轨迹，即，\(P\) 内部的圆，且其本身不被 \(P\) 内部的任何其他圆所包含。 将多边形转换为中轴的过程，有时被称为"草火变换(grassfire transformation)"。燎原。 因为如果将多边形 \(P\) 想象成一片干草地，那么同时点燃 \(P\) 的边界会使火以均匀的速率向内燃烧，而中轴就是熄灭点的集合——即火焰与来自另一个方向的火焰相遇的地方。 这个比喻与 5.1 节中讨论的森林火灾之间的联系应该是显而易见的。

中轴是 Blum(1967) 提出的，用于研究生物形状。他将其视为某种类似于骨架(轴)的东西，贯穿于多边形的中间(中位线)。 貌似在 3D 打印里面会用到这个，它们称之为骨骼线。 这对于凸多边形来说不如对非凸和平滑形状那么明显，而后者才是 Blum 的主要兴趣所在。 人们可以在一定程度上根据其中轴的结构来表征一个形状，这引起了模式识别和计算机视觉领域研究人员的极大兴趣 (Bookstein 1978)。例如，Bookstein (1991, pp. 80–7) 用它来表征正常下颌骨和变形下颌骨之间的差异。它可用于计算多边形的向内偏移：即多边形的一个缩小版本，其所有边界都向内偏移了固定距离。 多边形的向外或扩展偏移依赖于中轴。计算偏移量在制造中是一项重要任务，其中切削公差自然会导致偏移形状(Saced, de Pennington 和 Dodsworth 1988)。

具有 \(n\) 个顶点的多边形的中轴可以在 \(O(n \log n)\) 时间 (Lee 1982) 内构造出来；也存在更实用的算法 (Yap & Rokne 1991)，尽管其渐近速度较慢。 对于凸多边形，存在 \(O(n)\) 时间复杂度的算法 (Aggarwal, Guibas, Saxe & Shor 1989)。

5.6.1. 练习

1. 非凸多边形的中轴 Medial axis of a nonconvex polygon。通过举例表明，非凸多边形的中轴可以包含曲线段。关于这些曲线的函数形式，你能得出什么结论?
2. 中轴与维诺图 Medial axis and Voronoi diagram。凸多边形 \(P\) 的中轴与其顶点的维诺图之间是否存在某种关系? 猜想这种关系的一些性质，并尝试证明它们或构造反例。
3. 多胞形的中轴 Medial axis of a polytope。描述凸多胞形的中轴必须是什么样子的。
4. 直骨架 Straight skeleton。Aichholzer, Alberts, Aurenhammer & Gärtner (1995) 提到了一种类似于中轴的骨架，但即使对于非凸多边形，它也是由直线段组成的。 将多边形的每条边以恒定速度向内平行移动，相邻边随之收缩或增长，使得顶点沿角平分线移动。当一条边收缩至零长度时，其相邻边变为彼此相邻。当一个凹顶点撞到一条边时， 多边形被分割，收缩过程在分割后的部分上继续。手动计算几个单连通字母形状的直骨架，T, E, X。对直骨架的性质提出一些猜想。