voronoi图在机械加工路径规划中的应用

《voronoi图在机械加工路径规划中的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第1章引言1．1Voronoi图算法Voronoi图是俄国数学家G．Voronoi[Voronoil908]在研究邻近问题时提出来的，是关于空问邻近关系的一种基础数据结构。在不同的领域，Voronoi图有时也被称为Thiessen多边形、Dirichrit网格、或Wigner--Seitz区域等。平面上一个点集P的Voronoi图是对平面的一个划分，每个分区表示一些点的轨迹，这些点到P的一个元素比到其它元素更近。平面多边形的Voronoi图也是对平面的一种划分．每个分区从属于多边形的一条边，分区内的点到

2、该边比到其它边距离近。在Voronoi图中，被用来划分空间的各个基本图形元素一般被称为对象。最基本的Voronoi图是以平面点集P为对象的Voronoi图，Voronoi图的定义可以推广到二维或三维，也可以推广到二阶或高阶(以两个站点或多个站点为一组划分邻近区域)，也可以进一步推广到对象包括线段或多边形的广义Voronoi图11】【2】【3】【4】。另外，关于移动点的Voronoi图【5】【酊、带权的Voronoi图【7】【8】、以及曲面上的Voronoi图【9】【10】也被人们所研究，并且有着具体的应

3、用背景。随着Voronoi图的定义和算法被广泛传播，Voronoi图的应用领域也在不断扩展。目前，Voronoi图的主要应用领域有：几何形体重构、图像处理与模式识别、物理化学分子生物学、机器人运动规划、机械制造及装饰图案设计等。根据不同的图形元素可将Voronoi图分为三种主要形式，即平面点集的Voronoi图、平面曲线多边形的Voronoi图和空间多面体的Vomnoi图。这些不同形式的Voronoi图分别将平面和空间根据距离的远近关系进行了一定的划分。每个子区域分别从属于一个图形元素，并且分区内的点到

4、该图形元素的欧几里德距离比到其他图形元素的欧几里德距离近。最基本的Voronoi图是以平面点集P为元素的Voronoi图，它将平面划分成凸多边形形状的Voronoi区域，P中的每个元素对应一个这样的区域Ⅵ，使得Ⅵ内的任何点到Pi的欧几里德距离比到其他元素的欧几里德距离近。同理，平面内曲面多边形的Voronoi图是对有限区域的这样一个划分：区域Ⅵ内的点到相应边界轮廓元素I的欧几里德距离比到其他轮廓元素段的欧几里德距离近。本文主要研究Voronoi图在机械加工路径规划第1章引言中的应用。因此，重点放在平面多

5、边形轮廓的Voronoi图生成上。I∞l“1提出利用程序设计方法中的分治∞ivided-Conquer)思想来构造Voronoi图，这是Voronoi图构造算法上的一个里程碑。后来的许多学者在Lee的分治算法基础上逐步设计出了算法时间复杂度为O(nlogn)(n为轮廓C的线段数)的分治算法。1998年，MarthaHeldf”】在其增长算法(IncrementalAlgorithm)的基础上提出了波阵面传播法，形成了一个完全不同于分治算法思想的新的Voronoi图算法。该算法对于单连通域情况的时间复杂度

6、为O(klogh)(k为初始平分线个数，h为初始交点个数)。目前对两种算法思想的应用中大多采用双连接边表结构(Doubly-ConneBtedLisI)存储数据。出于清晰表达整个Voronoi区(VoronoiRegion浦息的目的，这种包含七个数据项的存储结构设计就显得比较复杂了。数据结构的复杂性也将影响该算法在实践中的广泛应用。单连通域Voronoi图算法Voronoi图由Voronoi边组成，Voronoi边是整个平面的区域划分边界，划分后的区域称为Voronoi区，每个对象对应某个区，Voron

7、oi区由到这个对象的欧几里德距离小于到任何其他对象的欧几里德距离的所有点组成，区域的边界由到这个对象的欧凡里德距离等于到其他对象的最小欧几里德距离的所有点组成。区域的边界称为Voronoi边或平分线。Voronoi图包含以下几个基本概念对象(object)、点到对象的欧几里德距离(distance)、边或平分线(bisector)和影响区(conesofinfluence)。Voronoi对象是划分平面的基础，是对点、线段或圆弧等的统称。不同类型的对象构造voronoi图的方法和应用范围都不同。本文研究

8、的对象限于点、线段、圆弧三种。对于内部无孔、洞(或称为孤岛)的单连通域，以直线段、圆弧、优顶点为轮廓边界元素的曲线多边形的Voronoi图的构造算法主要有分治算法[131[14]fll】(Divided．Conquer)、波阵面传播法【15】116】【17](Wavefront-Propagation)。其他还有Fortune(1987)118】提出了具有同样时间复杂度的离散点和线段Voronoi图的扫描线法(Sweepline)等。一系列