%0 Journal Article
%A WANG San
%A LIU Run-tao
%A WANG Hong-yan
%T Algorithms for convex hull of union and intersection of two intersecting convex polygons
%D 2010
%R 10.3778/j.issn.1002-8331.2010.05.047
%J Computer Engineering and Applications
%P 154-156
%V 46
%N 5
%X 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.
%U http://cea.ceaj.org/EN/10.3778/j.issn.1002-8331.2010.05.047