统一的带岛屿多边形Delaunay三角剖分算法：高效与应用

本文档探讨了一种针对带岛屿多边形的统一Delaunay三角剖分算法，发表于2009年的《东北大学学报》自然科学研究版。该算法是由马洪滨、郭甲腾、何群和刘馨蕊四位作者共同提出的，他们主要在东北大学资源与土木工程学院进行研究。 Delaunay三角剖分是一种经典的计算几何方法，用于将多边形内的点分布均匀地划分成一系列不相交的三角形，以便于后续的数据处理和分析。传统的方法在处理包含岛屿的多边形时，可能会遇到困难，因为岛屿会形成特殊的区域，使得三角形划分变得复杂。为了解决这个问题，作者们设计了一种新的算法，它首先将所有带岛屿多边形的顶点组织成一个基于多边形边约束的Delaunay不规则三角网（CD-TIN）。这种网络结构允许他们在考虑多边形边界的同时，对内部和周围的三角形进行有效的处理。 算法的关键创新在于提出了一种基于三角形顶点绕向的多边形域外三角形判定法则，这一规则有助于识别那些不属于多边形区域的三角形，从而剔除它们，确保最终的三角剖分仅限于多边形内。这种方法有效地避免了不必要的计算，提高了算法的时间效率，并且对于含有大量岛屿的情况表现出良好的鲁棒性。 实验结果表明，该算法在处理含有大量岛屿的多边形三角剖分任务时，无论是速度还是准确性上都表现出色。它被成功地应用于基于剖面的三维矿体建模与可视化系统中，解决了包含夹石或孔洞的矿体剖面多边形三角剖分问题，这在地质资源管理和可视化中具有重要的实际应用价值。因此，这个算法不仅提升了三角剖分技术在复杂地形处理上的效能，还为实际工程中的空间数据分析提供了有力工具。 这篇论文的核心内容是介绍了一种新的、适应性强的带岛屿多边形Delaunay三角剖分算法，它通过改进的CD-TIN构建和精确的域外三角形判断规则，实现了高效、稳定的三角化处理，对于解决实际领域中的复杂几何问题具有显著的意义。