摘要
目的设计并分析求两个任意多边形的并的一种新算法．方法利用分治思想设计算法，即根据Ｐ，Ｑ凸壳及Ｐ与Ｑ的凸壳的不同位置关系，分６种情况分别求并Ｐ∪Ｑ的边界．结果成功设计出新的算法并分析出该算法的时间复杂性为Ｏ（ｎ＋ｍ）次判断两条线段是否相交，其中ｎ，ｍ分别是多边形Ｐ与Ｑ的顶点数．结论该算法优于逐次判断Ｐ的每条边是否与Ｑ的边相交的方法．
Aim\ Designing and analysing a new algorithm for solving the union of two arbitrary polygons Methods The algorithm was designed according to the divide andconquer idea, that is ,to consider six cases and solve the boundary of the union P∪Q respectively in terms of the distinct positional relation of the convex hulls of polygons P, Q as well as the convex hulls of P and Q Results To succeed in designing a new algorithm and find that the time complexity of this algorithm is O(n+m) times of decisi on whether two segments intersect or not, in which n, m are the numbers of vertices of polygons P and Q respectively Conclusion This algorithm is much better than the approach deciding one by one whether each edge of P intersects the edges of Q
出处
《北京理工大学学报》
EI
CAS
CSCD
1998年第1期87-91,共5页
Transactions of Beijing Institute of Technology
关键词
多边形
并
得和杂度
计算几何
算法
simple polygon
union of two polygons
complexity
