共查询到20条相似文献,搜索用时 31 毫秒
1.
本文在对现有的相交检测算法进行研究的基础上,提出了基于夹边边对的空间平面凸多边形快速相交检测算法,为平面凸多边形间判交问题提供了一致的计算方法,并将算法的应用对象扩展到任意空间平面凸多边形。该算法分为两步:第一步,确定所要检测的两个凸多边形是否都存在相对于另一凸多边形所在平面的夹边边对,如果至少一个凸多多边形中不存在相对于另一凸多边形所在平面的夹边边对,那么立即返回两个多边形不相交;第二步,根据前面计算得到的两个凸多边形中的夹边边对,计算两组边对间对应夹边的符号距离判断两个多边形是否相交 相似文献
2.
本文提出了一个求两互不相交的凸多边形间的距离的快速算法,两个凸多边形间的距离指的是这两凸多边形沿着连心线方向以平移方式相互接近直至相交时所经过的路径长度。 相似文献
3.
4.
王晓东 《小型微型计算机系统》2002,23(8):995-999
本文提出了单调矩阵搜索问题一个统一的算法框架和实现策略,使得可在线性时间内求得矩阵搜索问题的解,并将此算法框架应用于设计凸多边形所有顶点最远邻点问题的高效算法。 相似文献
5.
判定凸多边形可碰撞的最优算法 总被引:14,自引:1,他引:14
设P与Q是平面内任意二互不相交的凸多边形,d为任一给定方向,本文研究P沿d以平移方式运动可否与Q碰撞的判定问题.文中定义了凸多边形顶点集上的偏序关系,给出了判定可碰撞性的新的充分必要条件,据此采用四分搜索方法构造了判定可碰撞的算法.在最坏情况下算法的复杂度为O(logn),在不计常数因子的情况下,这是最优的. 相似文献
6.
凸多边形窗口的线形裁剪算法是计算机图形学的基本问题之一,在许多领域均有应用。Cyrus-Beck算法是现有凸多边形窗口的线裁剪算法中最经典的,它采用不的是参数化方法。本文提出一种新的算法,采用基于交点符号的判别方法,裁剪过程在直角坐标系下进行。实验结果表明,本算法比Cyrus-Beck算法简单、直观。 相似文献
7.
求凸多边形直径是计算几何中的一个基本问题,在Preparata-Shamos算法的基础上,提出了采用动态规划和二分查找的算法,不需要对凸多边形进行预处理,使整个算法的时间复杂度降低到O(n)级别。对算法实现的理论分析结果进行了验证,实验结果表明算法具有较高效率。 相似文献
8.
蒋联源 《计算机工程与设计》2008,29(21)
平面点集的直径问题在计算机图形学、模式识别、图像处理、cAD,CAM等众多领域中均有广泛应用,该问题可转化为求凸多边形直径问题.研究得出了凸多边形顶点间距离关系的4条性质,利用这些性质提出一种基于顶点间距离性质的凸多边形直径算法.理论分析和实验结果表明,该算法计算速度快、存储效率高,实用性较强. 相似文献
9.
10.
求解Packing问题、计算机辅助设计、机器人路径规划、虚拟装配等经常用到凸多边形的不干涉算法。该文根据不适合多边形的概念,通过给定的平移规则控制平移多边形中心的移动方向和位移量而计算出两凸多边形的不适合多边形,进而提出了一种新的凸多边形不干涉算法。最后用实例说明了它在布局求解中的应用。文中方法不存在斜率图算法的缺陷,其计算复杂度为O(n+m)。 相似文献
11.
12.
基于直线斜率的凸多边形线裁剪算法 总被引:1,自引:0,他引:1
凸多边形的线裁剪算法在计算机图形学中占据着很重要的地位,现在的许多领域均有很重要的应用。本文提出了一种非常有效的基于直线斜率的凸多边形线裁剪算法,并与Cyrus—Berk算法进行了比较。结果表明:本算法更加简单、高效。 相似文献
13.
该文研究并提出了一种凸多边形的裁剪算法,它不同于传统的多边形剪算法,仅需对视口在点所关联的边检查与视口的相一。裁剪速度快,简单易行。 相似文献
14.
一、问题 2001年第7期擂台赛给出了这样一个问题:给定两凸多边形,则两凸多边形的相交部分也一定是一个凸多边形,请编程求出它们公共相交的凸多边形的面积。 (二)预备讨论 首先介绍后面要用到的几个子问题的解法。 第一,如何判断一个点是否在一个凸多边形内部? 相似文献
15.
16.
17.
为了获得丰富的曲面造型效果,构造了一种兼具单峰性和区域峰值性,支撑区域为任意凸多边形域的伸缩因子.首先引入基于凸多边形域的伸缩因子;然后构造了空间变形矩阵;最后将上述变形矩阵作用于待变形曲面的方程上,获得相应的变形效果.数值实例结果表明,通过调控支撑区域、峰值区域、变形中心、主方向、伸缩参数和光滑参数,可以灵活地对曲面变形;该方法不仅计算简单、易于控制,还能精确地控制变形的范围,迭加使用可以得到丰富的变形效果. 相似文献
18.
计算两凸多边形交集面积的计算机算法 总被引:11,自引:0,他引:11
张宝琳 《计算机工程与应用》2001,37(9):128-129
该文提出了计算两凸多边形交集面积的新的计算机算法。算法设计的思路简单,易于实现,实际应用中具有鲁棒性(robustness)。 相似文献
19.
一种改进的求凸多边形直径的最优算法 总被引:2,自引:1,他引:1
曲吉林 《计算机工程与应用》2005,41(26):94-96
求凸多边形的直径是计算几何中的一个基本问题。该文对Preparata-Shamos提出的最优算法进行了改进,使距离比较中的运算的次数从44n次减少到14n次,并减少了平行边的处理时间。实验结果表明,算法的运行时间减少到原来的53%。 相似文献
20.
在研究中轴性质的基础上,给出了一种全新的求解凸多边形直径算法。该算法首先求出凸多边形的中轴,再根据中轴的两个端点确定直径。算法简单,并在无预处理的情况下达到了O(n)。 相似文献