共查询到20条相似文献，搜索用时 42 毫秒
1.
郝晓军 《河北职业技术学院学报》2009,(2)
研究了怎样对于服从正态分布的平面点集进行的凸包算法加速,理论上计算了最适合的加速因子,同时通过相应的加速因子得到正态点集分布的凸包算法最优复杂度O(n)。 相似文献
2.
郝晓军 《廊坊师范学院学报(自然科学版)》2009,9(2):32-34
研究了怎样对于服从正态分布的平面点集进行的凸包算法加速,理论上计算了最适合的加速因子,同时通过相应的加速因子得到正态点集分布的凸包算法最优复杂度O（n）。 相似文献
3.
从蒲丰投针问题出发,利用线段与平行线相交之概率,导出一般的凸多边形与平行线相交之概率,进而利用两边夹原理得出一般的凸图形与平行线相交之概率,最后指出一般的图形与平行线相交之概率和其凸包与平行线相交之概率相同. 相似文献
4.
TSP问题是一个NP完全问题,在现实生活中许多领域得到充分应用。通过对＂S计算几何＂中凸包算法分析,提出了一种最大凸包工作集规划TSP路径算法,能快速解决二维TSP问题。首先运用凸包算法构造城市的最大凸包工作集,将剩余城市节点根据隶属度大小加入到相应的凸包子工作集中。再应用最大凸包算法逐个划分凸包子工作集,直至子工作集中的尺度为2。最后依次访问每个子工作集头,得到TSP最短路径。实验结果表明,该算法能更快速地得到问题的近似最优解。 相似文献
5.
目的:对简单多边形的三角剖分问题中的凸剖分问题,给出一种优化的算法。方法:利用简单多边形相邻凹点连线之间的关系,对简单多边形进行分类,采用递归分解的方法,实现简单多边形的凸剖分。结果:设计的算法每次分解可以获取多个子多边形,递归分解的次数少,每次分解前求交次数方面也优于参考文献[1]。结论:设计的算法简明实用,效率高,时间复杂度为O(n)。 相似文献
6.
基于点到角的最小距离提出一种判别点与多边形位置关系的新算法。通过扫描与点距离最小的线段,在多边形中有两个角共有此线段,选择其中任意一个角,定义点到此角的距离取得最小。判断点与角的内外侧关系,确定点与多边形内外侧位置关系。该算法通过点与点的距离运算避免了传统的交点、叉积的求解。比较试验表明,此新算法易于实现、计算速度快。 相似文献
7.
文章提出了一种平面散乱点集边界拟合算法,算法的基本思想是利用一种技巧对凸壳顶点进行筛选,使边界点迅速被找到,进而对其进行拟合。该算法能使用较少内存空间拟合平面散乱点集边界。设计了相应的vc程序验证了此算法。 相似文献
8.
构造了与给定多边形相切的分段三次、五次和六次可调广义Ball曲线,所构造的曲线分别是C1,C2和C3连续,而且对切线多边形是保形的.曲线的所有控制点由切线多边形的顶点直接计算产生.给出了在保持公共连接点处相应连续的条件下内控制点的活动范围.曲线可以在一定范围内做局部修改.计算实例表明文中方法是灵活、方便、有效的. 相似文献
9.
得到了平面凸多边形闭区域的一种较为简洁的参数方程.作为应用,给出了与凸多边形闭区域相关的求面积与最值等问题.特别地,给出了Jensen不等式的几何解释,并由此推广了一些已知的结果.最后,进一步讨论了几个与凸多边形闭区域相关的未解决的问题. 相似文献
10.
We present a new algorithm for nesting problems. Many equally spaced points are set on a sheet, and a piece is moved to one
of the points and rotated by an angle. Both the point and the rotation angle constitute the packing attitude of the piece.
We propose a new algorithm named HAPE (Heuristic Algorithm based on the principle of minimum total Potential Energy) to find
the optimal packing attitude at which the piece has the lowest center of gravity. In addition, a new technique for polygon
overlap testing is proposed which avoids the time-consuming calculation of no-fit-polygon (NFP). The detailed implementation
of HAPE is presented and two computational experiments are described. The first experiment is based on a real industrial problem
and the second on 11 published benchmark problems. Using a hill-climbing (HC) search method, the proposed algorithm performs
well in comparison with other published solutions. 相似文献
11.
利用分治法能够处理大规模问题但精度较低,分支限界法能够得到精确解但时间复杂度很高的优点,设计一种有效的基于分治法和分支限界法的大规模TSP求解方法.该算法利用聚类和凸包技术将大规模问题逐层进行有效划分,直到适合分支限界法求解的最佳规模;然后用分支限界法求出每个子问题和每层子问题间的最优解,合并而得到整个问题的解.比较实验表明:该算法在求解质量、稳定性和时间效率上有明显优势. 相似文献
12.
通过图的连通包集和连通包数的定义,得到了6类常见连通图（路、圈、树、完全二部图、轮图、蛛网图）的连通包数,并确定了Petersen图的连通包数。 相似文献
13.
YANG Cheng-lei QI Meng MENG Xiang-xu LI Xue-qing WANG Jia-ye 《浙江大学学报(A卷英文版)》2006,7(9):1522-1529
INTRODUCTION To compute the minimum distance between two convex polygons or polyhedrons is often a main step of many applications, such as collision detection (Choi et al., 2006; Li et al., 2003), path planning. In order to reduce the time complexity of the algorithm as much as possible, the convex property must be applied fully. Edelsbrunner (1985) proposed an algorithm for computing the minimum distance between two dis- joint convex polygons. The algorithm takes O(logm logn) time, and … 相似文献
14.
15.
AbstractThe Gauss-Lucas Theorem is a classical complex analysis result that states the critical points of a single-variable complex polynomial lie inside the closed convex hull of the zeros of the polynomial. Although the result is well-known, it is not typically presented in a first course in complex analysis. The ease with which modern technology allows the plotting of zeros and critical points makes the result discoverable by students. We propose a visual investigation, followed by a series of exercises leading to different complete proofs of the theorem. 相似文献
16.
This paper presents a new algorithm for line clipping against a polygonal window by exploiting the local relationship between each line segment and the polygon. Firstly, a minimal enclosing box (MEB) of the polygon is adopted to reject the invisible line segments located outside the MEB. Secondly, a 45° rotated box is used to encode the endpoint of the line segment, and then reject a portion of the invisible segments crossing polygon corners. Finally, instead of encoding the endpoints of all line segments with respect to the polygonal window, each vertex of the polygon is encoded, taking the line segment to be clipped as reference. For efficient encoding of the polygon vertices, a new concept, termed with slope adaptive virtual box, is introduced regarding each line segment. Such a box can not only conveniently reject all totally invisible lines lying outside the MEB conveniently, but also precisely identify the edges of the polygon with which the line segment potentially intersects. With the summation of the vertex codes, it can be verified whether the line segment is separated from or potentially intersects the polygon window. Based on the product of the codes of adjacent vertices, singular cases of intersection can be solved accurately. Experimental results demonstrate the efficiency and stability of the new algorithm. 相似文献
17.
设半群A是有限个幺半群{Ae}的强半格,所有幺元e的集合为I（A）．为I（A）定义一种序关系,使I（A）成为带偏序关系的半群．利用这个偏序半群构造出一个新的半群B,然后证明B和A的平移壳同构,从而揭示了A的平移壳的结构． 相似文献
18.
一个快速有效的凹多边形分解算法 总被引：1，自引：0，他引：1
提出了一个快速有效的凹多边形分解算法，避免了矢量法所需的大量、复杂的求交计算，因此该算法在时间及计算复杂性方面远远优于矢量法；而且该算法在三维环境中同样适用，这一点使得该算法除了在多边形裁剪中有广泛的应用外，在多面体的消隐中也经常用到．并用VisualC 语言实现． 相似文献
19.
ROCK是一种采用数据点间的公共链接数来衡量相似度的分层聚类方法,这种方法对于高维、稀疏特征的分类数据具有高效的聚类效果.其邻接度矩阵计算是影响其时间复杂度的关键步骤,将图形处理器(GUP)强大的浮点运算和超强的并行计算能力应用与此步骤,而其余步骤由CPU完成,这种基于GUP的ROCK算法的运算效率在AMD 643500+CPU和NVIDIA GeForce 6800 GT显卡的硬件环境下经过实验测试,证明其运算速度比完全采用CPU计算速度要快.这种改进的分层聚类算法适合在数据流环境下对大量数据进行实时高效聚类操作. 相似文献