基于梯形分解的不规则多边形干涉算法

研究了二维两不规则多边形之间的干涉量计算问题,将不规则多边形离散为有限个梯形的组合,从而转化为两两梯形对之间干涉量计算问题。分析了两梯形间干涉拓扑图形类型,并按内点个数区间及干涉量多边形顶点性质将其归类,给出两梯形对干涉量计算方法。在此基础上提出用水平梯形剖分不规则多边形的思想,进而得到基于梯形分解的平面多边形干涉算法,并进行该算法复杂度分析。最后,算例表明了本算法的可行性。     

二维不规则图形排料CAD系统的设计

采用轨迹线算法、自适应最低重心规则和遗传算法,解决了不规则图形的计算机辅助排料问题。提出采用轨迹线求解临界多边形实现快速的多边形靠接,根据自适应最低重心NFP的排样放置原则,配合改进后快速收敛的遗传算法,设计了一套自动并支持实时交互的排料CAD系统,给出了排料结果和对比,取得了良好的排料结果和应用。系统还提供零件及板材库的管理功能。     

基于三角划分的多连通域图形匹配研究

由若干个多边形通过组合产生的具有多个连通域的多连通域图形识别问题是工程图纸识别与理解所要解决的重要问题。首先,通过建立包围多边形、连通多边形概念,完成对多连通域图形的表示;然后,依据最近距离、无遮挡、包含原则添加辅助线,实现三角划分,解决了包含连通的定位问题。在匹配过程中,首先通过匹配包围多边形实现多连通域图形的外轮廓定位;然后通过匹配连通多边形删除连通域,逐步收缩图形,实现图形匹配。应用此方法,解决了多连通域图形的旋转、缩放匹配问题,在汽车线束图纸识别中取得了良好的应用效果。     

多边形OFFSET中无效环的去除算法

对于多边形OFFSET后产生的自交环现象,提出一种求解自交点的基于单调链的平面扫描算法,并对环的判别提出了一种简便而有效的方法。最后,对算法的时间复杂度进行了分析。实验表明,该算法高效而稳定地处理多边形OFFSET后产生的自交环。     

缺陷板材非规则件优化排样

针对理论上属于NPC问题的非规则件优化排样问题,论文提出一种基于小生境技术的自适应遗传模拟退火算法与基于内靠接临界多边形最低点的启发式布局算法相结合的方法。考虑到算法中交叉概率和变异概率的选择影响到算法收敛性,提出了自适应的交叉概率和变异概率,通过基于小生境技术的遗传模拟退火算法对非规则件排样的最优顺序和各自的旋转角度进行优化搜索。将非规则件定位在有缺陷原材料和非规则件多边形的内靠接临界多边形最低点以实现个体的解码,同时避开了原材料表面缺陷。排样实例表明,该优化排样算法行之有效,具有广泛的适应性。     

简单多边形方向及顶点凹凸性的快速判定

基于简单多边形方向与顶点凹凸性的内在联系，采用极值点性质判定多边形方向，通过多边形顶点坐标判定其拓扑映射点之间的位置关系，结合以上两方面对顶点的凹凸性作出判断。对基于拓扑映射的多边形顶点凹凸判别算法作出有效的改进，避免了原算法申大量的重复计算。实践证明，有效的减少计算次数，提高了效率。     

改进的波束形成算法及其在多声源定位中的应用

为提高多点声源工况的定位精确度及简化设备,对传统波束形成算法进行改进。引入改进扫描中的扫描向量并结合遗传算法对求解域内的非线性方程组进行求解,从而提高定位精度。基于改进算法,在消声室内采用空间星型(Y型)传感器阵列对不同声源进行定位,并将结果与传统算法定位结果进行比较。由比较可见:当多个声源相距较近时,这些源等效于单一点源,两种算法定位结果基本一致;但当声源相互距离增大时,改进算法可以有效提高定位精度,并准确定位多个源的位置。     

基于传递矩阵法的不确定链式结构固有频率区间分析

基于传递矩阵法，将链式结构中的不确定性参数用区间数来表示，导出关于系统固有频率的非线性区间方程，并针对该方程的求解，提出了一种区间逐步离散算法。此方法通过不确定性参数取区间离散值，将区间方程转化为相应的确定性方程，再搜索方程解中的最大最小值来确定系统各阶固有频率的边界。文中给出两个具有不确定性参数的链式结构算例，计算结果表明该算法是可行和有效的。     

基于区间法的发动机曲轴不确定性优化研究

该文基于非线性区间数规划方法和区间分析方法,针对某型发动机曲轴的不确定性优化问题进行了研究。载荷中的不确定参数采用区间描述,极限工况下的最大等效应力作为目标函数且通过有限元方法求解。非线性区间数规划方法用以处理不确定目标函数,区间分析方法用以快速求解目标函数在每一个设计矢量下的区间,隔代映射遗传算法作为优化求解器。应用算例说明了该文算法的有效性。     

求简单多边形可见点的一种新算法

提出一种求简单多边形可见点的新算法,通过对多边形作预处理,可预先剔除其中部分不可见点,并消除了判断可见点过程中的螺旋状态.将多边形剩余顶点序列分割为四段,每段分别按文中给出的方法找出可见点.算法中对点与线段的位置关系,用点与线段围成的三角形的方向表示.三角形的方向通过极点顺序法确定,避免了使用耗时的叉积法.试验表明,算法准确、高效和稳定.     

Asymmetric distribution of the scanned field of a rotating reflective polygon

A rigorous vector analysis is performed to investigate the structure of the scan field produced by a rotating polygon, and it is shown that the scan field is asymmetric to the ray reflected by the polygon at a neutral scan position. Some fundamental aspects of the polygon scanning systems are addressed, such as the scan duty cycle, the locus of the scan center, the depth of the scan field, and the off-axis defocus in convergent beam scanning.     

基于有向图的边界表示模型与重描算法

图像边界的精确表示和快速处理在模式识别、图像处理以及计算机视觉等领域扮演着十分重要的角色。本文提出了一种基于有向图的边界表示模型，并实现了一种边界跟踪平滑以及特征点检测算法，只需对图像进行一次遍历，即可实现边界的平滑和特征点检测。文章最后给出了该算法的一些实例。     

一种新的红外目标跟踪方法

一般的Snake模型用于目标跟踪时存在一些问题,如要求初始控制点位置非常接近于真实 轮廓、不能可靠跟踪快速运动目标、对目标的运动规律有许多约束条件等。在继承所提出的Auto-Snake模型跟踪算法优点的基础上,进一步采用最小二乘估计预测器对目标的位置进行预测,放宽对运动规律的约束,可以实现对快速运动(大位移)的目标的自动跟踪。     

A method for the automatic generation of triangular elements on a surface

An algorithm is given to discretize a polygon or curved surface into triangular arrays. The method first involves the manual division of the array into quadrilaterals with specified numbers on rows and columns. The individual points are then filled in automatically and elements are automatically generated. A point of particular importance is that the number of columns or rows may be made to change. A subroutine is given to perform this task.     

格网划分的双策略跟踪多边形裁剪算法

论文提出了一种高效稳定的多边形裁剪算法,算法支持带内环的平面简单多边形,同时也支持多边形的“并”和“差”等布尔运算.首先,设计了算法所需的数据结构;其次,基于直线扫描转换Bresenham算法原理提出了边网格划分的有效算法,并应用一个简单的方法避免不同网格内边的重复求交;最后,将交点分类为普通交点和顶交点,并针对这两类交点构造了不同的跟踪策略,在跟踪过程中交替、递归地应用这两个策略来确保算法处理特殊情况时的稳定性.与其它同类算法的比较表明,新算法具有更高的效率.     

Flat-field postobjective polygon scanner

A general two-dimensional ray-trace analysis is presented for the motion of a geometric focal point over a flat surface provided by a postobjective rotating polygon laser beam scanner. The exact defocus equation is derived for any value of the neutral scan position deflection angle and the polygon rotation angle. The scan nonlinearity is derived for the special case of a zero neutral scan deflection angle. Geometric parameters were found that reduce the peak-to-peak defocus by more than an order of magnitude from that found in previous design approaches. Conditions were also found that reduce scan nonlinearity to less than 2 × 10(-4). Practical limitations, such as large polygons and beam obscurations, encountered in the implementation of postobjective scanning are discussed.     

体可视化的快速光线投射算法

对规则标量数据场的体绘制算法进行了讨论。在此基础上给出了一种快速的自前向后的光线投射算法,利用多边形扫描转换减少了投射光线的数量。通过光线的参数化表示方法减少了光线与数据场求交的计算量。并且通过将Bresenham算法扩展至三维,对光线通过三维扫描转换以进行体素化,从而避免了对空间的采样从而加速了光线投射的效率,而且通过利用OpenGL提供的函数接口,简化了算法的实现过程。     

Effective nesting of rectangular parts in multiple rectangular sheets using genetic and heuristic algorithms

In this paper, a hybrid approach, employing both genetic and heuristic algorithms, is proposed for nesting of different rectangular parts in multiple rectangular sheets with the objective of utilizing the sheet material effectively. The proposed genetic approach gives the best sequence of sheets and parts to generate an effective nested pattern with a heuristic algorithm. The heuristic approach arranges each of the parts in the bottom-left-most position of the sheet(s) by considering the sequence of sheets and parts given by the genetic algorithm. The effectiveness of the proposed approach is shown by comparing the results obtained with the present approach to those obtained by Jakobs' (1996, European Journal of Operational Research , 88 , 165-181) approach when all the parts are nested in a single sheet. Finally, the application of the current approach for nesting of rectangular parts in multiple sheets is illustrated.     

生成正多边形和圆的新算法

针对正多边形各顶点坐标的计算,构造了新的递推公式并加以证明。以新公式为基础给出了正多边形和圆生成算法,并对算法误差进行了分析。计算正多边形每个顶点需要两次乘法和两次加法,优于目前＂多边形逼近法＂所采用的顶点计算方法。算法具有构造简单、执行速度较快和精度高的特点。理论分析和上机验证算法可行,完全可以满足常规的应用。     

Accommodating diverse shapes within hexagonal pavers

The efficient nesting of shapes is an important consideration in industries as diverse as ship building and shoe making. Optimum layouts yield significant savings in material, and consequently lead to lower unit cost of components. This paper considers how any shape, including concavities and circular sections, can be approximated to a polygon and determines the hexagonal paver that circumscribes this convex polygon for minimum area addition. Previous studies have shown that no convex polygon with more than six sides can be fitted side by side to give continuous surface covering of a plane.