关键词: 凸多边形的交, 并, 凸壳, 单调段

Abstract: 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 decided by two convex polygons of the same types of monotonous paragraph.The algorithm makes full use of the order of vertices of the convex polygon，so that the minimum time complexity of the algorithm can be achieved.

Key words: intersections of convex polygon, union, convex hull, monotonic segment