首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到18条相似文献,搜索用时 78 毫秒
1.
基于凹凸顶点判定的简单多边形的三角剖分   总被引:20,自引:1,他引:19  
本文提出了一种基于凹凸顶点判定的简单多边形的三角剖分,该算法首先计算简单多边形顶点的凹凸性,然后用环形追踪算法到一个三角剖分,最后通过局部变换得到一个较好的三角剖分。  相似文献   

2.
在充分挖掘AutoCAD图形中简单多边形自身隐含的垂直与共线关系的基础上,提出一种新的基于直角顶点判定和凹凸顶点判定的简单多边形剖分算法。该算法首先判断出多边形顶点的直角特性和凹凸性,然后根据多边形自身的特点按照一定的先后次序进行剖分,力求把多边形分割成直角梯形、矩形和直角三角形的形式。其中判断辅助线连接次序的优先级是实现剖分算法的关键。程序实现中采用递归算法,对分割后的多边形重新进行判断,直到多边形分割完毕。  相似文献   

3.
基于最小距离简单多边形的Delaunay三角剖分算法   总被引:2,自引:1,他引:1  
简单多边形的Delaunay三角剖分,在计算机图形学及三维建模领域有着广泛的应用.提出了一种时间复杂度为O((n-4)2)的基于三角形顶点距离最小的简单多边形Delaunay三角剖分算法.通过三角形顶点的最小距离,形成简单多边形的初始三角网,而后对初始三角网进行Delaunay剖分,并对算法的时间复杂度进行了分析.通过实例表明,此算法在时间复杂度和三角形形态质量上都得到了很大改进.  相似文献   

4.
基于动态分区的多边形顶点凹凸性判别   总被引:1,自引:0,他引:1       下载免费PDF全文
基于判别顶点对应的边,对平面进行动态分区,形成全正区、全负区和非全正负区,将顶点凹凸性判别转化为后继顶点所在区域位置判别。而全正区、全负区情况只需通过简单判别即可确定顶点的凹凸性,避免乘法运算,其复杂度按概率为(n/4)次乘法(n为多边形顶点数)。试验结果表明,该算法速度快,稳定可靠。  相似文献   

5.
平面多边形交集与并集面积的计算机算法可以利用多边形裁剪算法来实现。本文提出的算法思想是利用Weiler-Atherton多边形裁剪算法中的多边形链表,在遍历链表时遇到交点就改变跟踪方向,这样可以求出并集顶点表,求交集时只要从入点开始跟踪遇到交点再改变跟踪方向;最后,通过交集和并集表求出它们的面积。多边形可以是凸的或凹的、甚至是带孔的。  相似文献   

6.
基于顶点与邻边相关性的多边形填充算法   总被引:3,自引:0,他引:3       下载免费PDF全文
为了加快多边形填充算法的运算速度,在深入挖掘顶点与相邻边关系对填充算法影响的基础上,提出了一种基于顶点与邻边相关性的多边形填充算法。该算法首先归纳了多边形顶点与邻边相关性的5种典型类型,然后依据顶点与邻边的相关性,对原有多边形进行了分割与重新组合,使其完全由简单的三角形和梯形这样的单元区域组成,这样就将复杂的多边形填充问题转化为这些单元区域的填充问题,并由此将扫描线与多边形边求交的乘除计算转化为加减运算。通过实验分析,新算法大大减少了运算的时间和复杂度,从而为多边形填充创造了一种有效的新途径。  相似文献   

7.
简单多边形顶点凸凹性的线性识别   总被引:2,自引:0,他引:2  
本文提出了一种简单多边形顶点的凸凹性识别算法,算法是基于对多边形顶点的遍历,其复杂性为0(n),(n多边形顶点数)可在计算机上快速有效的实现简单多边形顶点凸凹性的自动识别,本算法也可用于解决其它几何复杂性的问题。  相似文献   

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

9.
一种有效的任意多边形裁剪算法   总被引:6,自引:0,他引:6  
介绍了一种基于改进的Weiler算法的任意多边形裁剪算法,该算法通过引入图形部件和合理的数据结构来组织裁剪后的多边形,减少了遍历多边形顶点链表的次数,并有效减少求交点的时间,具有占用存储空间少和处理速度快的特点。经过实例测试,算法对同时处理单个和多个任意多边形裁剪具有良好的稳定性、可靠性和较高的效率。  相似文献   

10.
寻求简单多边形凸壳的线性时间算法   总被引:7,自引:0,他引:7       下载免费PDF全文
本文提出在线性时间内构造简单多边形顶点凸壳的两种算法。第一个算法的基本思想是利用一种技巧对多边形顶点进行筛选,使剩余顶点的角的大小排成递增序,然后用Graham扫描方法删去非凸壳顶点,最后得到多边形凸壳的顶点序列.第二个算法不断删去多边形的凹点及新产生的 凹点,最后得到凸壳顶点序列。这两种算法简单,易于实现,时间复杂性都是O(n)。  相似文献   

11.
平面多边形顶点的凹凸性快速自动识别方法   总被引:1,自引:0,他引:1  
本文介绍了一种通过运用矢量运算方法对平面多边形顶点的凹凸性进行快速自动识别的原理和方法。该方法自动识别准确、可靠性高,已成功地应用于快速成形技术的分层实体制造过程中激光光斑半径的自动实时补偿。  相似文献   

12.
Normal support vector machine (SVM) is not suitable for classification of large data sets because of high training complexity. Convex hull can simplify the SVM training. However, the classification accuracy becomes lower when there exist inseparable points. This paper introduces a novel method for SVM classification, called convex–concave hull SVM (CCH-SVM). After grid processing, the convex hull is used to find extreme points. Then, we use Jarvis march method to determine the concave (non-convex) hull for the inseparable points. Finally, the vertices of the convex–concave hull are applied for SVM training. The proposed CCH-SVM classifier has distinctive advantages on dealing with large data sets. We apply the proposed method on several benchmark problems. Experimental results demonstrate that our approach has good classification accuracy while the training is significantly faster than other SVM classifiers. Compared with the other convex hull SVM methods, the classification accuracy is higher.  相似文献   

13.
圆形窗口上一般多边形的内/外裁剪算法   总被引:2,自引:0,他引:2  
本文详尽地分析了圆形窗口上一般多边形(凹/凸)的内/外裁剪问题,并通过构造顶交表、圆交表、入点表、出点表等给出了一般多边形(凹/凸)的内/外裁剪算法。  相似文献   

14.
基于凸凹信号的网格分割   总被引:2,自引:0,他引:2  
网格分割在网格参数化、纹理atlas图等几何处理问题中有着重要的应用,提出一种基于顶点或面凸凹信号的简单高效的网格分割算法,基于均匀支撑半径的顶点凸凹信号分析将顶点分为平坦点、凸点、凹点和特征点,先从平坦点进行平坦区域扩展,再从剩下的凸凹点出发进行凸凹区域扩展,最后根据顶点和边界边的光滑度进行区域竞争扩展;对于未能完全分割的简化程度高的模型,基于面的凸凹信号采用类似的过程进一步完成最后的分割,该算法可以快速地进行网格分割并能较好地保持网格特征,特别适用于CAD模型的分割。  相似文献   

15.
This paper describes a technique to transform a two-dimensional shape into a generalized fuzzy binary relation whose clusters represent the meaningful simple parts of the shape. The fuzzy binary relation is defined on the set of convex and concave boundary points, implying a piecewise linear approximation of the boundary, and describes the dissemblance of two vertices to a common cluster. Next some fuzzy subsets are defined over the points which determine the connection between the clusters.The decomposition method first determines nearly convex regions, which are subgraphs of the total graph, and then selects the greatest nearly convex region which satisfies best the defined fuzzy subsets and relations. Using this procedure on touching chromosomes defining the simple parts to be the separated chromosomes, the decomposition often corresponds well to the decomposition that a human might make.  相似文献   

16.
李运锋  刘修国 《计算机应用》2011,31(12):3353-3356
基于轮廓线拼接算法重构三维模型时,由于拼接对象的复杂性,任何一种拼接方法都不能完全涵盖所有情况。为此,提出一种基于方向包围盒(OBB)投影转换的轮廓线拼接算法:首先判断多边形的顶点凹凸性,对于凹顶点,将其转换到对应的凸包上;然后计算凸包的方向包围盒,旋转平移矩形包围盒,并求包围盒内接椭圆,将每个顶点都按比例投影此椭圆上;基于投影后的点进行轮廓线拼接,寻找相邻轮廓线顶点之间的对应关系;最后还原实际坐标,进行原始模型的三维重构。  相似文献   

17.
反求标准型有理二次Bezier曲线的参数与内权因子   总被引:3,自引:0,他引:3  
给定不共线的三个控制顶点和位于这些项点的凸包内在二次曲线上的一点,可以决定一条标准型有理二次Bezier曲线。本文提供了一些简单有效的方法,反求曲线上该点的参数和内权因子,避免了数值计算的不稳定性。  相似文献   

18.
Determining the minimum distance between convex objects is a problem that has been solved using many different approaches. On the other hand, computing the minimum distance between combinations of convex and concave objects is known to be a more complicated problem. Most methods propose to partition the concave object into convex subobjects and then solve the convex problem between all possible subobject combinations. This can add a large computational expense to the solution of the minimum distance problem. In this paper, an optimization-based approach is used to solve the concave problem without the need for partitioning concave objects into convex pieces. Since the optimization problem is no longer unimodal (i.e., has more than one local minimum point), global optimization techniques are used. Simulated Annealing (SA) and Genetic Algorithms (GAs) are used to solve the concave minimum distance problem. In order to reduce the computational expense, it is proposed to replace the objects' geometry by a set of points on the surface of each body. This reduces the problem to an unconstrained combinatorial optimization problem, where the combination of points (one on the surface of each body) that minimizes the distance will be the solution. Additionally, if the surface points are set as the nodes of a surface mesh, it is possible to accelerate the convergence of the global optimization algorithm by using a hill-climbing local optimization algorithm. Some examples using these novel approaches are presented.  相似文献   

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

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