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

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

作　　者：王三[1] 刘润涛[2] 王洪艳[1] 

机构地区：[1]哈尔滨理工大学应用科学学院,哈尔滨150080 [2]哈尔滨理工大学信息与计算科学研究所,哈尔滨150080

出　　处：《计算机工程与应用》2010年第5期154-156,共3页Computer Engineering and Applications

基　　金：国家自然科学基金No.10571037;黑龙江省教育厅项目No.11511027~~

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

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]