共查询到19条相似文献,搜索用时 125 毫秒
1.
在求解Packing问题、机器人路径规划、虚拟装配、碰撞检测等常用到椭圆-矩形的不干涉算法。针对椭圆和矩形分别在静止、运动状态下的不干涉问题,该文在Adamowicz&Albano的NFP基础上,给出了椭圆-矩形的静、动态不适合边界(NoFitBoundary,NFB)的定义,用图形变换方法证明了静态不适合边界是由4条线段和4段椭圆弧组成的对称曲八边形,给出了对称曲八边形顶点计算公式,提出了椭圆-矩形的静、动态不干涉算法。该算法简单且具有一定的应用价值。 相似文献
2.
3.
在充分挖掘AutoCAD图形中简单多边形自身隐含的垂直与共线关系的基础上,提出一种新的基于直角顶点判定和凹凸顶点判定的简单多边形剖分算法。该算法首先判断出多边形顶点的直角特性和凹凸性,然后根据多边形自身的特点按照一定的先后次序进行剖分,力求把多边形分割成直角梯形、矩形和直角三角形的形式。其中判断辅助线连接次序的优先级是实现剖分算法的关键。程序实现中采用递归算法,对分割后的多边形重新进行判断,直到多边形分割完毕。 相似文献
4.
基于链码和特征形的多边形内外点判断算法 总被引:1,自引:0,他引:1
通过对多边形各个顶点与待测点相对位置进行判别,给出了多边形的垂直(水平)链码序列生成方法.该方法根据多边形的链码将原多边形中对判别无关的冗余边或冗余点删除,形成多边形的特征形;待测点在特征形与原多边形内外位置关系上具有一致性,从而大大简化了运算.同时给出了一种点在多边形内外点判断算法,把点在原多边形内外的判断转化为点与其特征形的位置判断,特征形的提取过程是一个线性扫描及条件判断过程,可以避免大量的又积运算,从而有效地提高了多边形内外点判断算法的效率.程序验证表明:文中算法易于实现,具有运行速度快、稳定性高等优点. 相似文献
5.
求解Packing问题、计算机辅助设计、机器人路径规划、虚拟装配等经常用到凸多边形的不干涉算法。该文根据不适合多边形的概念,通过给定的平移规则控制平移多边形中心的移动方向和位移量而计算出两凸多边形的不适合多边形,进而提出了一种新的凸多边形不干涉算法。最后用实例说明了它在布局求解中的应用。文中方法不存在斜率图算法的缺陷,其计算复杂度为O(n+m)。 相似文献
6.
碰撞检测是计算机图形学领域中的一个普遍存在的问题。为了提高多边形碰撞检测的效率 ,针对简单形式刚性运动的多边形对象 ,提出了一种基于二维轴向矩形包围盒结构的平面简单多边形碰撞检测算法。该算法基于坐标轴的单调性对多边形进行分割 ,并通过矩形包围盒之间的预检来减少无关边对的相交测试 ,以加速算法的终止。由于采用轴向扫描线方法可以大大减少包围盒测试的数量和线段求交的数量 ,所以 ,经过少量的“边 -边”相交判断就能求解到所有交点 ,同时能快速地获得两多边形干涉发生的第 1位置。试验表明 :(1)对于一般多边形 ,该算法的复杂度也远远低于 O(NP× NQ) ;(2 )对于凸多边形对象 ,该算法的复杂度为 O(NP NQ) ,其中 NP,NQ 为多边形 P,Q的顶点数。由此可见 ,算法能够获得较好的运算效率 相似文献
7.
卫星舱布局问题不仅是一个复杂的耦合系统设计问题,也是一个特殊的优化问题,具有NP难度性。解决这类问题最大的挑战在于需要优化的目标函数具有大量的被高能势垒分隔开的局部极小值点。Wang-Landau(WL)抽样算法是一种改进的蒙特卡罗方法,已经被成功地运用蛋白质结构预测等优化问题。本文以卫星舱布局优化问题为背景,首次将WL抽样算法引入矩形装填问题的求解。针对矩形装填物的特点,提出了启发式格局更新策略,以引导抽样算法在解空间中进行有效行走。为了加速搜索全局最优解,每次蒙特卡罗扫描生成新的布局时,便执行梯度法进行局部搜索。通过将局部搜索机制、启发式格局更新策略与WL抽样算法相结合,提出了一种用于解决带静不平衡约束的任意矩形装填问题的启发式布局算法。在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项并采用质心平移的方法,使布局系统的静不平衡量达到约束要求。另外,为了改进算法的搜索效率,提出了改进的有限圆族法用于装填物之间的干涉性判断和干涉量计算。通过对文献中两组共10个有代表性的算例进行实算,计算结果表明,所提出的装填算法是一种求解带静不平衡性能约束的任意矩形装填问题的有效算法。 相似文献
8.
9.
GIS缓冲区重叠合并的快速算法 总被引:5,自引:1,他引:5
为了解决地理信息系统(GIS)缓冲区多边形间重叠合并问题,本文对正负缓冲区多边形边界相交后结点上弧段的方向规律进行了分析,提出了结点上有向弧段的删除规则。基于这一规则,形成了缓冲区多边形重叠合并的算法。该算法避免了通过多边形与曲线包容关系的判断来决定弧段取舍的复杂计算,因而具有简捷、高效的特性。 相似文献
10.
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.
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.
针对2D Packing排样方法中存在的择优匹配思想与排样优劣评估的平衡性问题,基于多目标优化的宽容分层策略提出一种新颖有效的择优匹配启发式排样算法。首先,定义排样空间和匹配值,计算入排零件与排样空间的宽、高匹配值,然后建立统一的多目标优化函数模型,并根据目标函数值的大小来确定排放优先规则。特别针对一般可排入匹配情况,可在目标函数模型中通过设置和调整宽容值,最后实现多种排样布局的最优化。对benchmark问题的7类数据实例的计算结果表明,该算法相对于底部左齐择优匹配(LLABF)和水平线择优匹配(LSBF)算法,Gap的平均值可降低了2%;在C1P1+C3P1以及C2~C7随机构成的两组混合数据测试中(矩形数量为33和66),排样高度达到24和339。该算法也可用于多类型异形零件的排样过程。 相似文献