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

Computer Algorithm for Intersection Area of Two Convex Polygons

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

In order to solve the intersection area of two planar convex polygons,this paper improves the original six step method.In the process of finding the intersection point,this paper determines whether the line segments intersect by judging whether they repel and straddle.In the process of sorting the intersection vertices,the intersection vertices are sorted by the cosine value of the azimuth angle of each point relative to the starting point.The time complexity is O(MN),where m and n are the number of vertices of two convex polygons respectively.