一种改进的扫描线多边形填充算法

典型的多边形填充算法主要包括扫描线填充算法和轮廓标志域填充算法,适用于矢量多边形文件的填充算法为扫描线填充算法。论文对原有的多边形扫描线填充算法中的最常用的活性边表和传统扫描线算法进行了分析,结合活性边表和传统的扫描线填充算法的特点,针对复杂的大数据量的多边形填充时间效率较低的问题,提出了一种改进的扫描线多边形填充算法—混合填充算法。该算法采用链表和数组结合的数据结构,形成连续的填充轨迹,有效地提高了时间效率。     

一种改进的种子填充算法

对种子填充算法进行了分析和讨论,并提出一种改进的种子填充算法。由于只记录搜索的路径,并且增加一个空间很小的辅栈,改进的种子填充算法无论是时间还是空间效率都优于传统算法。     

一种针对超大分辨率图像的分割填充算法

针对超大分辨率图像的填充问题提出一种图像分割与基于队列的填充算法。该算法分为图像分割与图像填充2个部分,适用于超大分辨率图像,特别是盆地模拟中的地质图的填充,能克服一般算法在处理大分辨率图像时存在的效率较低、精度不高和资源占用多等缺陷。将该算法应用到盆地模拟工程实践中,取得了较好的填充效果。     

CAD模型截面Voronoi图生成与分层面的等距线填充

目前快速成型中层面制作都是采用行扫描方式进行分层截面的填充，该扫描方式的缺点是：熔丝冷却后产生的收缩对上一层面形成切内应力，使得物理容易产生翘曲变形，另外对于注重外表面的形体，行扫描方式的填充效率较低，为此提出环扫描的填充方式，将VORONOI图的理论引入模型的分层制作，用外轮廓与它的等距线为轨迹完成截面的扫描填充，基于CAD模型分层后的轮廓线及其数据结构，研究了对该区域进行VORONOI图分割的算法，在此基础上规划出它的环扫描轨迹。     

APT-KNN:一种面向分类问题的高效缺失值填充算法

分类是一种常见的数据挖掘方法,而属性值缺失是分类过程中常见的一类数据质量问题,缺失值填充可以减少属性值缺失造成的分类错误。缺失值填充首先要求准确率高,在许多实际应用当中,缺失值填充还必须保证较高的计算效率。提出了一种填充缺失属性值算法APT-KNN,APT-KNN算法利用属性与属性之间的相互关系,根据与目标最相似的几个实例属性值来估计缺失值,以保证填充结果具有更高的准确性,同时设计了一种优化的AntiPole树索引结构,提高了缺失属性值的填充效率。实验表明,APT-KNN方法与现有的几种缺失属性填充方法相比,具有更高的准确率和填充效率。     

一种提高FDM三维打印系统成型效率的算法

目前,FDM三维打印系统制件加工时间比较长,成型效率较低。在权衡加工时间和加工精度的前提下,从切片层厚和层扫描速度控制的角度,提出了一种基于面积变化率的自适应切片层厚控制和基于周长变化率的自适应层扫描速度控制相结合的算法。首先通过二维轮廓面积变化情况计算每层切片数据的层厚值;然后用获得的层厚数据对模型进行切片,得到每层可打印的真实轮廓;最后计算每层二维多边形轮廓的周长,并根据周长的变化情况确定该层合适的扫描速度。实际打印测试结果表明,该算法可以有效降低打印时间,提高成型效率,验证了算法的有效性。     

图形生成填充方式研究

填充是图形生成中关键性的一步，其效率直接影响到整个图形生成系统的性能。本文首先讨论了几种常用的填充算法的局限性，然后提出了一种更有效的凸多边形填充算法，并详细说明了该算法在抗混叠。     

并行栅格扫描填充路径及其规划算法

深入分析快速成形制件翘曲变形的原因后,提出一种全新的扫描填充路径--并行栅格路径及其规划算法.按照这种路径能够近似、并行地完成整个待成形二维平面区域的扫描填充过程,在减小XY向温度梯度的同时,均匀化不同位置材料成形后的冷却收缩约束力,使得不同位置材料的冷却收缩趋于同步和均匀,减小了制件的整体翘曲变形量.实验表明,该算法能够在与其他类型路径的规划算法大致相当的时间和空间复杂度下,获得扫描填充性能更加优越的路径.     

熔焊成型中截面填充算法及软件实现

本文针对熔焊成型的特点,提出了一套适合熔焊成型的截面填充算法。该算法对截面轮廓进行内、外轮廓以及复连通区域和单连通区域的判定,将复连通区域剖分并对单连通区域的单调划分,最后对单调区域进行填充扫描,生成用于熔焊快速成型的数控指令。该截面填充算法采用VC 、OpenGL编程实现,生成的数控代码在成型机床上得到验证。     

基于EFDR编码压缩的非确定位填充算法

针对EFDR编码算法中非确定位填充算法的不足,提出了一种基于EFDR编码压缩算法的非确定位填充算法（ESA）。该算法在填充测试数据中的非确定位时,依据EFDR编码算法的特点,考虑非确定位两边确定位的特征以及非确定位游程自身的特点,对非确定位采用全0填充、全1填充和分块填充三种方法,从而提高了EFDR编码压缩算法的压缩效率并减少了测试时间,同时由于算法仅对测试数据的非确定位进行操作,不会增加测试的物理开销。实验结果表明,在不增加测试功耗和测试硬件开销的情况下,实现了EFDR编码压缩算法压缩效率的提高和测试时间的减少。     

3D打印模型切片及路径规划研究综述

3D打印包括建模、分层切片、路径规划及打印等过程。对3D打印中三维模型数据处理技术核心--切片和路径规划进行综述。介绍3D打印切片软件中针对单材料不同格式的模型切片处理方法,阐明了3D打印中的不同工艺参数影响下的切片算法,包括各类分层切片算法和扫描填充算法,说明每种算法的优缺点,并对现有的单相均质模型切片算法进行对比分析与评价,总结模型切片处理算法的不足,提出改进方向以及未来研究多材料3D打印模型数据处理的切入点。     

高分辨图像区域填充的并行计算方法

针对传统种子填充算法无法充分利用多核处理器性能以及需要人工指定种子的不足,提出基于动态连接和并查集的并行随机种子反向填充算法。将填充任务分为随机种子生成、并行填充、连通区域识别、并行合并与反转步骤,并采用C++和CUDA-C语言分别实现各步骤的CPU和GPU版本。在此基础上,从众多参数组合中选择能发挥硬件最佳性能的参数。实验结果表明,相比传统反向填充算法,并行随机种子反向填充算法能充分利用多核、异构处理器的多线程并行能力,在处理6种不同分辨率的单张和批量图像时获得了平均3.84倍和4.43倍的加速比,其中在处理8 KB高分辨图像时,最高取得6.05倍和7.09倍的加速比。     

基于改进A*算法机器人路径规划研究

针对移动机器人全局路径规划问题提出一种改进A*算法。首先建立栅格地图,基于传统A*算法,进行邻域扩展,将传统8邻域扩展到24邻域,使路径方向具有更多选择,减少不必要的转折点。优化改进A*算法的启发式函数,不再采用单一的曼哈顿距离或者欧几里得距离,将其进行融合改进,剔除路径中冗余节点和多余转折点。最后将全局路径与动态窗口法相结合,结合各自的优点,充分考虑到机器人全局最优路径的同时能安全避开障碍物,得到一条平滑轨迹。各个算法进行验证之后采用ROS平台对系统进行仿真分析,实验结果表明,改进后算法具有更优秀的路径规划能力。     

一种新的基于链码描述的轮廓填充方法

基于链码描述的轮廓填充是图象处理的基础算法,已广泛应用于图象处理、目标分析、图象压缩和计算机图形学中,但存在需要较大的辅助空间和速度较慢的问题。为此,在分析现有算法的基础上,提出了一类基于将整条码链的填充分解成子链填充的算法,这样每条子链都是简单封闭轮廓,与现有算法相比,该算法最大仅需要屯友链等大的辅助空间,而且在非二值图象或码链允许更改时,可不需要任何辅助空间;另外,该算法既不需要排序操作,也不需要用人工交互的方式给出种子,即可通过在子链中根据相邻链码的值来自动给出种子,理论和实验表明,该方法能正确填充任意复杂形状的轮廓,并具有实现方便、速度快、算法简单、易于理解等特点,此快速简单算法具有很大的应用价值。     

A new and fast contour-filling algorithm

Contour filling is one of the most common problems in image and graphics processing. The executing speed of the contour filling is vital, especially for a real-time system. This paper studies the advantages and disadvantages of the conventional filling algorithms, analyzes their original ideas, and proposes a new filling algorithm. The new algorithm presents a very simple idea for finding seeds automatically, and limits the scan within the filling regions. Repeated experiments have proven that with the new algorithm, any complex inner and outer contours can be filled with higher speed.     

A hybrid formation path planning based on A* and multi-target improved artificial potential field algorithm in the 2D random environments

Traditional artificial potential field algorithm for multi-robot formation is easy to fall into local minima and the path planning efficiency is low. To this end, we propose a new method of a hybrid formation path planning based on A* and multi-target improved artificial potential field algorithm (A*-MTIAPF) that provides the optimal collision free path and improves the efficiency for multi-robot formation path planning. The A*-MTIAPF algorithm integrates global path planning and local path planning. The novelties include combining A* with the improved artificial potential field algorithm and dividing multiple virtual sub-target points on the global optimal path of A* planning. Firstly, A* algorithm is used to complete the global path planning. Secondly, the improved artificial potential field algorithm which takes multiple sub-target points divided by the global optimal path as virtual target points is used to complete local path planning by switching target points. In addition, we propose a double priority judgment control algorithm (DPJC) to solve the collision problem among multiple robots by setting double priority to determine the movement order of each robot. Then, a new experimental method is designed by using the randomly generated 2D maps to verify the effectiveness of the proposed method. The results show that our method has advantages that it solves the local minimum problem, improves the efficiency of formation path planning and avoids collision among multiple robots over existing methods.     

A non-retraction path planning approach for extrusion-based additive manufacturing

Notwithstanding the widespread use and large number of advantages over traditional subtractive manufacturing techniques, the application of additive manufacturing technologies is currently limited by the undesirable fabricating efficiency, which has attracted attentions from a wide range of areas, such as fabrication method, material improvement, and algorithm optimization. As a critical step in the process planning of additive manufacturing, path planning plays a significant role in affecting the build time by means of determining the paths for the printing head's movement. So a novel path filling pattern for the deposition of extrusion–based additive manufacturing is developed in this paper, mainly to avoid the retraction during the deposition process, and hence the time moving along these retracting paths can be saved and the discontinuous deposition can be avoided as well. On the basis of analysis and discussion of the reason behind the occurrence of retraction in the deposition process, a path planning strategy called “go and back” is presented to avoid the retraction issue. The “go and back” strategy can be adopted to generate a continuous extruder path for simple areas with the start point being connected to the end point. So a sliced layer can be decomposed into several simple areas and the sub-paths for each area are generated based on the proposed strategy. All of these obtainable sub-paths can be connected into a continuous path with proper selection of the start point. By doing this, separated sub-paths are joined with each other to decrease the number of the startup and shutdown process for the extruder, which is beneficial for the enhancement of the deposition quality and the efficiency. Additionally, some methodologies are proposed to further optimize the generated non-retraction paths. At last, several cases are used to test and verify the developed methodology and the comparisons with conventional path filling patterns are conducted. The results show that the proposed approach can effectively reduce the retraction motions and is especially beneficial for the high efficient additive manufacturing without compromise on the part resistance.     

移动机器人路径规划算法综述

路径规划算法是实现移动机器人自主导航的关键技术。针对移动机器人路径规划技术进行研究,分析各算法的实现机制与原理,并系统性的总结了主流路径规划算法研究现状。根据移动机器人路径规划算法的特点,将路径规划算法分为：传统规划算法、智能规划算法、基于采样的规划算法。基于以上分类,分述近年来的主要研究成果,重点分析各类算法的优缺点。针对移动机器人路径规划算法研究现状,对其未来研究方向进行展望,为移动机器人路径规划大发展提供一定的思路。     

一种移动机器人路径规划新算法

快速搜索随机树（Rapidly-exploring random Tree Star,RRT*）算法在移动机器人实际应用中规划路径在转向部分存在较多的冗余转折点,导致移动机器人在移动转向过程中出现多次停顿与转向,为剔除规划路径中的冗余路径点,提高机器人移动流畅性,提出一种改进的 RRT*算法。算法将局部逆序试连法引入移动机器人路径规划,在确保RRT*算法概率完备性和渐进最优性的前提下,剔除规划路径中的冗余路径节点,使最终路径更加接近最短路径。通过MATLAB仿真实验证明,规划路径平均长度缩短4%,算法耗时缩短35%,改进后的RRT*算法能缩短规划路径且转向部分路径更加平滑。最后,使用改进后的RRT*算法在室内环境下进行移动机器人路径规划实验。实验结果表明：规划路径上无冗余路径点,且移动机器人沿路径移动流畅。