确定两个任意多边形的并的算法

被引：2

作者：

周培德

王文明

机构：

[1] 北京理工大学计算机科学与工程系

来源：

北京理工大学学报 | 1998年 / 01期

关键词：

简单多边形；两个多边形的并；复杂度;

D O I：

10.15918/j.tbit1001-0645.1998.01.017

中图分类号：

TP301, [];

学科分类号：

摘要：

目的设计并分析求两个任意多边形的并的一种新算法．方法利用分治思想设计算法，即根据Ｐ，Ｑ凸壳及Ｐ与Ｑ的凸壳的不同位置关系，分６种情况分别求并Ｐ∪Ｑ的边界．结果成功设计出新的算法并分析出该算法的时间复杂性为Ｏ（ｎ＋ｍ）次判断两条线段是否相交，其中ｎ，ｍ分别是多边形Ｐ与Ｑ的顶点数．结论该算法优于逐次判断Ｐ的每条边是否与Ｑ的边相交的方法．

引用

页码：3 / 5

页数：5