首页 | 官方网站   微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 140 毫秒
1.
文中提出一种快速判别简单多边形方向与顶点凸凹性的新算法。通过对简单多边形的每一个顶点引入伴随坐标系,将平面划分为与该顶点相关的四个部分;由此可以得到简单多边形中与该顶点相邻的两个顶点在该平面划分中的16种配置关系:不同的配置关系对判别该顶点的凸凹性所需要的计算量是不同的,从而使大量凸凹性判别工作由“比较”运算来完成,只有在必要时才运用“乘/除法”运算;算法利用“假设一检测”方法,通过获取诸顶点中横坐标值最大的顶点,最终确定简单多边形的方向和诸顶点的凸凹性。文中算法的时间复杂度为O(n)。一般情况下,计算一个顶点的凸凹性所使用的乘法次数平均不超过一次,最坏时也仅为一次。  相似文献   

2.
基于凹凸顶点判定的简单多边形Delaunay三角剖分   总被引:45,自引:1,他引:44  
提出一种基于凹凸顶点判定的简单多边形Delaunay三角剖分算法。该算法首先求出简单多边形的凹凸顶点,然后,逐次割去一个权值最大的三角形构造三角形网络,修改多边形顶点链表,并重新计算受影响的顶点的凹凸性。重复这个过程,直到边界顶点链表空为止。  相似文献   

3.
平面点集凸壳的快速算法   总被引:3,自引:0,他引:3       下载免费PDF全文
提出一种计算平面点集凸壳的快速算法。利用极值点划分出四个矩形,它们包含了所有凸壳顶点,通过对矩形中的点进行扫描,排除明显不是凸壳顶点的点,剩余的点构成一个简单多边形。再利用极点顺序法判断多边形顶点的凹凸性并删除所出现的凹顶点,最终得到一个凸多边形即为点集的凸壳。整个算法简洁明了,避免了乘法运算(除最坏情况外),从而节省计算时间。  相似文献   

4.
针对以往判断简单多边形顶点凸凹性算法计算量偏大的问题,在基于象限的简单多边形顶点凸凹性判断算法的基础上提出一种改进的识别算法。将直角坐标平面平均划分为八个区域,利用角两边在八个区域内的特性来快速判断角度的范围;将顶点凸凹性判断转化为顶点内角范围的判断,并将其引入多边形方向的判别,从而以简单的判断和逻辑运算代替耗时的乘法运算,加快了判断速度。实验分析表明,改进后的算法能有效地避免较为耗时的乘法运算,提高判断效率。  相似文献   

5.
基于凹凸顶点判定的简单多边形的三角剖分   总被引:20,自引:1,他引:19  
本文提出了一种基于凹凸顶点判定的简单多边形的三角剖分,该算法首先计算简单多边形顶点的凹凸性,然后用环形追踪算法到一个三角剖分,最后通过局部变换得到一个较好的三角剖分。  相似文献   

6.
多边形的内外点判别是图形学的一个基础算法,为了更大限度地降低其算法复杂度和运算量,提出一种基于斜率的点与多边形位置关系的快速判别法。该方法只需计算该点到多边形各顶点的斜率,然后与多边形各顶点的邻边的斜率进行比较,即可对多边形的内外点快速做出判别。该算法无需复杂的点乘、叉乘、求交、三角函数等运算,在判别过程中仅需平均2n次减法运算和n/2次的除法运算,以及一些比较运算,即可对简单n多边形的内外点做出判别。经测试,该算法快速有效。  相似文献   

7.
林政宽  赵源  樊建席  程宝雷 《计算机科学》2017,44(6):94-96, 107
在计算机互连网络中,完全独立生成树在信息的可靠传输、并行传输、安全分发等方面具有重要的作用。假设图G中存在n棵生成树T1,T2,…,Tn,若对于图G中任意两个顶点u和v,满足u和v之间的路径在这n棵树中都是顶点不相交的,则称这n棵树为完全独立生成树(CISTs)。在2015年,Chang等人证明了对于包含n(n≥6)个顶点的任意图G,如果图G的最小顶点度数至少为n-2,那么,G中存在至少 n/3 棵CISTs[1]。在Chang等人的基础上,文中继续深入研究了图G中顶点度数和CISTs的棵数之间的关系。对于包含n(n≥5) 个顶点的任意图G,假设图G的最小顶点度数至少为n-2,得出度数为n-2的顶点的个数、度数为n-1的顶点的个数与图G中CISTs的棵数之间关系的推导等式,并证明了其正确性,从而改进了文献[1]中的结果。  相似文献   

8.
周吉  张松林 《计算机应用》2003,23(Z2):99-99
给出了一种确定任意多边形顶点凸、凹性的简便算法.该算法只需要n+4次乘除法,平均3n次加减法及4n+3次比较即可完成(n是多边形顶点的个数).  相似文献   

9.
文中将具有2n个顶点的M(o)bius立方体的拓扑结构加以改变,得到了包含任意个顶点的互连网络--超级M(o)bius立方体,并证明它保持了M(o)bius立方体的高连通度、对数级的直径和顶点度数等优良性质,并且当顶点个数N=2n+2n-1 时,0-型超级M(o)bius立方体是一个(n+1)-正则图;更进一步地,由于它包含任意个顶点,所以其升级只需增加任意个顶点,从而克服了M(o)bius立方体的升级必须成倍增加其顶点个数的缺点.  相似文献   

10.
圆弧和直线段组成的封闭曲线凸凹性快速判定   总被引:1,自引:0,他引:1  
首先通过构造一中介凸多边形求出封闭曲线的方向,然后根据封闭曲线方向确定顶点及圆弧的凸凹性,进而确定封闭曲线的凸凹性.文中算法快速稳定,其时间复杂度为O(n),计算量最多为15n 33k 25次判断、12n-6k 14次乘除法、10n 16k 21次加减法、2次求正余弦和k次开方运算,其中n为封闭曲线顶点和圆弧圆心的个数、k为圆弧个数.  相似文献   

11.
简单多边形凸凹性自识别算法   总被引:14,自引:2,他引:14  
提出一种基于极值顶点构造凸多边形和矢量叉乘的自动识别简单多边形方向性,凸凹性的算法,该算法在稳定性方面采取了有效的措施,避免因极值顶点的奇异性而导致多边形方向性,凸凹性的错误识别,具有良好的可靠性和稳定性,算法原理直观简单,效率高,时间复杂度为O(n).  相似文献   

12.
基于拓扑映射的多边形顶点凸凹判别算法   总被引:10,自引:2,他引:10  
通过拓扑映射,多边形顶点凸凹判别可以转化为映射点在射影直线上的位置关系问题。首先求得相邻边在两条射影直线上的映射点,基于一般映射点归纳得到顶点凸凹判别的4条规则,然后将两条射影直线上的映射点归结为一条射影直线,从而得到更有效的映射点求取方法,顶点凸凹判别规则统一为两条;进一步考虑非固有映射点的求取方法,提高了算法的稳定性,实验结果表明,该算法实现简单、速度快、稳定可靠。  相似文献   

13.
多边形链求交的改进算法   总被引:5,自引:2,他引:5  
多边形链求交是CAD&CG及相关领域研究中的一个基本问题 利用多边形链的凸凹性、单调性等特性 ,结合包围盒技术 ,在扫描线算法基础上 ,提出一种多边形链求交的改进算法 该算法特别适用于包含大量直线段且交点数相对于顶点数少得多的多边形链求交的情况  相似文献   

14.
任意多边形顶点凸、凹性判别的简捷算法   总被引:21,自引:0,他引:21  
刘润涛 《软件学报》2002,13(7):1309-1312
给出了一种确定任意多边形顶点凸、凹性的简捷算法.该算法只需要2n+4次乘法,5n+10次加、减法及2n+3次比较即可完成(n是多边形顶点的个数).同时,给出了任意简单多边形走向的充要条件.  相似文献   

15.
一种优化的消失点估计方法及误差分析   总被引:1,自引:0,他引:1  
空间一组平行直线在图像平面上所成的像的交点称为消失点. 消失点可以提供大量的场景三维结构信息. 本文提出一种新的优化的消失点估计方法. 该方法基于随机采样一致算法(Random sample consensus, RANSAC)对图像空间中的线段进行聚类, 通过最小化Sampson误差获得消失点的极大似然估计(Maximum likelihood estimation, MLE). 该方法不需要预知摄像机参数及直线的三维位置信息. 为了对该算法进行定量评估, 构造了基于反向传播的消失点误差传递模型. 实验结果验证了本文提出算法的有效性.  相似文献   

16.
汤慧  周明全  耿国华 《计算机应用》2019,39(11):3355-3360
针对低覆盖点云配准的时间复杂度高、收敛速度缓慢以及对应点匹配易错等问题,提出一种基于区域分割的点云配准算法。首先,利用体积积分不变量计算点云上点的凹凸性,并提取凹凸特征点集;然后,采用基于混合流形谱聚类的分割算法对特征点集进行区域分割,并采用基于奇异值分解(SVD)的迭代最近点(ICP)算法对区域进行配准,从而实现点云的精确配准。实验结果表明,所提算法通过区域分割可以大幅提高点云区域的覆盖率,并且无需迭代即可计算刚体变换的最佳旋转矩阵,其配准精度比已有算法提高了10%以上,配准时间降低了20%以上。因此,所提算法是一种精度高、速度快的低覆盖点云配准算法。  相似文献   

17.
为了减少计算机分析乳腺肿瘤影像的数据量,提高肿瘤病灶计算机辅助探测和辅助诊断的精确度,降低假阳性和假阴性,乳腺肿瘤区域的提取是至关重要的。基于乳腺恶性肿瘤和有些良性乳腺瘤(如纤维性瘤)的边缘模糊不清和凹凸多变的特性,传统的边缘提取算子和阈值法分割乳腺肿瘤区域很困难,该文提出应用基于可变形模型的梯度矢量流的方法提取乳腺X光片肿瘤区域,用基于亥姆霍兹最小能量损耗原理的一种新的外部能量代替传统方法的外部能量,从而解决了传统方法的可变形轮廓线不能收敛于目标边缘凹陷处的问题,并取得了良好的效果,为进行乳腺X光片肿瘤区域的形状特征提取提供了前提。  相似文献   

18.
Mesh Segmentation via Spectral Embedding and Contour Analysis   总被引:7,自引:1,他引:7  
We propose a mesh segmentation algorithm via recursive bisection where at each step, a sub-mesh embedded in 3D is first spectrally projected into the plane and then a contour is extracted from the planar embedding. We rely on two operators to compute the projection: the well-known graph Laplacian and a geometric operator designed to emphasize concavity. The two embeddings reveal distinctive shape semantics of the 3D model and complement each other in capturing the structural or geometrical aspect of a segmentation. Transforming the shape analysis problem to the 2D domain also facilitates our segmentability analysis and sampling tasks. We propose a novel measure of the segmentability of a shape, which is used as the stopping criterionfor our segmentation. The measure is derived from simple area- and perimeter-based convexity measures. We achieve invariance to shape bending through multi-dimensional scaling (MDS) based on the notion of inner distance. We also utilize inner distances to develop a novel sampling scheme to extract two samples along a contour which correspond to two vertices residing on different parts of the sub-mesh. The two samples are used to derive a spectral linear ordering of the mesh faces. We obtain a final cut via a linear search over the face sequence based on part salience, where a choice of weights for different factors of part salience is guided by the result from segmentability analysis.  相似文献   

19.
In this paper, we extend some results in discrete geometry based on the 8-neighborhood to that of the 16-neighborhood, which now includes the chessboard and the knight moves. We first present some analogies between an 8-digital arc and a 16-digital arc as represented by shortest paths on the grid. We present a transformation which uniquely maps a 16-digital arc onto an 8-digital arc (and vice versa). The grid-intersect-quantization (GIQ) of real arcs is defined with the 16-neighborhood. This enables us to define a 16-digital straight segment. We then present two new distance functions which satisfy the metric properties and describe the extended neighborhood space. Based on these functions, we present some new results regarding discrete convexity and 16-digital straightness. In particular, we demonstrate the convexity of a 16-digital straight segment. Moreover, we define a new property for characterizing a digital straight segment in the 16-neighborhood space. In comparison to the 8-neighborhood space, the proposed 16-neighborhood coding scheme offers a more compact representation without any loss of information.  相似文献   

20.
提出了一种基于平面隐函数的实体切割思想和区域自动识别技术的地质体剖面图生成方法。其主要步骤包括:采用平面隐函数实现平面和地质实体的求交运算,生成离散的交线;采用基于KD树的空间索引方法,确定交线的邻接关系,生成地质体轮廓线;封闭的轮廓线将平面划分为多个复杂的区域(内含孔、岛),采用图论的多叉树形式化表达区域存储和组织;最后对多叉树表示的区域进行矢量图案的填充。实验结果表明,该算法有较好的计算效率,是一种比较实用的地质体剖切方法。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号