Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (5): 154-156.

• 图形、图像、模式识别 •

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

WANG San1，LIU Run-tao2，WANG Hong-yan1

1. 1.Applied Science College，Harbin University of Science and Technology，Harbin 150080，China
2.Institute of Information and Scientific Computing Technology，Harbin University of Science and Technology，Harbin 150080，China
• Received:2008-08-15 Revised:2008-10-27 Online:2010-02-11 Published:2010-02-11
• Contact: WANG San

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

1. 1.哈尔滨理工大学 应用科学学院，哈尔滨 150080
2.哈尔滨理工大学 信息与计算科学研究所，哈尔滨 150080
• 通讯作者: 王 三

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.

CLC Number: