判断简单多边形的核是否为空的一个快速算法 被引量：8

1

作者 王钲旋 徐长青 庞云阶 《计算机辅助设计与图形学学报》 EI CSCD 北大核心 2000年第9期656-659,共4页

简单多边形的核是位于多边形内部的一个点集 ,从其中任意一点可见多边形的全部边界 .文中考查了简单多边形的核在构成方面的性质 ,结合已有结果 ,提出了一个算法 .该算法能快速地判断简单多边形是否有核 ,有核时可以方便地求出核中一个... 简单多边形的核是位于多边形内部的一个点集 ,从其中任意一点可见多边形的全部边界 .文中考查了简单多边形的核在构成方面的性质 ,结合已有结果 ,提出了一个算法 .该算法能快速地判断简单多边形是否有核 ,有核时可以方便地求出核中一个顶点 .对算法进行简单扩展 ,可以求得核中一边及完整的核 .给出的算法容易理解 ,便于实现 。 展开更多

关键词 核 简单多边形 算法 计算几何

在线阅读 下载PDF 职称材料

一种多边形交、并、差运算的有效算法 被引量：10

2

作者 于雷易 边馥苓 万丰 《武汉大学学报（信息科学版）》 EI CSCD 北大核心 2003年第5期615-618,共4页

以周培德的Z5 4算法为参考 ,提出了一种简单多边形交、并、差运算算法———IBO算法。该算法能够处理二维现实世界中的各种情况 。

关键词 GIS 简单多边形 扫描线算法 空间关系 IBO算法 时间复杂度

在线阅读 下载PDF 职称材料

连接不相交线段成简单多边形(链)的算法及其实现 被引量：5

3

作者 周培德 王树武 李斌 《计算机辅助设计与图形学学报》 EI CSCD 北大核心 2002年第6期522-525,共4页

提出一个如何连接平面上 n条线段成一简单多边形或者简单多边形链的实际问题 ,并证明了连接平面上线段集 S成一简单多边形链的一个充分条件—— S中有一条线段连接凸壳 CH(S)中不相邻顶点 .提出了连接平面上线段集 S成一简单多边形或者... 提出一个如何连接平面上 n条线段成一简单多边形或者简单多边形链的实际问题 ,并证明了连接平面上线段集 S成一简单多边形链的一个充分条件—— S中有一条线段连接凸壳 CH(S)中不相邻顶点 .提出了连接平面上线段集 S成一简单多边形或者简单多边形链的算法 ,其基本思想是首先逐层计算线段集 S的凸壳 ,并将这些凸壳改变为简单多边形 ;然后计算各多边形之间的交点 ,进而删去这些交点 ;最后合并若干个简单多边形为一个简单多边形 .当 S中线段数目 n较大时 ,用分治思想设计分治算法 ,较好地求解了这个问题 . 展开更多

关键词 线段集 凸壳 简单多边形 简单多边形链 算法 复杂性 计算机

在线阅读 下载PDF 职称材料

寻求多边形链顶点凸壳的算法 被引量：8

4

作者 周培德 刘建 王立权 《北京理工大学学报》 EI CAS CSCD 北大核心 2003年第1期75-77,共3页

提出一种计算简单多边形链顶点凸壳的算法 ,基本思想是分段计算 ,在每段的计算中 ,先分 4种不同情况计算出边链 L1 ,然后利用一种技巧将 L1 上的部分顶点排列成顶点角递增序列 ,构成边链 L2 ,最后对 L2 进行倒查 ,删去非凸壳顶点 ,剩下... 提出一种计算简单多边形链顶点凸壳的算法 ,基本思想是分段计算 ,在每段的计算中 ,先分 4种不同情况计算出边链 L1 ,然后利用一种技巧将 L1 上的部分顶点排列成顶点角递增序列 ,构成边链 L2 ,最后对 L2 进行倒查 ,删去非凸壳顶点 ,剩下的点即凸壳顶点 .该算法不仅易于实现 ,而且其时间复杂性是线性的 . 展开更多

关键词 顶点 凸壳 简单多边形链 算法设计 复杂复杂性 计算几何 顶点角递增序列

在线阅读 下载PDF 职称材料

简单多边形分解成凸多边形差组合的算法 被引量：7

5

作者 汪嘉业 汪卫 《计算机辅助设计与图形学学报》 EI CSCD 1992年第2期22-29,共8页

本文说明一种把简单多边形分斛成凸多边形的差形式的组合的算法。该算法在求一简单多边形凸包的同时求出凸包和原多边形的差(把差称为内多边形),再对内多边形递归地作同样计算便可得到最终结果。最后证明了运算法的时间复杂性为O(N^2),... 本文说明一种把简单多边形分斛成凸多边形的差形式的组合的算法。该算法在求一简单多边形凸包的同时求出凸包和原多边形的差(把差称为内多边形),再对内多边形递归地作同样计算便可得到最终结果。最后证明了运算法的时间复杂性为O(N^2),其中N为原多边形的边数。 展开更多

关键词 分解 算法 凸多边形 差组合 多边形

在线阅读 下载PDF 职称材料

一种平面简单多边形核的求解算法 被引量：4

6

作者 柳伟 何援军 李震霄 《中国图象图形学报》 CSCD 北大核心 2007年第6期1098-1102,共5页

平面简单多边形的核是该多边形内部的一个点集,该点集中任意一点与多边形边界上一点的连线都处于这个多边形内部。可见核的这一性质在摄像机定位等问题上得到了应用,本文提出了一种简单多边形核求解的新方法,该方法不仅可以判断核的存在... 平面简单多边形的核是该多边形内部的一个点集,该点集中任意一点与多边形边界上一点的连线都处于这个多边形内部。可见核的这一性质在摄像机定位等问题上得到了应用,本文提出了一种简单多边形核求解的新方法,该方法不仅可以判断核的存在性,而且可以得到核多边形顶点序列。给出的算法容易理解,便于实现,可以广泛地应用于此类问题的求解。 展开更多

关键词 简单多边形 核 计算几何

在线阅读 下载PDF 职称材料

监视器覆盖多边形新算法 被引量：2

7

作者 于存光 刘润涛 陈相琳 《哈尔滨理工大学学报》 CAS 2007年第1期43-46,共4页

考察了简单多边形的核在构成方面的性质,结合已有结果,提出一个新算法.该算法先搜索当前凹点,并由该凹点所在边引射线,将多边形所在平面分为A、B、C三个区域.利用凹点的B域将多边形分成若干有核部分,在每一部分的核区域放置一个监视器,... 考察了简单多边形的核在构成方面的性质,结合已有结果,提出一个新算法.该算法先搜索当前凹点,并由该凹点所在边引射线,将多边形所在平面分为A、B、C三个区域.利用凹点的B域将多边形分成若干有核部分,在每一部分的核区域放置一个监视器,从而实现监视器覆盖多边形.本算法时间复杂性为O(nm2). 展开更多

关键词 计算几何 简单多边形 多边形核 监视器 星形分解

在线阅读 下载PDF 职称材料

确定两个任意多边形的并的算法 被引量：2

8

作者 周培德 王文明 《北京理工大学学报》 EI CAS CSCD 1998年第1期87-91,共5页

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

关键词 多边形 并 得和杂度 计算几何 算法

在线阅读 下载PDF 职称材料

求解简单多边形间包含关系的扫描线算法 被引量：2

9

作者 傅清祥 王晓东 李勇 《计算机辅助设计与图形学学报》 EI CSCD 北大核心 1997年第2期157-163,共7页

对于任意给定的一簇互不相交的简单多边形，本文提出一种旨在确定簇中多边形之间包含关系的扫描线法，并对其正确性和复杂性作出分析。

关键词 多边形 扫描线法 算法 计算机

在线阅读 下载PDF 职称材料

求解简单多边形核的新算法 被引量：1

10

作者 刘光惠 陈传波 吕泽华 《华中科技大学学报（自然科学版）》 EI CAS CSCD 北大核心 2007年第12期1-4,共4页

利用凹顶点间的位置信息,提出一种自动选择凹顶点来裁剪多边形的新求核算法.在选定凹顶点进行裁剪的同时,未选定的凹顶点集被分离成为待继续分离的凹顶点集和待裁剪包含核的凸多边形的凹顶点集.通过逐步对核的存在性进行判定,可较快对... 利用凹顶点间的位置信息,提出一种自动选择凹顶点来裁剪多边形的新求核算法.在选定凹顶点进行裁剪的同时,未选定的凹顶点集被分离成为待继续分离的凹顶点集和待裁剪包含核的凸多边形的凹顶点集.通过逐步对核的存在性进行判定,可较快对多边形的核为空集的情况加以报告.在多边形有核的情况下,裁剪过程不断更新包含核的多边形,快速求解得到包含核的凸多边形,从而可以采用凸多边形的线裁剪算法来加速求核计算.新的求核算法在快速判断出空核和提高求核速度方面都有较大改进. 展开更多

关键词 简单多边形 核 算法 自动选择 裁剪

在线阅读 下载PDF 职称材料

确定任意多边形的核的算法 被引量：7

11

作者 周培德 《工程图学学报》 CSCD 1995年第2期28-30,共3页

本文提出确定任意简单多边形Ｌ的核的算法，该算法的时间复杂性是Ｏ（ｌｎ）次乘法，其中ｎ是多边形的Ｌ的顶点数，ｉ是多边形Ｌ中凹点的数目。

关键词 多边形 任意多边形 算法 核

在线阅读 下载PDF 职称材料

一种简单多边形凸包的新线性算法 被引量：10

12

作者 刘润涛 《工程图学学报》 CSCD 2002年第2期120-126,共7页

给出了一个计算简单多边形凸包的新算法。其搜索策略为:对简单多边形上的点进行分类,排除不可能为凸包上的点,缩小搜索范围,从而降低算法的时间复杂度。该算法具有线性时间复杂度和空间复杂度。同时,具体量化了该算法的复杂度,给出了该... 给出了一个计算简单多边形凸包的新算法。其搜索策略为:对简单多边形上的点进行分类,排除不可能为凸包上的点,缩小搜索范围,从而降低算法的时间复杂度。该算法具有线性时间复杂度和空间复杂度。同时,具体量化了该算法的复杂度,给出了该算法的时间复杂度和空间复杂度的确定的上界,即,时间复杂度为不超过4(n-4)次乘法、6(n-4)次减法和17n-12次比较运算,空间复杂度为不超过2n个存储单元(n是该简单多边形顶点的个数)。 展开更多

关键词 线性算法 简单多边形 凸包 计算几何 时间复杂度 空间复杂度

在线阅读 下载PDF 职称材料

连接不相交线段成简单多边形(链)的算法 被引量：1

13

作者 周培德 《工程图学学报》 CSCD 2002年第1期109-114,共6页

提出一个实际问题,即如何连接平面上n条线段成一简单多边形或者简单多边形链,并证明了连接平面上线段集S成一简单多边形链的一个充分条件:S中有一条线段连接凸壳CH(S)中不相邻顶点。另外还提出了连接平面上线段集S成一简单多边形或者简... 提出一个实际问题,即如何连接平面上n条线段成一简单多边形或者简单多边形链,并证明了连接平面上线段集S成一简单多边形链的一个充分条件:S中有一条线段连接凸壳CH(S)中不相邻顶点。另外还提出了连接平面上线段集S成一简单多边形或者简单多边形链的算法。其基本思想是首先逐层计算线段集S的凸壳,并将这些凸壳改变为简单多边形;然后计算各多边形之间的交点,进而删去这些交点;最后合并若干个简单多边形为一个简单多边形。当S中线段数目n较大时,用分治思想可以设计分治算法,较好地求解了这个问题。利用计算机求解这个问题具有实际应用价值。 展开更多

关键词 线段集 凸壳 简单多边形 简单多边形链 分治算法

在线阅读 下载PDF 职称材料

一种确定平面多边形核的算法

14

作者 赵军 高满屯 王三民 《机械科学与技术》 CSCD 北大核心 2009年第5期601-604,共4页

对于简单多边形的求核问题,提出了一种直观而适应性强的算法。根据多边形的核与其顶点凹凸性的内在联系,只对其中的凹顶点进行处理,节省了计算时间。通过构造两个特殊三角形,并利用耗时很少的极点顺序法确定其方向,根据它们的方向相同与... 对于简单多边形的求核问题,提出了一种直观而适应性强的算法。根据多边形的核与其顶点凹凸性的内在联系,只对其中的凹顶点进行处理,节省了计算时间。通过构造两个特殊三角形,并利用耗时很少的极点顺序法确定其方向,根据它们的方向相同与否,对直线与线段是否相交进行判别,明显降低了算法的时间和空间复杂度。算法不仅能确定多边形核的边界顶点,对多边形无核的情况也能及时做出判断。 展开更多

关键词 简单多边形 核 凹凸顶点 极点

在线阅读 下载PDF 职称材料

一种寻找平面图形中最小封闭线框的方法 被引量：2

15

作者 雷安民 高满屯 张华梅 《科学技术与工程》 2010年第4期1021-1023,共3页

提出确定平面图形中最小封闭线框的算法。该算法巧妙、简练,时间复杂度是O(n)次乘法。

关键词 简单多边形 封闭线框 复杂度

在线阅读 下载PDF 职称材料

简单多边形核求解新算法

16

作者 王洪艳 刘润涛 王三 《计算机工程与应用》 CSCD 北大核心 2010年第17期166-168,共3页

简单多边形的核是位于多边形内部的一个点集,而且这个点集中的任意一点与多边形边界上的任意点的连线都属于这个多边形的内部。核的这一性质在监视器安放等问题上得到了应用。考察了简单多边形的核在构成方面的性质,结合已有的成果,提... 简单多边形的核是位于多边形内部的一个点集,而且这个点集中的任意一点与多边形边界上的任意点的连线都属于这个多边形的内部。核的这一性质在监视器安放等问题上得到了应用。考察了简单多边形的核在构成方面的性质,结合已有的成果,提出了一种求简单多边形核的新算法。该算法可以较快地对多边形的核为空的情况加以报告,而且在有核的情况下快速求解到核多边形的顶点序列。新的求核算法容易理解,而且易于实现,可以广泛地应用于实际问题。 展开更多

关键词 简单多边形 核 计算几何 裁剪

在线阅读 下载PDF 职称材料