计算几何是计算机理论科学的一个新的极有生命力的研究领域,该学科已经有了巨大的发展并且产生了一系列的理论成果,在理论和应用上都具有十分重要的意义,叠置算法是计算几何研究领域当中的一个分支,其研究成果已在动态仿真、机器人学、地理信息系统等许多领域中得到了广泛的应用,尤其在机器人学领域,它是利用Minkowski和计算机器人无碰撞路径过程中的重要步骤。因此,如何准确地为机器人计算出无障碍的路径,一直是国内外学者研究的重要课题。首先,叠置算法是计算两个多面体Minkowski和的重要步骤,计算线段之间的交点是叠置的第一步。在对国内外研究现状进行综合分析的基础上,深入研究现有的线段求交算法。通过为图层赋予颜色属性,提出了基于平面扫描的线段求交算法,分析了算法的详细执行过程和算法的执行效率,并讨论了该算法在众多领域中的应用。其次,通过对现有的叠置算法的研究,发现一些算法存在不足之处,例如不能计算平面划分为凹多边形的叠置。为了克服现有叠置算法的缺陷,提高计算叠置的执行效率,通过引入广度优先遍历图的思想,本文提出了平面内任意多边形简单划分的叠置算法,算法可以计算平面内多边形任意简单划分的叠置。整个算法分为计算交点、拓扑重组和更新双向链接边表三步。再次,通过实例来展示了叠置算法的详细执行过程,并对算法的正确性和复杂度进行了分析。最后,通过详细的实验过程验证了本文的研究内容,通过与现有算法的对比,对实验结果进行了详细分析。