优化移动碰撞算法：降低NFP求解复杂性

本文主要探讨了在计算机工程与应用领域的一项重要研究——改进临界多边形生成算法。临界多边形（No-Fit Polygon，NFP）作为一种关键的几何计算工具，对于解决多边形的靠接位置问题和重叠判断在排样问题中有显著作用，能显著降低重复计算和碰撞检测的复杂性，提高问题解决的效率。 原有的移动碰撞算法由Adamowicz等人提出，虽然易于理解，但在处理复杂情况时计算成本较高。为了克服这一局限，Burke等人提出了一个基础算法，本文在此基础上进行改进。作者着重研究了Minkowski矢量和法，这是一种针对凸多边形效率较高的方法，但不适用于凹多边形。Bennell等人和吴忻生等人分别通过倾斜图法和Ghost的斜率图法对这个问题有所改进，但仍存在不足。 刘胡瑶等人通过将滑动碰撞问题转化为轨迹线提取，提出了基于轨迹计算的NFP求解算法，尽管这种方法在某些情况下可能降低计算复杂度，但对凹多边形的处理仍然存在挑战。针对这些问题，本文作者深入剖析Burke等人的算法，并设计出一种改进方案，旨在减少几何计算的复杂性，使得在实际的二维排样问题中，能够实现更为高效和实用的临界多边形生成。 该改进算法不仅考虑了多边形的移动特性，还可能融入了启发式策略，使其在处理复杂排样场景时更具优势。通过实例验证，这个改进算法已被成功应用于皮革自动排样软件中，证明了其有效性和实用性。这项研究对优化多边形排样问题的算法性能，提升工业设计和自动化领域的计算效率具有重要意义。