首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到19条相似文献,搜索用时 125 毫秒
1.
在求解Packing问题、机器人路径规划、虚拟装配、碰撞检测等常用到椭圆-矩形的不干涉算法。针对椭圆和矩形分别在静止、运动状态下的不干涉问题,该文在Adamowicz&Albano的NFP基础上,给出了椭圆-矩形的静、动态不适合边界(NoFitBoundary,NFB)的定义,用图形变换方法证明了静态不适合边界是由4条线段和4段椭圆弧组成的对称曲八边形,给出了对称曲八边形顶点计算公式,提出了椭圆-矩形的静、动态不干涉算法。该算法简单且具有一定的应用价值。  相似文献   

2.
黎自强  滕弘飞 《计算机工程》2008,34(20):241-243
对被检测的2个长方体作图形变换,使其中一个长方体的最低顶点和以其作为端点的最长边分别与空间直角坐标系的原点和z轴重合,利用其在坐标平面上正投影的干涉性和空间解析几何理论得出在3D空间中2个长方体不干涉的3种可能情形,根据2D不适合多边形方法分别给出其不干涉判别条件的长方体碰撞检测算法。实验表明该方法具有较快的检测速度。  相似文献   

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

4.
基于链码和特征形的多边形内外点判断算法   总被引:1,自引:0,他引:1  
通过对多边形各个顶点与待测点相对位置进行判别,给出了多边形的垂直(水平)链码序列生成方法.该方法根据多边形的链码将原多边形中对判别无关的冗余边或冗余点删除,形成多边形的特征形;待测点在特征形与原多边形内外位置关系上具有一致性,从而大大简化了运算.同时给出了一种点在多边形内外点判断算法,把点在原多边形内外的判断转化为点与其特征形的位置判断,特征形的提取过程是一个线性扫描及条件判断过程,可以避免大量的又积运算,从而有效地提高了多边形内外点判断算法的效率.程序验证表明:文中算法易于实现,具有运行速度快、稳定性高等优点.  相似文献   

5.
求解Packing问题、计算机辅助设计、机器人路径规划、虚拟装配等经常用到凸多边形的不干涉算法。该文根据不适合多边形的概念,通过给定的平移规则控制平移多边形中心的移动方向和位移量而计算出两凸多边形的不适合多边形,进而提出了一种新的凸多边形不干涉算法。最后用实例说明了它在布局求解中的应用。文中方法不存在斜率图算法的缺陷,其计算复杂度为O(n+m)。  相似文献   

6.
基于矩形包围盒的多边形碰撞检测算法   总被引:9,自引:0,他引:9       下载免费PDF全文
碰撞检测是计算机图形学领域中的一个普遍存在的问题。为了提高多边形碰撞检测的效率 ,针对简单形式刚性运动的多边形对象 ,提出了一种基于二维轴向矩形包围盒结构的平面简单多边形碰撞检测算法。该算法基于坐标轴的单调性对多边形进行分割 ,并通过矩形包围盒之间的预检来减少无关边对的相交测试 ,以加速算法的终止。由于采用轴向扫描线方法可以大大减少包围盒测试的数量和线段求交的数量 ,所以 ,经过少量的“边 -边”相交判断就能求解到所有交点 ,同时能快速地获得两多边形干涉发生的第 1位置。试验表明 :(1)对于一般多边形 ,该算法的复杂度也远远低于 O(NP× NQ) ;(2 )对于凸多边形对象 ,该算法的复杂度为 O(NP NQ) ,其中 NP,NQ 为多边形 P,Q的顶点数。由此可见 ,算法能够获得较好的运算效率  相似文献   

7.
刘景发  刘思妤 《软件学报》2018,29(2):283-298
卫星舱布局问题不仅是一个复杂的耦合系统设计问题,也是一个特殊的优化问题,具有NP难度性。解决这类问题最大的挑战在于需要优化的目标函数具有大量的被高能势垒分隔开的局部极小值点。Wang-Landau(WL)抽样算法是一种改进的蒙特卡罗方法,已经被成功地运用蛋白质结构预测等优化问题。本文以卫星舱布局优化问题为背景,首次将WL抽样算法引入矩形装填问题的求解。针对矩形装填物的特点,提出了启发式格局更新策略,以引导抽样算法在解空间中进行有效行走。为了加速搜索全局最优解,每次蒙特卡罗扫描生成新的布局时,便执行梯度法进行局部搜索。通过将局部搜索机制、启发式格局更新策略与WL抽样算法相结合,提出了一种用于解决带静不平衡约束的任意矩形装填问题的启发式布局算法。在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项并采用质心平移的方法,使布局系统的静不平衡量达到约束要求。另外,为了改进算法的搜索效率,提出了改进的有限圆族法用于装填物之间的干涉性判断和干涉量计算。通过对文献中两组共10个有代表性的算例进行实算,计算结果表明,所提出的装填算法是一种求解带静不平衡性能约束的任意矩形装填问题的有效算法。  相似文献   

8.
一个有效的多边形窗口的线裁剪算法   总被引:25,自引:1,他引:24  
刘勇奎  颜叶  石教英 《计算机学报》1999,22(11):1209-1214
已有的线剪裁算法都是针对矩形窗口或凸多边形窗口的,对于一的多边形窗口(包括凹多边形)的线剪裁,目前尚无有效的算法,而这样的算法却有更普遍的应用意义。该文提出一个对于一般多边形窗口的线剪裁算法。该算法在被裁剪直线的延长线上取一固定点,然后求多边形窗口的每一顶点到该固定点引线的斜率。这样对于每个窗口边只需判断被裁剪直线的斜率是否在该边两顶点到固定点引线斜率之间,就可判定直线与边是否相交,因此,每处理一  相似文献   

9.
GIS缓冲区重叠合并的快速算法   总被引:5,自引:1,他引:5  
为了解决地理信息系统(GIS)缓冲区多边形间重叠合并问题,本文对正负缓冲区多边形边界相交后结点上弧段的方向规律进行了分析,提出了结点上有向弧段的删除规则。基于这一规则,形成了缓冲区多边形重叠合并的算法。该算法避免了通过多边形与曲线包容关系的判断来决定弧段取舍的复杂计算,因而具有简捷、高效的特性。  相似文献   

10.
许健  杨新  郭强  孙锟 《计算机工程》2006,32(3):231-232,256
三维纹理的体绘制算法由于其利用显卡加速渲染、硬件实现三线性插值和不丢失图像的纹理特性3大优点,尤其适合医学超声数据的实时三维可视化。显示大量多边形切片(slice polygon)是当前影响三维纹理体绘制渲染实时性的重要因素。为了克服常用的参数化算法在快速生成大量多边形切片时性能不佳的缺点,提出了的空间活动边表的方法,充分利用各个多边形切片之间的空间相关性实现增量计算,明显提高了计算速度。  相似文献   

11.
Rectangles with dimensions independently chosen from a uniform distribution on [0,1] are packed on-line into a unit-width strip under a constraint like that of the Tetris game: rectangles arrive from the top and must be moved inside the strip to reach their place; once placed, they cannot be moved again. Cargo loading applications impose similar constraints. This paper assumes that rectangles must be moved without rotation. For n rectangles, the resulting packing height is shown to have an asymptotic expected value of at least (0.31382733 ...)n under any on-line packing algorithm. An on-line algorithm is presented that achieves an asymptotic expected height of (0.36976421 ...)n. This algorithm improves the bound achieved in Next Fit Level (NFL) packing, by compressing the items packed on two successive levels of an NFL packing via on-line movement admissible under the Tetris constraint. Received: 6 February 2001 / 25 June 2002  相似文献   

12.
一个新的椭圆-椭圆的静动态不合适边界算法   总被引:2,自引:1,他引:2  
在求解Packing问题、机器人路径规划、虚拟装配、三维圆形管道作任意斜切割、医疗内外科手术中等经常用到两椭圆干涉算法。该文根据椭圆的画法提出了一个新的椭圆-椭圆的静动态不合适边界算法。和陈羽等(2003)的算法相比,该算法无需反复求三角函数和反正切三角函数值。另外,该算法具有计算工作量相对较少,容易实现等特点。  相似文献   

13.
基于形态学的新的汉字字形自动生成方法   总被引:7,自引:1,他引:6  
电子印刷,桌面出版,艺术,广告等领域对不同风格汉字的需求,迫切需求一种自动的汉字字形生成方法。传统方法只适用于两种字形相关不大的字体进行合成,并且需人干预,本文通过对字体的凸剖分,并建立两种不同字体的子凸集映射,提出了一种全新的基于形态变换的汉字形自动生成方法,  相似文献   

14.
《国际计算机数学杂志》2012,89(15):3525-3545
This paper is concerned with option pricing under a regime-switching model. The switching process takes two different modes, and the underlying stock price evolves in accordance with the two modes dictated by a continuous-time, finite-state Markov chain. At any given instance, the price follows either a geometric Brownian motion model or a mean-reversion model, depending on its market mode. Stochastic approximation/optimization algorithms are developed for model calibration. Convergence of the algorithm is proved; rate of convergence is also provided. Option market data are used to predict the future market mode.  相似文献   

15.
We propose 2D stick figures as a unified medium for visualizing and searching for human motion data. The stick figures can express a wide range or human motion, and they are easy to be drawn by people without any professional training. In our interface, the user can browse overall motion by viewing the stick figure images generated from the database and retrieve them directly by using sketched stick figures as an input query. We started with a preliminary survey to observe how people draw stick figures. Based on the rules observed from the user study, we developed an algorithm converting motion data to a sequence of stick figures. The feature‐based comparison method between the stick figures provides an interactive and progressive search for the users. They assist the user's sketching by showing the current retrieval result at each stroke. We demonstrate the utility of the system with a user study, in which the participants retrieved example motion segments from the database with 102 motion files by using our interface.  相似文献   

16.
The general label-placement problem consists in labeling a set of features (points, lines, regions) given a set of candidates (rectangles, circles, ellipses, irregularly shaped labels) for each feature. The problem arises when annotating classical cartographical maps, diagrams, or graph drawings. The size of a labeling is the number of features that receive pairwise nonintersecting candidates. Finding an optimal solution, i.e., a labeling of maximum size, is NP-hard. We present an approach to attack the problem in its full generality. The key idea is to separate the geometric part from the combinatorial part of the problem. The latter is captured by the conflict graph of the candidates. We present a set of rules that simplify the conflict graph without reducing the size of an optimal solution. Combining the application of these rules with a simple heuristic yields near-optimal solutions. We study competing algorithms and do a thorough empirical comparison on point-labeling data. The new algorithm we suggest is fast, simple, and effective. Received December 21, 1998; revised October 13, 1999.  相似文献   

17.
为了探索和改进操作系统课程的教学方法,加强学生对动态分区的深入理解,采用C语言中的链表模拟实现了动态分区中的两种分配算法:首次适应算法(First Fit)、最佳适应算法(Best Fit),以及内存回收算法。模拟结果表明:这种理论加实践的教学不仅有助于学生掌握操作系统的理论知识,使抽象内容具体化,而且有助于提高学生分析数据、选择数据结构以及综合编程的能力。  相似文献   

18.
梁利东  贾文友 《计算机应用》2018,38(4):1195-1200
针对2D Packing排样方法中存在的择优匹配思想与排样优劣评估的平衡性问题,基于多目标优化的宽容分层策略提出一种新颖有效的择优匹配启发式排样算法。首先,定义排样空间和匹配值,计算入排零件与排样空间的宽、高匹配值,然后建立统一的多目标优化函数模型,并根据目标函数值的大小来确定排放优先规则。特别针对一般可排入匹配情况,可在目标函数模型中通过设置和调整宽容值,最后实现多种排样布局的最优化。对benchmark问题的7类数据实例的计算结果表明,该算法相对于底部左齐择优匹配(LLABF)和水平线择优匹配(LSBF)算法,Gap的平均值可降低了2%;在C1P1+C3P1以及C2~C7随机构成的两组混合数据测试中(矩形数量为33和66),排样高度达到24和339。该算法也可用于多类型异形零件的排样过程。  相似文献   

19.
一种基于几何特征参数的圆检测方法   总被引:1,自引:0,他引:1       下载免费PDF全文
提出了一种利用一组几何特征参数对图像中的圆形进行检测的方法。对提取出的边缘进行多边形拟合,并对拟合后的多边形进行归一化处理,提取平移、旋转和尺度变换不变性的几何特征,计算相应的几何特征参数,将几何特征参数满足一定条件的形状识别为圆形。描述了该方法的具体步骤,并与随机Hough变换进行了对比实验。对合成图像和真实图像进行的实验结果表明,该方法具有较高的效率和实用性。  相似文献   

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

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