计算两凸多边形的并集多边形及其面积的计算机算法与实现

Algorithm and Implementation for Computing the Union of Two Convex Polygons and Its Area

提出计算两平面凸多边形的并集(多边形)及其面积的计算机算法,并对算法实现给出详细的计算过程。程序实现中,文中将算法分为判定点是否在多边形内部、求两多边形交点、求并集多边形及其面积三部分。引入利用向量叉积符号判定三角形的方向,进而判别平面上一点是否在凸多边形内的方法,简化了计算。还进一步提出了运用“区间分割”求两相交线段交点的新颖方法。

This paper presents an algorithm for computing the union polygon and its area of two convex polygons. It also discusses the implementation detail of the algorithm, which is divided into three pieces: checking whether a point being in a polygon or not, evaluating the intersects of two polygons, and computing the union polygon and its area. A method to decide whether a vertex on a plane is in a convex polygon or not is presented according to the sign of the third dimension element of cross product of two vectors; and by subdividing interval technology, a novel method for computing the point of intersection of two line segments has been developed. The idea of the algorithm in this paper is easy to understand and implement.