共查询到20条相似文献,搜索用时 31 毫秒
1.
王钲旋 《计算机工程与应用》1989,(6)
<正> 在贵刊1988年第5期(总227期)所载《一个快速的多边形凸包求取算法》一文的第三节,给出有一个对点可见多边形的凸包求取算法。所给出的算法(以下简称原算法)有一些不够清楚的地方,看来做些修改是必要的。显然求凸包的点可见多边形的顶点数应大于3,开始考察时应设头二个顶点已取为是凸包上的顶点,故应初始化为i=3,j=2。值得注意的是原算法步z所做的斜率比较 相似文献
2.
3.
求解简单多边形和平面点集凸包的新算法 总被引:3,自引:0,他引:3
沿一定方向遍历凸多边形的边,其内部在边的同一侧。本文依据凸多边形的这一特性,提出求解简单多边形凸包的新算法,进而扩展得到求解平面点集凸包的新算法。新点集凸包算法先找到点集的极值点,得到极值点间的候选点子集,再求得相邻极值点间的有序凸包点列,最后顺序连接极值点间的有序凸包点列,得到凸包。新算法达到目前平面点集凸包问题的渐进最好算法的时间复杂度O(n log h),其中,n为平面点集的点数,h为平面点集凸包的顶点数。相比相同复杂度的凸包算法,新算法简单、易于实现。又由于是顺序求得凸包上的点,新算法还具有更易于实现基于其上的有效空间算法的优点。 相似文献
4.
Graham ScanA求解简单多边形凸包算法简洁高效,但是对于未确定方向的简单多边形,该算法需设定一个方向求解其凸包。提出一种新的算法,该算法通过利用凸包求解的Graham ScanA算法来判断简单多边形的方向。算法取得了较好的实用效果。 相似文献
5.
二维凸包是指包含平面点集的最小简单多边形,广泛应用于GIS.将二维凸包与TSP相结合,提出了基于二维凸包的TSP算法,首先快速凸包算法构造城市点集的凸包,该凸包是经过部分城市点且其余点都在其内部的回路.其次将其余的城市点依次插入回路形成新回路,使新回路的长度增量最小,直至所有的城市点都在回路上.在TSPLIB中的典型实例上的实验结果表明,该算法比简单遗传算法更快得到问题的近似解. 相似文献
6.
简单多边形分解成凸多边形差组合的算法 总被引:4,自引:1,他引:4
本文说明一种把简单多边形分斛成凸多边形的差形式的组合的算法。该算法在求一简单多边形凸包的同时求出凸包和原多边形的差(把差称为内多边形),再对内多边形递归地作同样计算便可得到最终结果。最后证明了运算法的时间复杂性为O(N~2),其中N为原多边形的边数。 相似文献
7.
8.
一种平面点集凸包与三角网格综合生成的算法 总被引:7,自引:0,他引:7
平面点集作为一种觉数学模型,其上常做的运算是求其凸包和三角网格,目前二者的研究是独立进行的,鉴于在很多情形下这两种处理结果均需要,提出了一种综合算法:在对离散点集进行delaunay剖分的过程中,增加对三角形边界的判别、管理功能,记录其中作为点集凸包边界的线段,使得在实现剖分的同时产生出点集的凸包,从而提高了算法效率,且当该算法实现单一的点集剖分或凸包功能或是用于简单多边形的凸包与剖分时效果也很好 相似文献
9.
10.
11.
判定点集是否在多边形内部的算法 总被引:4,自引:0,他引:4
周培德 《计算机研究与发展》1997,34(9):672-674
本文提出了判定n个点的点集S是否落入多边形L内部的算法,该算法的复杂性为:max(O(mn),O(ln log n))比比较和O(ln)次乘法,其中m是L的顶点数,l为S的凸包层数。 相似文献
12.
文中提出了一个基于多边形逼近和凸包球取的人体三围特征计算方法。首先给出了一个具有确定性的高效的多边形逼年算法,运用该算法对人体横截面边界进行特征化处理,再通过特征识别抽取人体三围的特征多边形,最后通过计算凸包的方法获取人体三围特征值。文中提出的方法已运用于一个综合化的服装CAD系统中。 相似文献
13.
14.
确定多边形凸凹顶点的快速算法及其应用 总被引:13,自引:0,他引:13
提出一种确定任意多边形凸凹顶点的快速算法,该算法的时间复杂性为O(n)次乘法和O(n)次比较。还介绍把该算法用于求平面点集的凸包以及对任意的平面多边形进行Delaunay三角剖分。 相似文献
15.
针对点的可见性计算这一计算几何中的基础问题,提出一种支持任意查询点的可见多边形快速计算的基于多边形Voronoi图的点可见性算法.以与Voronoi骨架路径对应的Voronoi通道概念,以及相应的局部最短路径概念为基础,按照深度优先策略对Voronoi图进行遍历,在计算Voronoi骨架路径的同时计算局部最短路径,并基于局部最短路径计算所遍历的多边形边的可见部分.该算法可以处理“带洞”多边形,而且只对多边形进行局部访问;对于“带洞”多边形,由于该算法的数据结构比较简单、剖分空间合理且易于实现,因此仅需O(n)空间和O(nlgn)预处理时间.最后给出了在三维室内虚拟场景设计与漫游系统中的应用实例,结果表明文中算法是实际可行,且运行时间与点的可见多边形的边数和多边形的边数均呈线性关系. 相似文献
16.
平面上简单多边形平移时确定碰撞部位的最优算法 总被引:18,自引:5,他引:18
本文提出一种时间复杂性为O(m+n)的算法,在一个多边形的凸包不和另一个多边形相交的条件下,该算法可确定二个多边形是否相撞,在相撞时可确定全部碰撞部位.本文还证明了确定碰撞部位问题算法的时间复杂性的下界为O(m+n),因而本文提出的算法是最佳的. 相似文献
17.
一种改进的快速三维凸包生成算法及实现 总被引:3,自引:0,他引:3
本文阐述一种快速的三维凸包构造新算法,算法吸收了Quick Hull方法中每次选用凸包的极值点(Extremal-Point)来构造新凸包的思想,在此基础上改进为选用二次极值点的方法来构造新凸包,并结合"冲突图"(Conflict-Graph)来更新凸包外的点和当前凸包的拓扑结构关系,从而取得了快速排除凸包的内部点、缩小问题规模、实现高效构建凸包的效果。本文算法的时间复杂度为O(nlgr),通过实验证明本文算法与QuickHull算法相比平均执行消耗时间减少20%,因此本算法具有理论和实际应用价值。 相似文献
18.
19.
点集模型作为一种新兴的三维几何形体表示形式,近年来备受关注.本文运用点集法向计算与凸包构建等技术,对原始点集模型进行直接可视性计算,并利用可见性计算的结果对点集模型进行基于视点的绘制.算法首先对原始模型进行基于视点的精简,剔除大部分不可见点;再对精简后的模型进行球面对称变换,并构建变换后点集的凸包,进而提取出可见点集;最后运用真实感图形绘制技术实现可见点集的快速绘制.实验证明,本文算法能够快速地计算点集模型中采样点的可见性.该算法可应用于点集模型基于视点的绘制与曲面重建,以及点集模型的阴影绘制等领域. 相似文献