基于Voronoi图的多边形中轴提取及骨架化算法

资 源 简 介

该项目旨在利用MATLAB平台实现对任意闭合简单多边形的中轴（骨架）的精确提取。其核心功能是基于几何拓扑原理，通过对多边形边界进行高密度离散采样，并利用Voronoi图（泰森多边形）的特性来逼近连续的中轴线。算法首先接收多边形的顶点序列，动态计算各边界段的法向量与曲率特征，随后通过约束性计算生成Voronoi顶点，并利用严格的几何准则筛选出位于多边形内部的有效节点。为了保证中轴的连贯性与准确性，项目还包含了针对噪声支点的剪枝优化处理，能够自动识别并剔除由于边界微小起伏产生的伪骨架分支。该实现方案支持具有凹

详 情 说 明

项目介绍：任意简单多边形中轴提取算法实现

本项目提供了一套基于 MATLAB 开发的几何处理工具，旨在精确提取任意闭合简单多边形（包括凸多边形与凹多边形）的中轴线（亦称骨架）。该算法采用离散几何逼近思路，通过在多边形边界进行高密度采样并构建 Voronoi 图（泰森多边形），从而生成能够反映图形拓扑特征的中轴结构。该实现不仅能够准确勾勒出图形的几何中心线，还能定量计算中轴各点到边界的局部半径（最短距离），为形状分析、路径规划及工业设计提供基础数据支持。

功能特性

1. 复杂多边形支持：算法能够有效处理具有凹部和凸部的复杂几何形状，保持原始图形的拓扑结构。
2. 高精度采样控制：支持动态调整边界采样步长，通过提高采样密度实现对连续中轴线的精细逼近。
3. 严格几何过滤：集成双重筛选机制，确保所有提取的中轴点及连线段均严格位于多边形内部，防止产生跨越边界的无效分叉。
4. 智能剪枝优化：内置迭代剪枝功能，能够识别并剔除由于边界微小起伏（离散噪声）产生的冗余末梢分支。
5. 半径场计算：自动计算中轴节点到最近边界点的欧几里得距离，并以色彩映射表的形式直观展示局部宽度特征。
6. 结果可视化：提供完整的数据可视化方案，包括多边形填充、中轴线绘制以及基于半径大小的节点热力图显示。

使用方法

1. 环境准备：确保计算机已安装 MATLAB 环境。
2. 定义多边形：在程序开始处定义多边形的顶点序列（坐标对），确保多边形是闭合的。
3. 设置参数：

* 采样步长：修改 sampleDist 参数以平衡计算精度与速度（数值越小精度越高）。 * 剪枝阈值：修改 pruneThreshold 以调整对微小分叉的过滤强度。

1. 运行程序：直接运行主函数。程序将自动执行从采样、构图到剪枝的所有操作。
2. 输出查看：程序运行结束后将弹出窗口显示提取结果，并生成包含节点坐标、边连接关系及局部半径的结构体数据。

系统要求

• MATLAB R2016b 或更高版本。
• 通常无需额外工具箱（核心函数如 voronoin, inpolygon 属于 MATLAB 基础功能）。

算法逻辑与实现细节

程序的实现严格遵循以下几何拓泊流程：

1. 边界离散化抽样 算法通过一个专门的采样模块对多边形连续边界进行重采样。对于每一条边，根据预设的采样步长进行等间距内插，将多边形转化为高密度的散点集合。这一步是利用离散 Voronoi 图逼近连续中轴的基础。

2. Voronoi 图构建与顶点筛选 对所有采样点执行泰森多边形剖分，获取所有 Voronoi 顶点。由于 Voronoi 顶点在数学上定义为到其周围采样点等距离的点，因此它们是中轴线的天然候选者。程序利用射线检测算法（inpolygon）判定每个顶点是否位于多边形内。

3. 中轴边约束连接 在构建边连接时，程序执行严格的合法性检查：

• 端点校验：只有当一条 Voronoi 边的两个端点均位于多边形内部且不是无穷远点时，该边才被视为合法。
• 中点校验：为了防止在狭窄区域或极端凹部发生“越界”现象，算法会进一步验证该边线段的中点是否同样位于多边形内部。

4. 局部半径场提取 对于每一个保留下来的中轴节点，程序计算其到所有边界采样点的最短欧式距离。该数值代表了多边形在该位置的“局部厚度”，即以该点为圆心且与边界相切的最大内切圆半径。

5. 迭代剪枝优化模块 这是提升中轴质量的关键步骤。离散采样往往会导致中轴在末端产生大量微小分叉。该模块通过以下逻辑进行优化：

• 拓扑分析：通过邻接矩阵计算每个节点的度数，识别出度为 1 的“叶子节点”。
• 长度判定：如果叶子节点与其唯一邻居之间的边长小于设定的阈值，则认为该分支是由采样波动引起的噪声，予以删除。
• 迭代清理：该过程会循环执行，直到没有任何满足条件的短分支为止，从而保证了生成的骨架既简洁又连贯。

6. 数据映射与重分布 在剪枝完成后，程序会重新映射剩余节点的索引，更新邻接关系和半径信息，确保最终导出的结构体数据在逻辑上是完整且连续的。

核心算法分析

• Voronoi 近似原理：该算法利用了“当边界采样点密度趋向无穷大时，内部 Voronoi 边的集合收敛于中轴”的几何特性。
• 效率考量：通过矩阵化处理距离计算（sum((...).^2, 2)）和利用 MATLAB 内置的空间几何函数，程序在处理数千个采样点时仍能保持较高的运行效率。
• 鲁棒性机制：通过 unique 函数处理重复边，以及对采样点重合情况的预处理，增强了代码在处理复杂自交趋势或极端形状时的稳定性。