任意两个多边形的求交算法 (1995年)

在计算机图形学和计算机辅助设计（CAD）领域，多边形的求交问题是基础而重要的问题之一。它在计算机辅助排样（Computer Aided Nesting，简称CAN）、数控编程、地理信息系统、碰撞检测等多种应用中都有广泛的应用。随着技术的发展，对算法的效率和通用性要求也越来越高。 我们从文章标题“任意两个多边形的求交算法”入手，多边形求交算法的目标是找出两个多边形共同占据的空间区域，即它们的交集。这是计算机图形学中一个经典的问题，因为它直接关系到图形的几何属性和空间关系。多边形求交问题的解决对于图形的显示、编辑、分析等都有着非常重要的意义。 描述中提到对A.Mangen算法的改进，这说明作者的工作是在现有算法的基础上进行的。算法改进的目标是在提高算法效率的同时，保持或增强算法的通用性。效率提升通常意味着减少算法执行时间，减少所需的内存资源，或者提高算法的可扩展性。通用性的增强可能包括算法适用范围的扩大、对不同形状和大小多边形的求交处理能力的提高。 文章中提及的关键字“排样”指的是在一个给定的平面区域内，如何合理地放置多个形状，通常是为了减少材料的浪费和提高材料的利用率。在服装裁剪、金属加工等领域，排样是提高生产效率和节约成本的重要手段。计算机辅助排样，即通过计算机程序来自动计算排样的最优解，是排样问题现代化的标志。 文章中的“离散化处理”部分，作者提到了在多边形求交算法中使用的一种预处理技术。这种技术的目的是通过简化多边形表示来降低算法的复杂度。离散化处理实质上是将连续的曲线用一组离散的点来近似，从而减少计算量。在算法中，离散化处理通常涉及到对曲线上足够密集和平滑的点进行简化，只保留能够代表多边形边界的特征点。特征点的选择依赖于曲线段的分组和弯曲度的评估。 “包围盒检测”部分描述的是另一个预处理步骤，旨在加速求交算法的判断过程。包围盒是包含多边形的最小矩形区域。通过检查两个多边形的包围盒是否相交，可以快速判断两个多边形是否可能相交。如果包围盒不相交，则说明两个多边形本身不可能有交集，这样就不必执行后续的详细求交计算，节省了计算资源。 在“求交算法的实现”章节中，作者强调了检测点是否在多边形内部、外部或边界上这一过程的重要性。为了确定点与多边形的位置关系，文章提到了“奇偶法”、“Miding-Number”法和Warnock算法。这些方法能够通过不同的几何和数学原理来确定点与多边形的相对位置，是求交算法的核心部分。 通过上述知识点的梳理，我们可以看出该篇论文涉及的不仅是一个特定的求交算法，还对相关算法进行了深入的分析和改进。同时，它还涉及到计算机辅助排样应用中对效率和通用性提升的具体实践和探索。这些内容对于当时和现在从事计算机图形学和CAD相关工作的人士来说，都是非常宝贵的知识财富。通过算法的改进，能够使得计算机辅助排样更加高效和智能，从而推动相关行业的发展。