计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (5): 154-156.DOI: 10.3778/j.issn.1002-8331.2010.05.047

• 图形、图像、模式识别 • 上一篇    下一篇

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

王 三1,刘润涛2,王洪艳1   

  1. 1.哈尔滨理工大学 应用科学学院,哈尔滨 150080
    2.哈尔滨理工大学 信息与计算科学研究所,哈尔滨 150080
  • 收稿日期:2008-08-15 修回日期:2008-10-27 出版日期:2010-02-11 发布日期:2010-02-11
  • 通讯作者: 王 三

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

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

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

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

中图分类号: