期刊文献+
共找到21篇文章
< 1 2 >
每页显示 20 50 100
基于顶点可见性的凹多边形快速凸分解算法 被引量:20
1
作者 金文华 饶上荣 +1 位作者 唐卫清 刘慎权 《计算机研究与发展》 EI CSCD 北大核心 1999年第12期1455-1460,共6页
凹多边形的凸分解问题是计算几何的基本问题之一,在许多领域均有应用.现有算法大多为全局剖分算法,而局部剖分算法研究的很少.全局方法由于耗时太多,而不能满足所有工程应用的需要.目前局部剖分算法中最经典的是Rogers算法... 凹多边形的凸分解问题是计算几何的基本问题之一,在许多领域均有应用.现有算法大多为全局剖分算法,而局部剖分算法研究的很少.全局方法由于耗时太多,而不能满足所有工程应用的需要.目前局部剖分算法中最经典的是Rogers算法,但由于其存在许多缺陷而在实际应用中受到限制.文中在多边形顶点可见性基础上,提出了新的局部剖分方法.利用凹点的局部几何特性,通过引入权函数从凹点的可见点串中选取适当的点引剖分线,或者利用凹点夹角平分线与某两可见顶点所在边的交点引剖分线进行多边形分解.文中算法已应用于工厂设计软件PDSOFTPiping 中,实践证明效果很好. 展开更多
关键词 顶点可见性 计算几何 算法 凹多边形 凸分解
下载PDF
基于有序简单多边形的平面点集凸包快速求取算法 被引量:50
2
作者 金文华 何涛 +2 位作者 刘晓平 唐卫清 唐荣锡 《计算机学报》 EI CSCD 北大核心 1998年第6期533-539,共7页
凸包问题是计算几何的基本问题之一,在许多领域均有应用.传统平面点集凸包算法和简单多边形凸包算法平行发展,互不相干.本文将改进的简单多边形凸包算法应用于平面点集凸包问题中,提出了新的点集凸包算法.该算法首先淘汰掉明显不... 凸包问题是计算几何的基本问题之一,在许多领域均有应用.传统平面点集凸包算法和简单多边形凸包算法平行发展,互不相干.本文将改进的简单多边形凸包算法应用于平面点集凸包问题中,提出了新的点集凸包算法.该算法首先淘汰掉明显不位于凸包上的点,然后对剩余点集排序,再将点集按照一定顺序串联成有序简单多边形,最后利用前瞻回溯方法搜索多边形凸包,从而得到点集的凸包.本文算法不仅达到了O(nlogn)的理论时间复杂度下限,而且算法极其简单,易于实现.本文方法已应用于工厂设计软件PDSOFT中,实践证明效果很好. 展开更多
关键词 凸包 平面点集 简单多边形 算法 计算几何
下载PDF
简单多边形可见点问题的快速求解算法 被引量:12
3
作者 金文华 何涛 +2 位作者 唐卫清 唐荣锡 刘慎权 《计算机学报》 EI CSCD 北大核心 1999年第3期275-282,共8页
简单多边形可见点问题是计算几何的基本问题之一,在许多领域均有应用.本文在参考现有算法(尤其是Lee算法)的基础上,提出了改进的方法.文中方法先用射线法求取第一个可见点,然后利用文中设定的规则搜索后续可见点.本文算法继... 简单多边形可见点问题是计算几何的基本问题之一,在许多领域均有应用.本文在参考现有算法(尤其是Lee算法)的基础上,提出了改进的方法.文中方法先用射线法求取第一个可见点,然后利用文中设定的规则搜索后续可见点.本文算法继承和发展了Lee算法的几何直观性,且也只采用一个堆栈,但无须耗时的坐标变换和三角函数运算,而且彻底修改了Lee算法的错误,避免了Lee算法中的不足之处,并且算法的时间和空间复杂度仍为O(n).本文算法已应用于工厂设计配管软件PDSOFTforPiping中,实践证明效果很好. 展开更多
关键词 简单多边形 计算几何 可见点问题 计算机图形学
下载PDF
多边形的简单性、方向及内外点的判别算法 被引量:42
4
作者 王志强 肖立瑾 洪嘉振 《计算机学报》 EI CSCD 北大核心 1998年第2期183-187,共5页
本文用三维空间来解决二维平面问题,从而得出了一个简单的点与有向线段之间关系的判别式,并在此基础上根据凸凹点的性质及有向多边形的性质提出了不用解任何方程组也不用计算三角函数的判定平面多边形的简单性、方向及内外点的简单、... 本文用三维空间来解决二维平面问题,从而得出了一个简单的点与有向线段之间关系的判别式,并在此基础上根据凸凹点的性质及有向多边形的性质提出了不用解任何方程组也不用计算三角函数的判定平面多边形的简单性、方向及内外点的简单、强健而高效的算法. 展开更多
关键词 计算几何 多边形 算法
下载PDF
一个加权剖分简单多边形为凸多边形的算法 被引量:14
5
作者 王钲旋 李文辉 庞云阶 《计算机学报》 EI CSCD 北大核心 1998年第3期229-233,共5页
本文提出可以为简单多边形中的可视点对建立一种权函数.这种权函数容易计算,可以反映在点对间加入剖分线时获得剖分在形态质量方面的性质,因此可以用来引导剖分.描述了一个利用这种权函数加权剖分简单多边形为凸多边形的算法实现步... 本文提出可以为简单多边形中的可视点对建立一种权函数.这种权函数容易计算,可以反映在点对间加入剖分线时获得剖分在形态质量方面的性质,因此可以用来引导剖分.描述了一个利用这种权函数加权剖分简单多边形为凸多边形的算法实现步骤,讨论了所建立算法的性质.结果表明算法既能够使剖分得到凸多边形的数目较少,又能够使得到的剖分有较好的形态质量,因此有很好的实用性. 展开更多
关键词 权函数 简单多边形 凸多边形 计算几何学 算法
下载PDF
判断简单多边形的核是否为空的一个快速算法 被引量:8
6
作者 王钲旋 徐长青 庞云阶 《计算机辅助设计与图形学学报》 EI CSCD 北大核心 2000年第9期656-659,共4页
简单多边形的核是位于多边形内部的一个点集 ,从其中任意一点可见多边形的全部边界 .文中考查了简单多边形的核在构成方面的性质 ,结合已有结果 ,提出了一个算法 .该算法能快速地判断简单多边形是否有核 ,有核时可以方便地求出核中一个... 简单多边形的核是位于多边形内部的一个点集 ,从其中任意一点可见多边形的全部边界 .文中考查了简单多边形的核在构成方面的性质 ,结合已有结果 ,提出了一个算法 .该算法能快速地判断简单多边形是否有核 ,有核时可以方便地求出核中一个顶点 .对算法进行简单扩展 ,可以求得核中一边及完整的核 .给出的算法容易理解 ,便于实现 。 展开更多
关键词 简单多边形 算法 计算几何
下载PDF
自适应扫描线的简单多边形核填充算法 被引量:9
7
作者 陈炳发 廖文和 《南京航空航天大学学报》 EI CAS CSCD 北大核心 2004年第4期477-481,共5页
针对简单多边形核的填充问题 ,提出了一种基于自适应扫描线方法的直接填充简单多边形核的快速算法。该算法避免了核顶点 (边 )的计算 ,利用简单多边形顶点凸凹性和凹顶点极值性 ,自动确定扫描线的最佳移动方向和扫描范围 ,从而快速绘制... 针对简单多边形核的填充问题 ,提出了一种基于自适应扫描线方法的直接填充简单多边形核的快速算法。该算法避免了核顶点 (边 )的计算 ,利用简单多边形顶点凸凹性和凹顶点极值性 ,自动确定扫描线的最佳移动方向和扫描范围 ,从而快速绘制出简单多边形的核 ,使较复杂的二维线段求交点简化为一维直线的填充问题 ,并同时获得核轮廓 ,降低了计算和填充核的复杂性 ,效率明显提高 。 展开更多
关键词 自适应扫描线 多边形核 填充算法 计算几何 计算机图形学
下载PDF
一种平面简单多边形核的求解算法 被引量:4
8
作者 柳伟 何援军 李震霄 《中国图象图形学报》 CSCD 北大核心 2007年第6期1098-1102,共5页
平面简单多边形的核是该多边形内部的一个点集,该点集中任意一点与多边形边界上一点的连线都处于这个多边形内部。可见核的这一性质在摄像机定位等问题上得到了应用,本文提出了一种简单多边形核求解的新方法,该方法不仅可以判断核的存在... 平面简单多边形的核是该多边形内部的一个点集,该点集中任意一点与多边形边界上一点的连线都处于这个多边形内部。可见核的这一性质在摄像机定位等问题上得到了应用,本文提出了一种简单多边形核求解的新方法,该方法不仅可以判断核的存在性,而且可以得到核多边形顶点序列。给出的算法容易理解,便于实现,可以广泛地应用于此类问题的求解。 展开更多
关键词 简单多边形 计算几何
下载PDF
监视器覆盖多边形新算法 被引量:2
9
作者 于存光 刘润涛 陈相琳 《哈尔滨理工大学学报》 CAS 2007年第1期43-46,共4页
考察了简单多边形的核在构成方面的性质,结合已有结果,提出一个新算法.该算法先搜索当前凹点,并由该凹点所在边引射线,将多边形所在平面分为A、B、C三个区域.利用凹点的B域将多边形分成若干有核部分,在每一部分的核区域放置一个监视器,... 考察了简单多边形的核在构成方面的性质,结合已有结果,提出一个新算法.该算法先搜索当前凹点,并由该凹点所在边引射线,将多边形所在平面分为A、B、C三个区域.利用凹点的B域将多边形分成若干有核部分,在每一部分的核区域放置一个监视器,从而实现监视器覆盖多边形.本算法时间复杂性为O(nm2). 展开更多
关键词 计算几何 简单多边形 多边形核 监视器 星形分解
下载PDF
判定点是否在多边形内部的算法 被引量:16
10
作者 周培德 《北京理工大学学报》 EI CAS CSCD 1995年第4期437-440,共4页
提出判定点是否在多边形内部的一种算法,其方法是判定射线与多边形边的交点数目以及必要时移动该点的位置,再判定交点的数目.该算法的时间复杂性为O(n)次四则运算和O(n)次比较,其中n为多边形的顶点数.
关键词 多边形 计算几何 简单多边形 算法
下载PDF
优化TSP算法的完善及推广 被引量:2
11
作者 卢朝阳 吴成柯 陆心如 《电子学报》 EI CAS CSCD 北大核心 1994年第1期87-89,94,共4页
本文完善和推广了文献[1]中的简单多边形优化三角剖分算法,提出了一种一般化的算法,它能对卷曲、缠绕复杂的简单多边形进行优化三角剖分,我们还把这种算法推广到简单多边形的优化外三角剖分和任意嵌套封闭多边形的情形。
关键词 多边形分割 优化算法 图形学
下载PDF
基于边向量斜率比较的简单多边形顶点凸凹性快速判别算法 被引量:6
12
作者 庞明勇 卢章平 《工程图学学报》 CSCD 2004年第3期71-77,共7页
对于给定的平面简单多边形顶点序列,判别多边形方向和顶点凸凹性的传统方法为:先计算多边形相邻边向量的叉积或相邻3个顶点所确定三角形的有向面积,再由叉积或有向面积的符号来确定顶点的凸凹性,使得处理一个顶点需要2次以上的乘法运算... 对于给定的平面简单多边形顶点序列,判别多边形方向和顶点凸凹性的传统方法为:先计算多边形相邻边向量的叉积或相邻3个顶点所确定三角形的有向面积,再由叉积或有向面积的符号来确定顶点的凸凹性,使得处理一个顶点需要2次以上的乘法运算。笔者通过边向量斜率的计算和比较,将多边形顶点的凸凹性与边向量的斜率联系起来,并采用“假设-检验”方法,提出了一种快速判别简单多边形方向与顶点凸凹性的新算法,其时间复杂度为)(nO,判别多边形任一顶点凸凹性所需的乘法运算平均不超过1次。该算法原理直观简单,实现容易。实际运行结果表明,该算法速度快捷、运行稳定。 展开更多
关键词 计算机应用 计算几何 凸凹性判别 边向量比较 简单多边形 算法
下载PDF
可重构造网孔机器上简单多边形三角剖分的常数时间算法 被引量:1
13
作者 万颖瑜 陈国良 许胤龙 《计算机学报》 EI CSCD 北大核心 2002年第1期93-99,共7页
简单多边形的三角剖分是计算几何的基本问题之一 ,在计算机图形学、地理信息系统及有限元方法等领域有许多重要的应用 .可重构造网孔机器是近几年出现的一种新的并行计算模型 ,由于其特有的灵活性 ,已经有很多领域的基本问题在这种模型... 简单多边形的三角剖分是计算几何的基本问题之一 ,在计算机图形学、地理信息系统及有限元方法等领域有许多重要的应用 .可重构造网孔机器是近几年出现的一种新的并行计算模型 ,由于其特有的灵活性 ,已经有很多领域的基本问题在这种模型上得到了研究 .该文在这种结构上考虑了简单多边形的三角剖分问题 :提出了一个将简单多边形分解为特殊单调多边形的算法 ,并在规模为 n× n的可重构造网孔机器上实现了常数时间分解单调多边形为特殊单调多边形的并行算法 ,基于这个算法得到了一个 n× n的机器上常数时间三角剖分单调多边形的算法 ;将这些算法稍加推广 ,并使用稍多的处理器 ,得到了一个在规模为 n× n1 +ε(0 <ε<1为常数 )的可重构造网孔机器上三角剖分简单多边形的常数时间算法 .就目前了解到的情况而言 。 展开更多
关键词 三角剖分 简单多边形 单调多边形 并行算法 常数时间算法 可重构造网孔机器 计算机
下载PDF
确定任意简单多边形平移时碰撞部位的扫描算法 被引量:10
14
作者 曲吉林 《计算机学报》 EI CSCD 北大核心 2000年第7期692-698,共7页
设 P和 Q为平面内任意两个互不相交的简单多边形 ,若 P沿方向 d平移时与 Q碰撞 ,采用平面扫描法 ,通过提取多边形的单调链 ,给出了求其碰撞部位的算法 .最坏情况下 ,算法的时间复杂性为 O((m +n) log(m+n) ) ,其中 n和 m分别为多边形 P... 设 P和 Q为平面内任意两个互不相交的简单多边形 ,若 P沿方向 d平移时与 Q碰撞 ,采用平面扫描法 ,通过提取多边形的单调链 ,给出了求其碰撞部位的算法 .最坏情况下 ,算法的时间复杂性为 O((m +n) log(m+n) ) ,其中 n和 m分别为多边形 P与 Q的边数 ,与现有的算法相比 ,降低了时间复杂性 . 展开更多
关键词 计算几何 简单多边形 碰撞部位 算法
下载PDF
简单多边形凸单元剖分算法的设计及实现 被引量:1
15
作者 高翔 高中山 《燕山大学学报》 CAS 2005年第6期506-510,共5页
简单多边形凸单元剖分是计算几何的基本问题之一,剖分算法在许多领域均有较广泛的应用。本文给出了一个利用剖分线的特征性质,剖分简单多边形为凸多边形的剖分算法。算法消除了剖分后存在部分凸多边形可以合并的现象,既能使剖分得到的... 简单多边形凸单元剖分是计算几何的基本问题之一,剖分算法在许多领域均有较广泛的应用。本文给出了一个利用剖分线的特征性质,剖分简单多边形为凸多边形的剖分算法。算法消除了剖分后存在部分凸多边形可以合并的现象,既能使剖分得到的凸多边形数目较少,能使得到的剖分有较好的形态质量。实例表明算法具有较高的运行效率,因此有很好的实用性。 展开更多
关键词 简单多边形 凸多边形 计算几何
下载PDF
平面内任意一组简单多边形的可见性 被引量:1
16
作者 曲吉林 杨洪万 《山东师范大学学报(自然科学版)》 CAS 2000年第2期133-137,共5页
给定平面内任意一组简单多边形 ,讨论其相对于平面内某点的可见性 .通过对多边形可见边的分析 ,利用平面扫描技术 ,给出了求其可见边的算法 .
关键词 计算几何 简单多边形 可见性 算法 计算机图形学
下载PDF
改进的加权剖分简单多边形为凸多边形的算法 被引量:3
17
作者 张玉连 《燕山大学学报》 CAS 2001年第1期76-79,共4页
对加权剖分简单多边形为凸多边形算法的权函数做了改进,新的权函数容易计算,可以反映在点对间加入剖分线时获得剖分在形态质量方面的性质,因此可以用来引导剖分。给出了一个利用这种权函数加权剖分简单多边形为凸多边形的算法实现步... 对加权剖分简单多边形为凸多边形算法的权函数做了改进,新的权函数容易计算,可以反映在点对间加入剖分线时获得剖分在形态质量方面的性质,因此可以用来引导剖分。给出了一个利用这种权函数加权剖分简单多边形为凸多边形的算法实现步骤,讨论了所建立算法的性质。结果表明算法既能够使剖分得到的凸多边形数目较少,又能够使得到的剖分具有较好的形态质量,因此有很好的实用性。 展开更多
关键词 权函数 剖分 简单多边形 凸多边形 计算几何学 算法
下载PDF
二面体群作用下简单多边形的分类 被引量:1
18
作者 徐嘉 《计算机辅助设计与图形学学报》 EI CSCD 北大核心 2012年第7期896-900,共5页
针对简单多边形的分类问题,将对称情况看成是相同类别进行分类来简化分类数,提出一种分类方法.首先分析简单多边形顶点的凹凸性,根据简单多边形顶点处凸点和凹点的分布情况,定义了简单多边形的标记矩阵;然后利用标记矩阵将简单多边形的... 针对简单多边形的分类问题,将对称情况看成是相同类别进行分类来简化分类数,提出一种分类方法.首先分析简单多边形顶点的凹凸性,根据简单多边形顶点处凸点和凹点的分布情况,定义了简单多边形的标记矩阵;然后利用标记矩阵将简单多边形的分类问题归结为二面体群作用在状态集(全体标记矩阵组成的集合)上的轨道划分问题;最后利用熟知的Pólya计数定理求解轨道的个数,并给出了新的分类公式.实验结果表明,当简单多边形边数为6时,采用文中方法的分类数小于原来分类数,并且随着边数的增大,这种差距逐渐变大. 展开更多
关键词 计算几何 简单多边形 凹凸性 标记矩阵 状态集 二面体群
下载PDF
平面内任意简单多边形的旋转可移动性
19
作者 曲吉林 《计算机学报》 EI CSCD 北大核心 2000年第7期685-691,共7页
设 P和 Q为平面内两个互不相交的简单多边形 ,若 P在平面内绕某点旋转 ,文中讨论了其旋转可移动性问题 .通过提取多边形的单调链 ,采用曲线扫描法 ,给出了求其最大可旋转角度及碰撞部位的算法 ,与现有的算法相比 ,降低了时间复杂性 .
关键词 计算几何 简单多边形 旋转 可移动性 算法
下载PDF
判别简单多边形的核为空的快速算法
20
作者 于存光 《价值工程》 2014年第5期191-192,共2页
简单多边形的核是位于多边形内部的一个点集,从其中任意一点可见多边形的全部边界。根据多边形的核只与多边形凹点有关,只对多边形的凹顶点进行处理。当多边形有连续凹点时,利用平行射线法和线性求交法迅速判断多边形是否有核,在多边形... 简单多边形的核是位于多边形内部的一个点集,从其中任意一点可见多边形的全部边界。根据多边形的核只与多边形凹点有关,只对多边形的凹顶点进行处理。当多边形有连续凹点时,利用平行射线法和线性求交法迅速判断多边形是否有核,在多边形有核时可以求多边形核的一个交点的时间复杂度。 展开更多
关键词 计算几何 简单多边形 多边形核 多边形无核
下载PDF
上一页 1 2 下一页 到第
使用帮助 返回顶部