测点数据生成刀具路径研究

为了提高反求加工的效率，提出由大规模测点数据直接生成粗、精加工刀具路径的算法．粗加工采用层切法分层切削材料，首先构造健壮的数据结构——层切网；然后计算无干涉刀位点，并把整个层切网划分为几个优化的子加工区域；最后应用优化的刀路链接法则得到粗加工刀具路径．精加工由大规模数据点构建三角曲面．为了避免干涉，需计算点、面和边的无干涉刀位点．实验结果表明，粗加工刀具路径算法具有较高的效率，只需要占用较小的内存空间；精加工可以成功地避免干涉并且获得可靠的表面精度．     

轮廓平移无跳刀连接刀路环树优化算法

提出一个无跳刀的轮廓平移刀路轨迹优化算法．根据刀路环之间父环和子环关系,提出“刀路环树”的概念,将加工刀路的一次环切定义为一个“刀路环向量”,并将刀路环的各个属性定义为刀路环向量的分量．根据无跳刀轨迹的要求,针对刀路环树的各个刀路环向量进行遍历,以获得了一个无跳刀的轮廓平移刀路轨迹算法,并通过与其他算法比较,证明该算法无跳刀、无重复切削,并且可以自动执行．     

环切区域加工分步式刀具轨迹生成算法研究

与传统的集中式刀具轨迹计算方法不同,基于ＮＣ特征单元,把刀具轨迹计算分为两步完成,以此改善数控加工系统的可集成性,可视性和可控性,给出了抽象ＮＣ特征单元及适合２．５轴区域加工的环切特征单元的定义,提出了通过链接划分法生成环切特征单元,以及通过环切特征单元计算刀具轨迹的算法。     

测量点数据等残留高度刀具路径规划

在介绍计算几何模型的基础上,提出一种刀具路径算法.首先分别以刀具半径值和残留高度值为等距距离,通过等距计算求出等距点集和残留高度点集;然后以前一行刀具路径为中心构建刀具包络面,并求出刀具包络面与残留高度点集的交点,即过渡点集;最后通过求以过渡点集为中心的刀具包络面与等距点集的交点,得出相邻行刀具轨迹,依次递推,求出所有的刀具路径行.针对计算过程中可能出现的欠切问题,给出了应用密切圆追踪的边界处理方法.通过实例验证了该算法的可行性.与等间距刀具路径生成方法进行比较表明,应用文中算法解决针对测量点数据的数控加工刀具路径生成问题,可缩短刀具路径长度,提高加工效率.     

路径存储法在生成树形结构中的应用研究

动态树形结构应用十分广泛,现有的"遍历节点法"、"层点展开法"、"多表存储法"等技术在生成树形结构时有利有弊。本文将节点在树分支中的线性结构关系作为路径,把路径信息存储在节点数据表的一个字段中,并将路径信息作为检索排序依据,实现对树节点排序,从而按照此序列生成树形结构的路径存储法。该方法提高了"遍历节点法"访问节点算法的效率,解决了"层点展开法"的访问子树节点问题,优化了"多表存储法"的存储结构。     

用静态链表和逆序插入算法构成的动态查找表

目前的动态查找表都是树结构,对于结点量很大的情况,其所需存储空间过大且查找效率低的缺点突出.对此.文章设计了一种新的动态查找表,将有序静态链表结构与结点群"逆序插入"算法相结合,相比树结构动态查找表有两个优势:1.所需存储空间小;2.结点群的结点数越多,则动态查找效率越高.该方法的要点是:先将已有结点用静态链表构造出一个有序表,简称"主表".若某"结点群"要插入该主表中,需将该结点群用静态链表构造成一个有序"副表",然后用逆序算法对副表中各结点查找其在主表中的插入点,并从对应的插入点与主表进行链接,最后将链接好的主表和副表一次性收集到一个新的静态链表中.类似的"逆序删除"也可以删除整个副表的结点.     

基于几何特性的槽加工刀具选取算法

刀具选取是复杂零件数控加工编程的一项重要内容,为实现数控加工程序编制过程中自动选取加工刀具,提高数控加工及其编程效率和质量,结合飞机整体壁板数控加工编程及其粗加工特点,提出基于几何特性的槽加工刀具自动选取算法.在分析刀具与可切削区域间关系的基础上,对Voronoi Mountain定义域进行修正,建立切削轮廓45°拔模体;并给出刀具的可切削面积、残留不可切削面积,以及小刀具半径计算方法;最后根据整体加工时间最短的原则确定最优加工刀具.该算法已在"飞机壁板快速数控加工编程系统"项目中得以应用,结果证明了其是可行、有效的.     

基于有序双循环链表的低代价最短路径树快速算法

低代价最短路径树是一种广泛使用的多播树。在FLSPT算法的基础上,通过选择有序双循环链表作为待发展节点序列Q的运算与存储中心,提出了基于有序双循环链表的低代价最短路径树快速算法DKFLSPT。该算法构造的最短路径树与FLSPT算法构造的最短路径树具有相同的性能,利用有序双循环链表的局部性原理来达到改进节点路径最小值的搜索过程。随机网络模型的仿真结果表明,DKFLSPT 算法效率平均可以提高19%。     

基于可视图与A*算法的路径规划

结合可视图的骨架构造方法和A~*图搜索方法,采用矩形包络障碍物,在障碍物顶点外延生成路径点。在此基础上,提出一种新的路径规划算法Lambda~*,与A~*算法类似,搜索过程需要2张表,但CLOSED表保存从起始节点开始的路径节点,OPEN表保存CLOSED表中扩展节点的后续节点,可减少在OPEN表中保存的节点数量,减少计算量和耗时,并通过增加SMOOTH过程以提高路径的平滑度。将算法应用于二维空间环境进行机器人路径规划仿真实验,结果表明,与A~*算法相比,Lambda~*算法能够以增加较少路径长度为前提,大幅降低路径规划的耗时。     

基于动态局部更新体素模型的虚拟加工仿真算法研究

为提高虚拟加工仿真算法的仿真速度和精度,提出一种新的基于动态局部更新体素模型的虚拟加工仿真算法.该算法利用体素节点间的邻接关系,实现虚拟加工仿真的动态局部更新.算法在初始化阶段建立虚拟毛坯的八叉树结构体素模型,并建立任意体素6-邻接关系遍历算法.在虚拟加工几何仿真阶段,利用刀具和毛坯相对运动的时空一致性,从毛坯上一帧已...     

基于启发式机器人路径规划仿真研究

研究路径规划优化选择问题,路径规划一直是工业机器人需要解决的重点技术。为了使机器人的移动目标位姿寻找无碰撞路径,针对传统的A*的路径规划算法对路径规划选择时容易陷入"死循环",而且找到的路径并非最优路径等缺陷。为解决上述问题,提出了一种在原A*算法的基础上改进为新的双向A*递归路径规划算法,首先通过加入搜索方向因子,充分利用硬件资源和并行编程技术,遍历路径中的所有节点,当某一节点前后节点连线上无障碍物时,将延长线路的中间节点删除,从而建立双向A*模型。仿真结果表明,改进后的算法性能优于标准A*算法以及蚁群算法,并使路径选择得到优化。     

基三分层网络中一种基于查表的确定路由算法

路由算法对互连网络的通信性能和并行系统性能的发挥起着重要作用。针对基三分层互连网络，提出一种基于查表的使消息沿两节点间近似最短路径传递的分布式确定路由算法TDRA。该算法充分利用基三分层互连网络的层次特性，其路由表中仅保存各节点的同族节点和部分组的路由信息，路由表所占存储空间小，路由效率高。     

基于边缘块的线段提取方法

为了解决传统直线提取算法中由于梯度信息孤立而造成检测效果不理想的问题,本文提出结合边缘块的连通域信息进行边缘连接的直线提取方法.首先提取图像边缘图,利用边缘点的连通域,建立边缘点标注模型,进行边缘块搜索.然后用邻接矩阵统计边缘块之间的位置信息,采用深度优先搜素算法,得到初始路径.最后利用直线的几何特征作为路径筛选条件,...     

Adaptive iso-planar tool path generation for machining of free-form surfaces

The iso-planar (Cartesian) tool path generation method has been used for several decades. However, it suffers an inherent drawback: in the region where the direction of the surface normal is close to that of the parallel intersecting planes, the intersecting plane intervals have to be reduced because of the influence of surface slopes. This causes redundant tool paths in the associated flatter regions and results in lower machining efficiency. This paper presents an algorithm that overcomes the disadvantage of the iso-planar method while keeping its advantages of robustness and simplicity. In this algorithm, the concept of isophote is applied to partition the surface into different regions. In each region the tool path side steps are adaptive to the surface features. Therefore redundant tool paths are avoided. By applying the region-by-region or global-local machining strategy, the machining efficiency is increased.     

Computing transitive closure on systolic arrays of fixed size

Summary Forming the transitive closure of a binary relation (or directed graph) is an important part of many algorithms. When the relation is represented by a bit matrix, the transitive closure can be efficiently computed in parallel in a systolic array.Here we propose two novel ways of computing the transitive closure of an arbitrarily big graph on a systolic array of fixed size. The first method is a simple partitioning of a well-known systolic algorithm for computing the transitive closure. The second is a block-structured algorithm. This algorithm is suitable for execution on a systolic array that can multiply fixed size bit matrices and compute transitive closure of graphs with a fixed number of nodes. The algorithm is, however, not limited to systolic array implementations; it works onany parallel architecture that can perform these bit matrix operatons efficiently.The shortest path problem, for directed graphs with weighted edges, can also be solved in the same manner, devised above, as the transitive closure is computed. Björn Lisper was born in 1956 in Solna, Sweden. He received the M. Eng. Physics degree in 1980 and the Ph.D. degree in Computer Science in 1987, both from the Royal Institute of Technology in Stockholm. Currently he shares his time between the Royal Institute of Technology and the Swedish Institute of Computer Science. His research interests are mainly in the area of formal methods for deriving efficient parallel implementations of algorithms, including synthesis of fixed hardware structures for specific algorithms and compilation techniques for tightly coupled parallel systems. Dr. Lisper is a member of the European Association for Theoretical Computer Science.     

一种求解最少时间最小费用路问题的算法

针对同时带有弧费用和弧时间的运输网络中最少时间最小费用路的问题,本文提出了一种算法。该算法能高效地求出此类网络中从源节点到目的节点的双目标最短路（最少时间最小费用路）。实例计算表明,该算法是有效的。     

扇形优化Dijkstra算法

Dijkstra算法无数次遍历所有的临时标记结点,无疑成为该算法的一个瓶颈。在分析Dijkstra算法的基础上,结合平面网络的特点,从限制搜索范围和限定搜索方向两方面着手,在扇形区域内寻找最短路径,从而完成对Dijkstra算法的优化。优化算法基于有损算法,抛弃寻找最短路径时概率较小的顶点,直接寻求在方向和位置上趋向终点的顶点。它根据用户给出的起始顶点与目标顶点以及搜索的扇形角度查找最短路径。因此,在优化算法中,频繁遍历的顶点数量大幅度减少,提高了算法的速度和运行效率。     

一个改进的较佳路径求解算法

较佳路径的求解问题事实上是货郎担近似算法的问题。现有算法实质上属于一种经典的单向增长的贪婪法,存在着改进的余地。本文提出一种改进的双向增长的贪婪算法,与经典算法相比,其策略有所增强,因而其结果得到进一步改善,更加接近于理想的Hamilton通路。算法的理论分析和实际测试数据都证实,改进是有效的。     

基于方向导数和B样条小波的图像边缘检测

根据图像边缘及噪声的多尺度传播特性和小波边缘检测的基本原理,提出了一种基于方向导数和三次B样条小波的边缘检测算法。该算法兼顾图像边缘的方向特征和小波基对称、线性相位的特点,较好地解决了边缘提取精度与噪声抑制能力之间的矛盾。通过计算机仿真对该算法进行验证,结果表明该算法不仅能准确地检测出图像边缘,而且能有效地抑制噪声,优于传统的边缘检测算法。     

基于新路由表的双向搜索chord路由算法

针对结构化P2P（Peer to Peer）网络资源高效搜索问题,提出了一种基于新路由表的双向搜索chord路由算法。该算法为解决chord算法路由表中存在着大量冗余信息,查找资源效率低下等缺点,提出了一个新的路由表构造公式。该公式首次加入路由因子概念,充分考虑了网络中节点个数和资源个数对路由表的影响,在不增加路由表项的前提下,不仅基本删除了路由表的冗余项,还实现了chord环的双向查找以减少平均查找跳数。实验仿真结果表明,该算法基本消除了路由表中的冗余信息,减少了平均查找跳数,有效地提高了资源的查找效率。