Voronoi图研究及其在RP螺旋扫描路径生成中的应用

摘要

计算几何范畴的Voronoi图概念在不同的研究领域得到广泛地应用。通过对Voronoi图的基本理论、定义和参数化平分线公式的分析，以及对两种主要单连通域Voronoi图算法的比较，作者改进了初始化算法和数据结构，得到便于工程应用的单连通域Voronoi算法，并将波阵面传播的思想扩展应用到多连通域的Voronoi图计算，形成新的多连通域问题算法。利用MFC类库的优势，采用面向对象的方法设计和存储相关轮廓段、平分线、内点以及偏置线等，实现了单连通域和多连通域在算法上的一致性和在存储结构上的统一性。 平面多边形边界偏置线的生成策略是螺旋路径规划的关键，也是影响快速激光烧结精度和效率的重要因素。通过对当前该领域的研究成果分析，重点论述了快速成型工艺中基于Voronoi图理论的螺旋扫描路径生成关键技术：提出两个定理并依据这两个定理给出了内点查找算法；区分定义了桥和搭桥两个概念并应用于非单调域和内轮廓情况；为提高算法执行的健壮性提出了几种特殊情况下的相应处理策略。从而解决了螺旋路径规划的一般性问题。 本文提出的Voronoi图算法也可以在图形处理、地理地质、机器人寻径等方面得到应用；提出的螺旋偏置线规划对于激光雕刻、型腔铣削等方面也具有重要的参考价值。

目录

文摘

英文文摘

学位论文版权使用授权书和独创性申明

第一章绪论

1.1 Voronoi图算法研究背景与现状

1.1.1单连通域Voronoi图算法

1.1.2多连通域Voronoi图算法

1.2扫描路径规划的研究背景、现状及研究课题的提出

1.3研究内容及论文结构安排

1.3.1本文研究内容

1.3.1论文结构安排

第二章Voronoi图理论

2.1基本概念

2.2基本定理

2.3 Voronoi图的平分线

2.3.1边界轮廓段表达式

2.3.2平分线表达式

2.3.3平分线的相交

第三章Voronoi图的算法研究及实现技术

3.1 Voronoi图算法

3.1.1主要的单连通域Voronoi图的算法

3.1.2单连通域波阵面传播法

3.1.3新的多连通域的Voronoi图算法

3.2基于MFC的面向对象存储结构

第四章Voronoi图在RP螺旋扫描路径生成中的应用

4.1加工路径生成方法的研究

4.2基于Voronoi图的螺旋路径生成算法

4.2.1内点查找算法

4.2.2偏置量的确定

4.2.3偏置线生成算法

4.3提高算法健壮性的几个相关问题处理

4.3.1平行、同心圆情况下的图形处理

4.3.2圆弧的偏置

4.3.3 Voronoi边求交时重合情况

4.4激光加工工艺中的几个问题

4.4.1激光加工路径的半径补偿问题

4.4.2过烧问题

第五章Voronoi图及轨迹线生成实例

第六章论文工作总结及展望

参考文献

硕士研究生期间发表论文

致 谢