基于集合与递归运算的两凹多边形交集面积计算方法

作者：温锦辉; 栾尚敏^*

来源：数学建模及其应用, 2022, 11(01): 16-22.

DOI：10.19943/j.2095-3070.jmmia.2022.01.02

• 交集面积
• 凹多边形
• 全局凹点
• 全局凸点

由于凸多边形的交集面积计算较为容易，本文在此基础上，使用基于集合和递归运算的方法计算凹多边形的交集面积.该方法的主要思路是将凹多边形补全成为凸多边形，然后使用集合的交、差、并等运算，将凹多边形的交集面积转化为凸多边形之间的交集面积进行计算.在将凹多边形补全为凸多边形的过程中，需要根据顶点的全局凹凸性构建全局凹凸二叉树，然后从二叉树中提取多边形的凹陷和补全后的轮廓.该算法绕开了复杂的出入点的计算和判定，使得算法变得简洁，易于编程实现，对空间多面体的交集体积计算也有一定的参考意义.

• 单位
  华北科技学院