Voronoi图扫描线算法的三维演示-JunhuiDeng.PDFVIP

Voronoi 图扫描线算法的三维演示 1. 最近Voronoi 图定义及性质 Voronoi 图的定义： 在平面上有N 个独立的站点 ，而Voronoi 图就是把平面分成N 个子区域， 每个站点都拥有自己的子区域，在这个区域中的任何点q 到当前站点的距离比到其他站点的 距离最短。 Voronoi 图的性质： 图一 图二 如图一所示，站点 与 对应的Voronoi 边上的点在 与 的垂直平分线上，以这个点为 圆心的圆能够经过 与 并且圆内无其它站点。 如图二所示，如果一个点是Voronoi 定点，则它至少经过三个站点，并且圆内无其它站 点。 2. Voronoi 图扫描线算法 扫描线算法概述： 1. 通过水平线从上往下扫描站点； 2. 增量构造，跟踪每个站点对应的结构的变化。 扫描线算法待处理事件： 1. 如图三所示，图中的红色弧的序列为海岸线，是我们要跟踪处理的数据结构 （组织成二 叉树）。 图三 2. 图四中到两个站点及扫描线相等的点为分裂点，为海岸线结构中的重要成分，实际上为 二叉树中的内点，而每条弧则为叶子节点。 图四 3. 图五和图六为两个连续的瞬间，图五中间的那条弧即将消失，取而代之的是Voronoi 顶 点。它的两条边为分裂点生长而成。 图五 图六 我们所用的数据结构： 1. 用DCEL 记录Voronoi 图： 图七 Vertex ： 点的辅助信息 bool inner; 表示该点是不是一个内部点（非边界点） vectorint inTris; 记录该点所在的三角形号 vectorint inTrisOrd; 记录该点在相应三角形中的编号（只取0，1，2 ） int startHe; 该点起始半边编号 int endHe; 该点终止半边编号（仅对边界点有效） HalfFace3： 面辅助信息 int he[3]; 记录一个面中三条半边号码 HalfEdge： 基础半边结构 int fv; 起始点 int tv; 终止点 int fn; 面号 int prev; 前一条半边 int next; 后一条半边 int opp; 对面相反的半边 2. 海岸线结构，也即是二叉树。树中的内节点为两条弧相交的分裂点；叶子节点为它们所 代表的弧，与生成弧的站点相对应，注意同一个站点有可能出现两次，被其它弧所割裂。 图八 定义基类 node 内部基类 : interior_node left_index ; 左边节点的叶子编号 right index; 右边节点的叶子编号 叶子基类 :leaf_node cycle_event*: 指向一个圆事件 index: 叶子所在的站点 3. 事件队列，包含所有站点事件和圆事件，它们按照y 坐标排序。 站点事件： 站点事件前 图九 当扫描线刚刚经过一个新的站点，则新的弧被创建 图十 在新的站点上原来的弧被一分为二 图十一 圆事件 图十二 如果一个圆能经过三个以上的站点，并且圆内无其它的站点，则相应的弧消失，转化成 圆的圆心。扫描线与圆的切点为圆事件点。 扫描线算法： 1. Initialize • Event queue Q  all site events