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

Calculation Method of Intersection Area of Two Concave Polygons Based on Set and Recursive Operation

作　　者：温锦辉 栾尚敏 WEN Jinhui;LUAN Shangmin(College of Safety Engineering,North China Institute of Science and Technology,Beijing East Yanjiao,Beijing 101601,China;College of Computer Science,North China Institute of Science and Technology,Beijing East Yanjiao,Beijing 101601,China)

机构地区：[1]华北科技学院安全工程学院,北京东燕郊101601 [2]华北科技学院计算机学院,北京东燕郊101601

出　　处：《数学建模及其应用》2022年第1期16-22,共7页Mathematical Modeling and Its Applications

基　　金：国家重点研发计划(2018YFC0808306)。

摘　　要：由于凸多边形的交集面积计算较为容易,本文在此基础上,使用基于集合和递归运算的方法计算凹多边形的交集面积.该方法的主要思路是将凹多边形补全成为凸多边形,然后使用集合的交、差、并等运算,将凹多边形的交集面积转化为凸多边形之间的交集面积进行计算.在将凹多边形补全为凸多边形的过程中,需要根据顶点的全局凹凸性构建全局凹凸二叉树,然后从二叉树中提取多边形的凹陷和补全后的轮廓.该算法绕开了复杂的出入点的计算和判定,使得算法变得简洁,易于编程实现,对空间多面体的交集体积计算也有一定的参考意义.Because the intersection area of convex polygons is easy to calculate,on this basis,this paper uses the method based on set and recursive operation to calculate the intersection area of concave polygons.The main idea of this method is to complete the concave polygon into a convex polygon,and then use the intersection,difference,and union operation of set to convert the intersection area of two concave polygons into the intersection area between convex polygons for calculation.In the process of completing concave polygons into convex polygons,we need to build a global concave convex binary tree according to the global concave convex of vertices,and then extract the sunkens and completed contour of concave polygons from the binary tree.The algorithm bypasses the complex calculation and judgment of entry and exit points,makes the algorithm concise and easy to program,and also has a certain reference significance for the intersection volume calculation of spatial polyhedrons.

关 键 词：交集面积 凹多边形 全局凹点 全局凸点 

分 类 号：O29[理学—应用数学]