非契合多边形计算的优化方法

"本文介绍了计算非适应多边形（No-Fit Polygon, NFP）的一种改进方法，主要关注两个非凸多边形的情况。NFP是在两个多边形不重叠的情况下，一个多边形可能占据的所有可行位置的集合。这种计算在二维包装问题和机器人运动规划等场景中有广泛应用。现有的算法在处理两个非凸多边形时效率较低或实现困难。该文提出了一种扩展自Ghosh（CVGIP: Image Understanding 54(1991)119）的NFP算法，利用排序的多边形边列表进行高效计算。关键词包括：非适应多边形、二维包装和Minkowski和。" 在二维空间中，非适应多边形（NFP）的计算是解决各种几何优化问题的关键步骤，特别是在包装设计和路径规划等领域。传统的算法对于处理两个凸多边形或者一个凸一个多边形的情况相对有效，但当涉及到两个非凸多边形时，由于其复杂的形状和可能的内部凹陷，计算NFP变得相当复杂和低效。 Ghosh的NFP算法是通过计算多边形的Minkowski差来找出不相交区域的基础。Minkowski差是两个几何形状的组合，结果是一个新的形状，其中每个输入形状的每个点都被另一个形状平移并相减。对于凸多边形，这种方法可以直接得出NFP，但对于非凸多边形，需要更复杂的处理，因为Minkowski差可能会产生更多的非凸部分。 本文提出的改进方法对Ghosh的算法进行了扩展，通过操纵排序的多边形边列表来更有效地找到NFP。这种方法可能包括以下步骤： 1. 对两个非凸多边形的边缘进行排序，以便于后续处理。 2. 计算多边形的Minkowski差，生成一个初始的非适应多边形。 3. 使用排序边列表来识别和修剪Minkowski差中的无效部分，这些部分不属于NFP。 4. 遍历边列表，检查每条边是否与NFP的边界相交，不断更新NFP的边界。 5. 继续这个过程，直到所有边都检查完毕，最终得到的边界即为所求的非适应多边形。 这种方法的优势在于它简化了对非凸多边形NFP的搜索过程，通过有序的数据结构提高了计算效率，降低了实现难度。对于需要快速解决复杂NFP计算的问题，如实时机器人路径规划或动态包装设计，这样的优化尤其重要。 总结来说，这篇论文提供了一个在两个非凸多边形之间高效计算非适应多边形的新策略，对于优化二维几何问题的解决方案具有重要的理论和实践价值。通过改进Ghosh的算法并引入排序边列表的概念，它为计算NFP提供了一种更有效且易于实现的方法。