两凸多边形交集面积的计算机算法

摘要：

为了求解两个平面凸多边形的交集面积,对原有的六步法进行了改进.在求交点的过程中,通过判断线段之间是否排斥和跨立来确定线段之间是否相交;在交集顶点的排序过程中,通过各点相对于起始点的方位角余弦值大小对交集顶点进行排序.整个求面积的过程易于实现,时间复杂度为O(mn),其中,m和n分别为两个凸多边形的顶点数目.

关键词：凸多边形交集;相交判断;顶点排序

所属期刊栏目：10

分类号：O29(应用数学)

资助基金：国家重点研发计划;河北省物联网监控中心;河北省重点项目;河北省重点研发计划项目;河北省高等学校科学技术项目;中央高校基本业务费

在线出版日期：2021-09-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：44-48