求两个相交凸多边形并的凸包及交的算法

凸多边形交、并求解的难点在于如何维护结果多边形的顶点序列。利用坐标的极值将凸多边形分成几个段，利用凸壳顶点有序性，分段计算凸壳顶点而得到凸壳。两个相交的凸多边形P和Q，求P和Q并的凸壳通过计算它的4个单调段来进行。每个单调段的点是否是凸壳上的点只与2个凸多边形中的同一类型的单调段有关。该算法充分地利用了凸多边形顶点的有序性，使算法的时间复杂度达到最小。

Algorithms for convex hull of union and intersection of two intersecting convex polygons

The key difficulty of calculating the intersection and union of convex polygons is how to maintain the vertex sequences of the result polygon.In this paper,the algorithm divides the convex ploygon into several segments by the extreme points,and then computes the convex hull points of every segment.The union convex hull of two intersecting convex polygons P and Q is calculated through calculating its four monotonic segments.Whether the points of each monotonous segment is the points of convex hull,it is only...