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

摘要

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

关键词

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