基于MATLAB的简单多边形核计算算法优化及其在几何建模中的应用

本研究针对传统多边形核算法在MATLAB环境中实现不足的问题，提出了一种基于三角形定向分析的改进算法。通过优化凹顶点处理逻辑和交点排序机制，显著提升了算法鲁棒性，解决了原方法在复杂几何结构中的失效问题。研究实现了O(NP 2 )时间复杂度，在160余个测试案例中验证了与C++库CinoLib的等效性，为计算机图形学和有限元分析等领域提供了高效计算工具。

　　

在计算几何领域，简单多边形的核(kernel)计算是计算机图形学、机器人路径规划和有限元网格生成等应用的核心问题。传统算法通常采用半平面相交法，但存在实现复杂、计算效率低等问题。尤其值得注意的是，主流计算工具如MATLAB缺乏现成的核计算函数，而现有开源实现如CGAL、Boost.Geometry等对非专业用户存在使用门槛。更关键的是，Zhao和Wang于2010年提出的基于三角形定向的替代算法，虽具有理论创新性，但在处理多重交点或准共线顶点时会出现严重错误，这极大限制了其工程适用性。

针对这些技术瓶颈，研究人员开展了一项突破性研究。通过系统分析原算法的失效机制，发现其核心问题在于：当同一线段上产生多个交点时，缺乏有效的优先级判定规则；此外，对凹顶点(concave vertex)邻域处理的不足会导致核边界误判。研究团队创造性地引入双重验证机制——通过比较三角形T₁
-T₃
的定向关系(Orient)来智能选择有效交点，并开发了基于距离度量的顶点排序算法。这些改进使算法能正确处理图3所示的多重交点情况，以及图4中的退化条件。

关键技术方法包括：1) 采用atan2函数实现顶点凹凸性检测，设置10^-14
的数值容差；2) 基于行列式计算三角形定向，建立射线-线段相交判定准则；3) 构建动态顶点列表kernP/kernP1实现核边界迭代更新；4) 从2D形状结构数据集选取187顶点量级的测试案例进行验证。

研究结果主要体现在三个方面：
算法优化方面：通过引入"update2stepconcnode"函数扩展凹顶点处理范围（图7），解决了原算法在Heart类多边形中产生10^-3
级面积误差的问题。改进后的算法在保持O(N_P
)线性复杂度（凸多边形）的同时，将最坏复杂度控制在O(N_P
²
)。

计算效能方面：对2560个顶点的卡迪尔曲线多边形测试表明（图15），采用10^-14
容差的orientation函数可获得与CinoLib一致的5顶点核，面积误差低于10^-7
。三类测试家族（凸多边形、星形多边形、空核多边形）的时序分析显示（图14），其时间增长指数分别为0.7、1.2-1.5和0.9，验证了算法的线性趋势。

应用验证方面：在160个测试案例中，包括从GitHub获取的60顶点测试用例（图8）和Shape Structure数据集的187顶点复杂多边形（图9），改进算法与C++库的结果一致性达97.5%。仅5个曲线多边形因离散化差异产生2-4个额外顶点，但核面积保持完全一致。

这项发表于《Journal of Computational Science》的研究具有多重意义：理论上，首次系统解决了Zhao-Wang算法在退化条件下的失效问题；工程上，提供的MATLAB实现填补了该语言在核计算领域的工具空白；应用方面，其10^-14
精度的数值稳定性使其特别适合有限元网格质量评估。值得注意的是，研究揭示的"相邻顶点扩展"机制（图11）为后续处理高曲率边界提供了新思路。未来工作可探索该算法在三维非凸多面体核计算中的扩展应用。