维普资讯 http://www.cqvip.com 第３３卷第５期 ２００７年１Ｏ月 兰州理Ｉ工大学学报 Ｖ０１．３３ Ｎｏ．５ Ｊｏｕｒｎａｌ ｏｆ Ｌａｎｚｈｏｕ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ Ｏｃｔ．２００７ 文章编号：１６７３—５１９６（２００７）０５—００９９—０６ 空间点集Ｖｏｒｏｎｏｉ图的海量构造算法及可视化技术 李俊琛，李旭东，刘德学 （兰州理工大学甘肃省有色金属新材料省部共建国家重点实验室，甘肃兰州７３００５０） 摘要：设计空间点集Ｖｏｒｏｎｏｉ图的增量式外存算法以及空间点集Ｖｏｒｏｎｏｉ图的任意平面可视化剖分技术，以“点一线 一面一体，’的空间数据结构为基础，实现在指定空间区域内生成Ｖｏｒｏｎｏｉ图的新方法．提出的算法数据结构清晰合理， 数据交互方案简单有效且无内存，发展的可视化技术可以对空间点集Ｖｏｒｏｎｏｉ图进行任意的平面剖分，实现 了三维Ｖｏｒｏｎｏｉ晶胞集合体内部结构的可视化． 关键词：增量算法；Ｖｏｒｏｎｏｉ图；海量空间点集；可视化技术 中图分类号：ＴＰ３１１．１ 文献标识码：Ａ Ｍａｓｓｉｖｅ ｃｏｎｓｔｒｕｃｔｉｏｎａｌ ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｖｏｒｏｎｏｉ ｄｉａｇｒａｍ ｗｉｔｈ ｓｐａｔｉａｌ ｐｏｉｎｔ ｓｅｔｓ ａｎｄ ｔｈｅｉｒ ｖｉｓｕａｌｉｚａｔｉｏｎ ｔｅｃｈｎｉｑｕｅ ＬＩ Ｊ ｕｎ－ｃｈｅｎ，ＬＩ Ｘｕ—ｄｏｎｇ，ＬＩＵ Ｄｅ－ｘｕｅ （Ｓｔａｔｅ Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ａｄｖａｎｃｅｄ Ｎｏｎ－ｆｅｒｒｏｕｓ Ｍａｔｅｒｉａｌｓ，Ｌａｎｚｈｏｕ Ｕｎｉｖ．ｏｆ Ｔｅｅｈ．，Ｌａｎｚｈｏｕ ７３００５０，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｉｎｃｒｅｍｅｎｔａｌ ｏｕｔ－ｏｆ－ｃｏｒｅ ａｌｇｏｒｉｔｈｍ ｆｏｒ ３Ｄ Ｖｏｒｏｎｏｉ ｄｉａｇｒａｍ ｗｉｔｈ ｓｐａｔｉａｌ ｐｏｉｎｔ ｓｅｔｓ（ＶＤＳＰＳ） ｗａｓ ｄｅｓｉｇｎｅｄ．Ａ ｖｉｓｕａｌｉｚａｔｉｏｎ ｔｅｃｈｎｉｑｕｅ ｆｏｒ ａｎ ａｒｂｉｔｒａｒｙ ｐｌａｎｅ ｉｎｔｅｒｓｅｃｔｉｎｇ ｔｈｅ ｃｏｎｓｔｒｕｃｔｅｄ Ｖｏｒｏｎｏｉ ｄｉａｇｒａｍ ｗａｓ ａｌｓｏ ｉｎｃｌｕｄｅｄ．Ａｎ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｃｏｎｓｔｒｕｃｔｉｎｇ ｔｈｅ Ｖｏｒｏｎｏｉ ｄｉａｇｒａｍ ｉｎ ａ ｄｅｓｉｇｎａｔｅｄ ｒｅｇｉｏｎ ｗａｓ ｉｍｐｌｅｍｅｎｔｅｄ ｂｙ ｍｅａｎｓ ｏｆ“ｐｏｉｎｔ—ｌｉｎｅ－ｐｌａｎｅ－ｓｏｌｉｄ”ｓｐａｔｉａｌ ｄａｔａ ｓｔｒｕｃｔｕｒｅ．Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｐｒｅｓｅｎｔｅｄ ｗａｓ ｔｅｃｈｎｉｃａｌｌｙ ｌｏｇｉｃａｌ ａｎｄ ｖａｌｉｄ，ａｎｄ ｉｔｓ ａｓｓｏｃｉａｔｅｄ ｄａｔａ ｓｔｒｕｃｔｕｒｅ ｗａｓ ｒａｔｉｏｎａｌ ａｓ ｗｅｌ１．Ｍｅａｎｗｈｉｌｅ，ｔｈｅ ｆｏｒｍａｔ ｏｆ ｄａｔａ—ｅｘｃｈａｎｇｅ ｗａｓ ｓｉｍｐｌｅ ａｎｄ ｅｆｆｉｃｉｅｎｔ，ｗｈｉｃｈ ｅｌｉｍｉｎａｔｅｄ ｒｅｓｔｒｉｃｔｉｏｎｓ ｏｎ ｃｏｍｐｕｔｅｒ ｍｅｍｏｒｙ ｓｔｏｒａｇｅ．Ｔｈｅ ｄｅｖｅｌｏｐｅｄ ｖｉｓｕａｌｉｚａｔｉｏｎ ｔｅｃｈｎｉｑｕｅ ｃｏｕｌｄ ｔｒｅａｔ ａｎｙ ｏｆ ｒａｎｄｏｍ ｐｌａｎｅ ｔｈａｔ ｉｎｔｅｒｓｅｃｔｅｄ ｔｈｅ ３Ｄ Ｖｏｒｏｎｏｉ ｄｉａｇｒａｍ ｓｈｏｗｉｎｇ ｖｉｓｕａｌｌｙ ｔｈｅ ｉｎｔｅｒｎａｌ ｓｔｒｕｃｔｕｒｅ ｏｆ ｔｈｅ ３Ｄ Ｖｏｒｏｎｏｉ ｄｉａｇｒａｍ ａｓ ａ ｒｅｓｕｌｔ． Ｋｅｙ ｗｏｒｄｓ：ｉｎｃｒｅｍｅｎｔａｌ ａｌｇｏｒｉｔｈｍ￣ｖｏｒｏｎｏｉ ｄｉａｇｒａｍ；ｍａｓｓｉｖｅ ｓｐａｔｉａｌ ｐｏｉｎｔ ｓｅｔｓ；ｖｉｓｕａｌｉｚａｔｉｏｎ ｔｅｃｈｎｉｑｕｅ Ｖｏｒｏｎｏｉ图是计算几何学科一个关于空间划分 的重要数据结构［１］，多年来，平面点集的Ｖｏｒｏｎｏｉ图 已经广泛地应用在科学研究与工程实际中［２ ］．随 着计算机技术的普及和发展，空间点集Ｖｏｒｏｎｏｉ图 的应用也越来越受人们的重视． 间数据交互的增量算法，算法的时间复杂度为 ０（ 。），有效实现了数以万计三维Ｖｏｒｏｎｏｉ晶胞集 合体的构造．在算法构造的过程中，提出在用户指定 空间区域构造Ｖｏｒｏｎｏｉ图的方法，处理计算误差可 能产生的“裂缝”．为了显示三维Ｖｏｒｏｎｏｉ晶胞集合 体的内部构造，本文还介绍一种可视化技术，对三维 Ｖｏｒｏｎｏｉ晶胞集合体的内部构造进行任意平面的可 视化剖分． 实验证明，三维情况下Ｖｏｒｏｎｏｉ图的几何信息 数据结构比较复杂，设计用三个三重嵌套结构体数 组处理数据的交互、拓扑关系的表达，可以使程序清 晰易读，同时，结构体数组能够成块存储几何信息数 据，避免了信息的混乱与冲突．在此基础上，与构造 海量平面点集Ｖｏｒｏｎｏｉ图类似，设计基于硬盘上的 外部文件为存储空间、动态实现程序与外部文件之 收稿日期：２００６～１０—１０ 基金项目：国家自然科学基金（５０５７１０４２） 作者简介：李俊琛（１９８１一），男，甘肃合作人，博士生 １ Ｖｏｒｏｎｏｉ图的定义 ’ 设Ｐ一（Ｐ－，Ｐｚ，…，Ｐ ）ｍＲ。是三维欧氏空间内 的 个点，ｄ（Ｐ，Ｐｉ）为Ｐ和Ｐ 问的欧几里德距离， 将由 （Ｐｉ）一ｎ（Ｐ∈Ｒ。ｆｄ（Ｐ，Ｐ ）＜ｄ（Ｐ，Ｐ ））所 给出的对空间的分割称为以Ｐ一（Ｐ－，Ｐｚ，…，Ｐ ）ｃ Ｒ。为空间点集的Ｖｏｒｏｎｏｉ图， （ ）（ 一１，２，…， ） 维普资讯 http://www.cqvip.com ・１００・ 兰州理工大学学报 第３３卷 为Ｖｏｒｏｎｏｉ多面体，简称Ｖｏｒｏｎｏｉ晶胞，Ｐｉ（ 一１，２， ，７２）称为Ｖｏｒｏｎｏｉ晶胞的生成子． …２构造海量空问点集Ｖｏｒｏｎｏｉ图的增 量算法 ２．１数据结构与数据存储 三维情况下的数据结构与数据存储与二维情况 相类似，这里简单介绍一下三个三重嵌套结构体数 组所包含的信息． ， １）嵌套结构体数组ｆｉｌｅ１： ①ｆｉｌｅ１．Ｐｏｌｙｈｅｄｒｏｎ—Ｏｒｄｅｒ；多面体的序号． ②ｆｉｌｅ１．Ｆａｃｅ＿Ｎｕｍ；此多面体上面的个数． ③ｆｉｌｅ１．Ｎｕｃｌ＿Ｘ，ｆｉｌｅ１。Ｎｕｃｌ—Ｙ，ｆｉｌｅ１．Ｎｕｃｌ—Ｚ； 此多面体的生成子坐标． ④ｆｉｌｅ１．Ｐｏｌｙｇｏｎ［／］．Ｆａｃｅ—Ｏｒｄｅｒ；此多面体中 第ｉ个面的序号（如图１ａ中厂１，厂２，…， 厂８）． ⑤ｆｉｌｅ１．Ｐｏｌｙｇｏｎ［－ｉ］．Ｅｄｇｅ—Ｎｕｍ；此多面体中 第ｉ个面的边数． ⑥ｆｉｌｅ１．Ｐｏｌｙｇｏｎ［ ］．Ｍａｒｋ—Ｘ，ｆｉｌｅ１．Ｐｏｌｙｇｏｎ ［ Ｍａｒｋ＿ｙ，ｆｉｌｅ１．Ｐｏｌｙｇｏｎ［ｉ］．Ｍａｒｋ—ｚ；此多面体 中第ｉ个面的中心点坐标． ⑦ｆｉｌｅ１．Ｐｏｌｙｇｏｎ［－ｉ］．Ｖｅｒｔｅｘ［ｊ］．Ｘ，ｆｉｌｅ１．Ｐｏｌｙ— ｇｏｎ［／］．Ｖｅｒｔｅｘ［ｊ］．Ｙ，ｆｉｌｅ１．Ｐｏｌｙｇｏｎ［ｉ］．Ｖｅｒｔｅｘ￣ｊ］． ｚ；此多面体中第ｉ个面上第 个顶点的坐标． ２）嵌套结构体数组ｆｉｌｅ２： ①ｆｉｌｅ２．Ｐｏｌｙｈｅｄｒｏｎ＿Ｏｒｄｅｒ；多面体的序号． ②ｆｉｌｅ２．Ｐｏｌｙｇｏｎ—Ｅｄｇｅ［，－ｉ］．Ｆａｃｅ—Ｏｒｄｅｒ；此多 面体中第ｉ个面的序号． ③ｆｉｌｅ２．Ｐｏｌｙｇｏｎ＿Ｅｄｇｅ［ｉ］．Ｂｏｕｎｄａｒｙ［ｊ］．Ｅｄｇｅ —Ｏｒｄｅｒ；此多面体中第 个面上第 条边的序号（如 图１ａ中．厂１面周围ｓ１，ｓ２，…，ｓ７边）． ④ｆｉｌｅ２．Ｐｏｌｙｇｏｎ—Ｅｄｇｅ［／］．Ｂｏｕｎｄａｒｙ［ｊ］．Ｘ１， ｆｉｌｅ２．Ｐｏｌｙｇｏｎ—Ｅｄｇｅ［ ］．Ｂｏｕｎｄａｒｙ［力．ｙ１，ｆｉｌｅ２． Ｐｏｌｙｇｏｎ＿Ｅｄｇｅ［ｉ］．Ｂｏｕｎｄａｒｙ［ｊ］．Ｚ１；此多面体中第 ｉ个面上第Ｊ条边的起点坐标。 ⑤ｆｉｌｅ２。Ｐｏｌｙｇｏｎ—Ｅｄｇｅ［／］：Ｂｏｕｎｄａｒｙ［ｊ］．ｘ２， ｆｉｌｅ２．Ｐｏｌｙｇｏｎ—Ｅｄｇｅ Ｅｌｉ．Ｂｏｕｎｄａｒｙ［力．ｙ２，ｆｉｌｅ２。 Ｐｏｌｙｇｏｎ＿Ｅｄｇｅ［－／］．Ｂｏｕｎｄａｒｙ［ｊ］． ；此多面体中第 ｉ个面上第 条边的终点坐标． ３）嵌套结构体数组ｆｉｌｅ３： ①ｆｉｌｅ３．Ｐｏｌｙｈｅｄｒｏｎ＿Ｏｒｄｅｒ；多面体的序号。 ② ｆｉｌｅ３．Ｆａｃｅ—Ｐｏｌｙｈｅｄｒｏｎ［ｉ］。Ｆａｃｅ—Ｏｒｄｅｒ；此 多面体中第 个面的序号。 ③ｆｉｌｅ３．Ｆａｃｅ—Ｐｏｌｙｈｅｄｒｏｎ［ｉ］．Ｆａｃｅ—Ｍａｒｋ；此 多面体中第ｉ个面的属性 界面或内部面）． （ｂ） 图１三维Ｖｏｒｏｎｏｉ晶胞结构示意图 Ｆｉｇ．１ Ｓｃｈｅｍａｔｉｃ ｄｉａｇｒａｍ ｏｆ ａｇｇｒｅｇａｔｅ ｃｏｎｓｉｓｔｉｎｇ ｏｆ ３Ｄ Ｖｏｒｏｎｏｉ ｃｅｌｌｓ ④ｆｉｌｅ３．Ｆａｃｅ＿Ｐｏｌｙｈｅｄｒｏｎ［－ｉ］．Ａｓｉｄｅ—Ｐｏｌｙｈｅｄ－ ｒｏｎ＿Ｏｒｄｅｒ；此多面体中第 个面外侧多面体的序号 （如图１ｂ中－厂１面为Ｖ（Ｐ ）的第１个面，它的外侧多 面体为 （Ｐ２））． ⑤ｆｉｌｅ３．Ｆａｃｅ—Ｐｏｌｙｈｅｄｒｏｎ［－／］．Ｅｄｇｅ—Ｆａｃｅ［ｊ］． Ｅｄｇｅ＿Ｏｒｄｅｒ；此多面体中第 个面上第 条边的序 号． ⑥ｆｉｌｅ３。Ｆａｃｅ—Ｐｏｌｙｈｅｄｒｏｎ［／］．Ｅｄｇｅ—Ｆａｃｅ［ｊ］． Ａｓｉｄｅ＿Ｆａｃｅ＿Ｏｒｄｅｒ；此多面体中第ｉ个面上第 条 边相邻的面的序号（如图１ａ中－厂１面Ｓｓ，Ｓ ，Ｓ 各边 相邻的面的序号为厂５，厂４，厂２）． ２．２面的法向量与顶点排序 构造二维Ｖｏｒｏｎｏｉ图时，每一个Ｖｏｒｏｎｏｉ晶胞 的顶点在右手系中都是按逆时针方向排序的．显然， 在三维情况下也要解决Ｖｏｒｏｎｏｉ晶胞每个面上顶点 的排序问题，这是构造空间点集Ｖｏｒｏｎｏｉ图的一个 核心问题．解决这个问题的思路是：首先，需要区分 平面的两个侧面．面向物体内部的一面为“内侧”面， 维普资讯 http://www.cqvip.com 第５期 李俊琛等：空间点集Ｖｏｒｏｎｏｉ图的海量构造算法及可视化技术 面向物体外部的一面为“外侧”面．然后，使得空间中 的每一个Ｖｏｒｏｎｏｉ晶胞，当观察者从晶胞外向晶胞 内看时，晶胞的每个“外侧”面上的顶点都是按逆时 针方向排序的（如图ｌａ）．具体处理的方法如下： 不再赘述．但是生成随机点 后怎样构造Ｖ（Ｐ ）， Ｖ（Ｐ ）生成后怎样修改邻近受影响晶胞，这两个构 造空间点集Ｖｏｒｏｎｏｉ图过程中出现的问题较为复 杂． 在图２中Ｐ一点落在Ｖ（Ｐ０Ｉｄ）（ （Ｐ。Ｊｄ）为整个 立方体）晶胞内，用点Ｐ一与点ＰｏＩｄ之间垂直平分面 １）构造Ｖ（Ｐ ）的子程序流程． 步骤１：判断点 落在哪个Ｖｏｒｏｎｏｉ晶胞 的方程与Ｖ（Ｐ ｏＩ ）的各面依次作交线，在，１面上作 出 、ｗ。两点之后，以拓扑关系找到ｗ 所在边相 邻的面．厂５，由于ｗ 所在的边为，－面与，５面的公 共边，在．厂５面上必有一条交线，做出Ｗｓ点．以 Ｖ（Ｐ ）内（做Ｐ 与先前所有生成子之间的距离，则 Ｐｉ落人与Ｐ 距离最小的生成子所在的Ｖｏｒｏｎｏｉ晶 胞内），从外部文件读取此晶胞数据到内存． 步骤２：在此晶胞内做出Ｐ 与Ｐ 的垂直平分 Ｐ—Ｐ。 为垂直平分面的法向量，判断ｗ 与 ｗ 的差积是否与垂直平分面的法向量同向，如 果方向相同，则符合顶点按逆时针方向排序的原则， 按ｗ。—ｗｚ的顺序排列顶点；反向则以ｗｚ—ｗ 进 行排序．图２所示为同向的情况，所以Ｗ 一Ｗｚ为 正确的排序，以拓扑关系找到ｗｚ所在边相邻的面 ．厂３，在．厂３面上做出下一顶点Ｌ。，用同样的方法做出 顶点Ｌ 、Ｌ 、Ｌ 直到回到Ｗ 点，这样 （Ｐ一）的第 一个面构造完成，并且对于 （Ｐ一）来说，第一面 “外侧”面上的顶点都是按逆时针方向排序的．在修 改Ｖ（Ｐ。Ｉｄ）时，对这个Ｐ—Ｐ。 的垂直平分面生成的 新面，各顶点的排序与它们在 （Ｐ一）上的排序恰 恰相反，即这个公共面对Ｖ（Ｐ。 ）来说顶点依次是 Ｌ６，Ｌ５，…，Ｌ１． 图２ Ｖｏｒｏｎｏｉ晶胞的一个面上的顶点的排序与该面的 法向示意图 Ｆｉｇ．２ Ｓｃｈｅｍａｔｉｃ ｄｉａｇｒａｍ ｏｆ ｓｅｑｕｅｎｔｉａｌ ａｒｒａｎｇｅｍｅｎｔ ｏｆ ｖｅｒｔｅｘｅｓ ｓｉｔｔｉｎｇ ｉｎ ａ ｐｌａｎｅ ｏｆ ａ Ｖｏｒｏｎｏｉ ｐｏｌｙｈｅｄｒｏｎ ｎａｄ ａｌｏｎｇ ｎｏｒｍａｌ ｄｉｒｅｃｔｉｏｎ ｔｏ ｐｌａｎｅ ２．３算法具体步骤 构造空间点集Ｖｏｒｏｎｏｉ图增量算法 。 的主流 程图与构造平面点集Ｖｏｒｏｎｏｉ图增量算法的主流程 图［】ｏ］完全相同，算法具体步骤也是类似的，这里就 面为Ｖ（Ｐ ）的第一面，此面一定是内部面． 步骤３：由于 （Ｐｉ）第一面的各新边分别在 Ｖ（Ｐ ）的各面上，通过拓扑关系可以找到以这些面 为公共面的其他Ｖｏｒｏｎｏｉ晶胞，这些晶胞内同样能 做出Ｖ（Ｐ ）的一个面，循环做出这些内部面． 步骤４：检测六个边界面备用结构体数组中是 否存储有边界线段，如果存在这样的线段，作出相应 边界上的面． 步骤５：检测六个边界面是否有被包含的情况， 如果有，做出相应的包含面． 步骤６：所有Ｖ（Ｐ ）的面做完之后，确定拓扑关 系． ２）修改邻近受影响的Ｖｏｒｏｎｏｉ晶胞子程序流 程． 步骤１：从第一个邻近受影响晶胞 （ ，）开 始，从外部文件定位读取受影响晶胞数据到内存． 步骤２：修改ｖ（Ｐ ，）数据，以Ｐ 与Ｐ ，的垂直 平分面为ｖ（Ｐｋ￣）第一面． 步骤３：循环修改与 （Ｐ ，）第一面相交的原 Ｖ（Ｐｇ）各面为新Ｖ（Ｐ ，）面． 步骤４：追加在 （Ｐ ）第一面上方的原 （ ，） 各面为新 （ ｒ）面． 步骤５：新 （Ｐｖ）做完之后，确定拓扑关系，文 件重新定位到原Ｖ（Ｐｇ）位置，用内存中已修改数据 覆盖原Ｖ（Ｐｅ）数据． 步骤６：读取下一个邻近受影响晶胞数据进行 修改，直到所有受影响晶胞数据修改完毕． ２．４在指定空间区域内生成Ｖｏｒｏｎｏｉ图 以立方体空间区域为例，将立方体空间的六个 边界面分别标识为ｅｄｇｅ＿ｆａｃｅ１，ｅｄｇｅ—ｆａｃｅ２，…，ｅｄｇｅ —ｆａｃｅ６（如图３ａ所示）． １）多面体一面或几面在边界面上的处理． 在逐面构造Ｖｏｒｏｎｏｉ晶胞的过程中，如果内部 面与某边界面相交，就肯定有晶胞的一个面落在此 边界面上．如图３ａ中构造Ｖ（Ｐ。）时，已构造内部面 维普资讯 http://www.cqvip.com ・１０２・ 兰州理工大学学报 第３３卷 ｆ 与边界面ｅｄｇｅ＿ｆａｃｅ４相交于线段Ｓ ，这时将ｓ 的 两端点坐标暂时存放在对应于此边界面的备用结构 如图３ｂ中，先以备用结构体数组ｒｅｓ—ｃａｓｅ４［Ｏ￣ 中的线段Ｓ 为．厂３的第一边，然后判断Ｓ 的终点是 否落在边界面的某边界线上，可见Ｌｚ落在边界线ｚ ＝体数组ｒｅｓ＿ｃａｓｅ４［０］．砌１一ｚ，ｒｅｓ＿ｃａｓｅ４［Ｏ￣．砌１一Ｙ，ｒｅｓ —ｃａｓｅ４［０］．砌１一 ，ｒｅｓ—ｃａｓｅ４［０］．砌２一ｚ，ｒｅｓ—ｃａｓｅ４ ［０］．砌２一Ｙ，ｒｅｓ—ｃａｓｅ４［－Ｏ￣．７；Ｕ２一 中，继续做内部面， 另一内部面．厂２与边界面ｅｄｇｅ＿ｆａｃｅ４相交于线段Ｓｚ， 同样将ｓ 的两端点坐标存放在ｒｅｓ—ｃａｓｅ４［１］．砌 一 １ ０００， 一１ ０００上，从ｒｅｓ—ｃａｓｅ４［－ｉ￣中检索是否还 有其他存储线段的起点也落在这条边界线上，如果 没有，找到此边界线的终点Ｌ。，以Ｌｚ 为．厂３的第二 条边，再以Ｌ 为起点，在边界线ｚ：１ ０００，ｙ＝Ｏ上， ｃａｓｅ４［１］．砌１一Ｙ，ｒｅｓ—ｃａｓｅ４［１］．Ｗｌ— ，ｒｅｓ— ｃａｓｅ４［１￣．Ｗ２ Ｘ，ｒｅｓ＿ｃａｓｅ４［－Ｏ￣．Ｗ２一Ｙ，ｒｅｓ＿ｃａｓｅ４［－Ｏ￣． ｚ，ｒｅｓ—从ｒｅｓ＿ｃａｓｅ４［ｉ￣中检索是否还有其他存储线段的起 点也落在这条边界线上，找到Ｓｚ的起点Ｌ 满足条 件，以Ｌ。 为ｌ厂３的第三条边，ｓｚ为 的第四条边， 砌ｚ— 中，所有内部面做完后，检测各边界面备用结 构体中是否存储有边界线段，有则自动转到对此边 界面的处理中，在ｅｄｇｅ—ｆａｃｅ４边界面对应的备用结 构体数组ｒｅｓ—ｃａｓｅ４中存放两条边界线段Ｓ 、Ｓ２．下 面将在ｅｄｇｅ＿ｆａｃｅ４边界面中构造Ｖ（Ｐ。）的ｌ厂３面． 图３逐面构造Ｖｏｒｏｎｏｉ晶胞过程中与边界面相交晶胞 的处理 ３ Ｈａｎｄｌｉｎｇ ａ ｃｅｌｌｓ ｉｎｔｅｒｓｅｃｔｉｎｇ ｗｉｔｈ ｂｏｕｎｄａｒｉｅｓ ｉｎ ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｃｏｎｓｔｒｕｃｔｉｎｇ ａ Ｖｏｒｏｎｏｉ ｐｏｌｙｈｅｄｒｏｎ ｏｎｅ ｐｌａｎｅ ｂｙ ａｎｏｔｈｅｒ ．厂３面构造完成．在构造类似面的过程中如果有存储 线段的终点落在边界面的某边界线上，情况就会复 杂，否则，只要以线段的终点坐标在备用结构体数组 中检索其他以此点为起点的线段，依次连接这些线 段就能做出此Ｖｏｒｏｎｏｉ晶胞落在边界面上的面了． 图３ａ中，Ｖ（Ｐ。）的面，４在ｅｄｇｅ—ｆａｃｅ２上，对应 于它的备用结构体数组为ｒｅｓ—ｃａｓｅ２；面．厂５在ｅｄｇｅ＿ ｆａｃｅ３上，对应于它的备用结构体数组为ｒｅｓ—ｃａｓｅ３； 面，６在ｅｄｇｅ＿ｆａｃｅ６上，对应于它的备用结构体数组 为ｒｅｓ＿ｃａｓｅ６，它们的构造方法与构造．厂３面完全相 同． ２）构造初期，晶胞包含边界面的处理． 在以上处理多面体一面或几面落在边界面上的 问题时，前提是内部面必须与边界面至少有一条相 交线段，而由于空间点是随机生成的，还有可能出现 如图４中 （Ｐａ）包含ｅｄｇｅ—ｆａｃｅ６的情况，由于在 ｅｄｇｅ＿ｆａｃｅ６对应的备用结构体数组ｒｅｓ—ｃａｓｅ６中没 有储存边界线段，用以上方法处理时会认为ｅｄｇｅ一 图４逐面构造Ｖｏｒｏｎｏｉ晶胞过程中晶胞包含边界面的 示意图 Ｆｉｇ．４ Ｓｃｈｅｍａｔｉｃ ｄｉａｇｒａｍ ｃｅｌｌｓ ｉｎｔｅｒｓｅｃｔｉｎｇ ｂｏｕｎｄａｒｉｅｓ ｉｎ ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｃｏｎｓｔｒｕｃｔｉｎｇ ａ Ｖｏｒｏｎｏｉ ｐｏｌｙｈｅｄｒｏｎ ｐｌｎａｅ ｂｙ ｐｌａｎｅ 维普资讯 http://www.cqvip.com
第５期 李俊琛等：空间点集Ｖｏｒｏｎｏｉ图的海量构造算法及可视化技术 ｆａｃｅ６上没有Ｖ（Ｐ。）的品胞面．所以在边界面的问题 上进行如下技术处理． 以图４中构造Ｖ（Ｐ。）为例，在ｅｄｇｅ—ｆａｃｅ２上做 ．邻的其他面 时，由于两面共用一条边，相邻面． 上这一边的数据不用重新计算，直接用 的同一边 数据即可，以此类推．这样构造的单个Ｖｏｒｏｎｏｉ晶胞 面与面之间也是完全封闭的． 厂３面时，此边界面完整地包含了ｅｄｇｅ＿ｆａｃｅ２的一条 边界线 ，所以与 相邻的ｅｄｇｅ＿ｆａｃｅ６有可能成为包 含面，对开关变量ｅｍｂｏｄｙ—ｆａｃｅ６置１，在做厂４面、 厂５面、厂６面时同样也对ｅｍｂｏｄｙ—ｆａｃｅ６置１，在做完 内部面后对各包含面开关变量ｅｍｂｏｄｙ—ｆａｃｅ１，ｅｍ— ｂｏｄｙｆａｃｅ２，…，ｅｍｂｏｄｙ＿—在修改邻近受影响Ｖｏｒｏｎｏｉ晶胞Ｖ（Ｐｋｚ）时，利 用已做出的Ｐ｛与Ｐ ，的垂直平分面数据进行修改， 保证了晶胞与晶胞之间不会出现“裂缝”．这样，在整 个构造空间点集Ｖｏｒｏｎｏｉ图的过程中避免了所有可 能产生的数据误差，得到了正确的空间点集 ｆａｃｅ６进行检测，如果有开 关变量被置１，进而判断与之对应的边界面上是否 Ｖｏｒｏｎｏｉ图． 已做出Ｖｏｒｏｎｏｉ晶胞的一面，已做出则此边界面未 被包含，检测其他边界面，未做出则证明开关变量对 ３实验结果与空间点集Ｖｏｒｏｎｏｉ图的 应的边界面为包含面，此边界面是Ｖｏｒｏｎｏｉ晶胞的 内部构造 一面，在构造Ｖ（Ｐ３）时，检测到ｅｍｂｏｄｙ—ｆａｃｅ６—１， 图５是由本文发展算法所构造的空间点集 并且判断后发现ｅｄｇｅ＿ｆａｃｅ６上未做出Ｖｏｒｏｎｏｉ晶胞 Ｖｏｒｏｎｏｉ图用ＯｒｉｇｉｎＰｒｏ软件实现可视化的效果图． 面，所以ｅｄｇｅ—ｆａｃｅ６为Ｖ（Ｐ。）的一个包含面．本文 图５ａ是三维Ｖｏｒｏｎｏｉ晶胞集合体实体示意图，图 的算法已经完整地考虑了可能出现包含面的各种情 ５ｂ是三维Ｖｏｒｏｎｏｉ晶胞集合体表面示意图． 况，包括一个晶胞有三个包含面的极端情况． 构造空间点集Ｖｏｒｏｎｏｉ图后，并不能明确清晰 ２．５计算误差引起的“裂缝”的处理 地看到其内部结构，这给应用空间点集Ｖｏｒｏｎｏｉ图 在构造Ｖ（Ｐ ）各面的过程中，同样使用二维情 解决实际问题时增加了困难，为了解决这个问题， 况下采用的逐点继承的方法，以保证各面的完全封 程序中设计了对空间点集Ｖｏｒｏｎｏｉ图进行任意可视 闭．各面之间采用类似逐点继承法的逐线继承法，即 化平面剖分的模块． 构造出Ｖ（Ｐ ）的任意一个面 后，在构造与此面相 （ｄ） （ｅ） （ｆ） 图５三维Ｖｏｒｏｎｏｉ晶胞集合体及其内部构造演示 Ｈｇ．５ Ｄｅｍｏｎｓｔｒａｔｉｏｎ ｏｆ ３Ｄ Ｖｏｒｏｎｏｉ ｃｅｌｌｓ ａｎｄ ｉｎｔｅｒｉｏｒ ｓｔｒｕｃｔｕｒｅ ｏｆ ｅａｃｈ ａｇｇｒｅｇａｔｅ 维普资讯 http://www.cqvip.com
兰州理工大学学报 第３３卷 在空间点集Ｖｏｒｏｎｏｉ图构造完成后，程序提示是否 要做任意平面剖分，选择“是”启动剖分模块．以下为 ４结论 本项研究工作运用简单合理的空间数据结构， 设计了基于计算机硬盘文件为运算及存储对象的空 间点集Ｖｏｒｏｎｏｉ图的增量算法，在指定空间区域内 实现了海量三维Ｖｏｒｏｎｏｉ晶胞集合体的构造，同时 设计了对空间点集Ｖｏｒｏｎｏｉ图的任意平面剖分方 法，达到了演示三维Ｖｏｒｏｎｏｉ晶胞集合体内部构造 剖面构造的具体步骤： 步骤１：建立剖面储存文件，提示输人任意剖面 方程的４个参数，即ａｘ＋ｂｙ＋ＣＺ＋ｄ＝０中的４个系 数ａ ｃ、ｄ，判断剖面是否切到Ｖｏｒｏｎｏｉ图，未切到 则提示重新输人剖面参数． 步骤２：剖面与构成Ｖｏｒｏｎｏｉ图区域的１２条边 做交点以确定从哪条边切人，然后判断切点切到哪 个Ｖｏｒｏｎｏｉ晶胞，记录此Ｖｏｒｏｎｏｉ晶胞． 步骤３：在记录晶胞内做出单个晶胞剖面，因为 单个晶胞剖面的各边在相邻两个Ｖｏｒｏｎｏｉ晶胞的公 共面上，找到相邻Ｖｏｒｏｎｏｉ晶胞并在这个晶胞内做 出下一个单个晶胞剖面，以次类推做出完整的剖面， 并将数据存人文件． 步骤４：剖面完成后，看它是否影响到可视边界 面，如果有影响，对可视边界面做相应修改． 运用任意平面剖分的方法可以从任意角度、任 意深度显示空间点集Ｖｏｒｏｎｏｉ图的内部构造，图 ５ｃ、ｄ、ｅ、ｆ是几种剖分的效果图． 表１列出了本文增量式外存算法的执行时间和 硬盘占用量，生成子是随机产生的，实验环境为 ｐｅｎｔｉｕｍ（Ｒ）４ ３．２ＧＨ／３２Ｍ／１６ＯＧＢ，ＷｉｎｄｏｗｓＸＰ／ Ｖｉｓｕａｌ Ｃ＋＋６．０． 表１算法的耗时测试结果 Ｔａｂ．１ Ｔｉｍｅ ｃｏｎｓｕｍｐｔｉｏｎ ｔｅｓｔ ｆｏｒ ｔｈｅ ａｌｇｏｒｉｔｈｍ 的目的，发展的算法与程序的实用性很强． 参考文献： Ｅｌｉ ＡＵＲＥＮＨＡＭＭＥＲ Ｖｏｒｏｎｏｉ ｄｉａｇｒａｍｓ－ａ ｓｕｒｖｅｙ ｏｆ ａ ｆｕｎｄａ－ ｍｅｎｔａｌ ｇｅｏｍｅｔｒｉｃ ｄａｔａ ｓｔｒｕｃｔｕｒｅ［Ｊ］．ＡＣＭ Ｃｏｍｐｕｔｉｎｇ Ｓｕｒ— ｖｅｙｓ，１９９１，２３（３）：３４５－４０５． ［２］ＡＭＥＮＴＡ Ｎ，ＢＥＲＮ眦Ｓｕｒｆａｃｅ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｆｒｏｍ Ｖｏｒｏｎｏｉ ｆｉｌｔｅｒｉｎｇ［Ｊ］．Ｄｉｓｃｒｅｔｅ ａｎｄ ｏＣｍｐｕｔａｔｉｏｎａｌ Ｇｅｏｍｅｔｒｙ，１９９９，２２： ４８１－５０４． ［３］ＴｕＣＥＲＹＡＮ Ｍ，ＪＡＩＮ Ａ Ｋ．Ｔｅｘｔｕｒｅ ｓｅｇｍｅｎｔａｔｉｏｎ ｕｓｉｎｇ Ｖｏｒｏｎｏｉ ｄｉａｇｒａｍｓ［Ｊ］．ＩＥＥＥ Ｔｒｎａｓａ￣ｉｏｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ，１９９０，１２（２）；２１１－２１６． ［４］ＰＯＮＡＭＧＩ Ｍ Ｋ．Ｉｎｃｒｅｍｅｎｔａｌ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｏｃｌｌｉｓｉｏｎ ｄｅｔｅｃｔｉｏｎ ｂｅｔｗｅｅｎ ｓｏｌｉｄ ｍｏｄｅｌｓ［Ｊ］．ＩＥＥＥ Ｔｒｎａｓａｃｔｉｏｎｓ ｏｎ Ｖｉｓｕａｌｉｚａｔｉｏｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ，１９９７，３（１）：５１－６４． ［５］ｓｗＡＮｓＯＮ Ｋ．Ａｎ ｏｐｔｉｍａｌ ａｌｇｏｒｉｔｈｍ ｏｆｒ ｒｏｕｎｄｎｅｓｓ ｄｅｔｅｒｍｉｎａ— ｔｉｏｎ ｏｎ ｃｏｎｖｅｘ ｐｏｌｙｇｏｎｓ口］．Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｇｅｏｍｅｔｒｙ：Ｔｈｅｏｒｙ ＆Ａｐｐｌｉｃａｔｉｏｎｓ，１９９５，５：２２５—２３５． １１６３普雷帕拉塔Ｆ Ｐ，沙莫斯Ｍ Ｌ计算几何导论［Ｍ］．庄心谷译． 北京：科学出版社，１９９０：２２６—２７７． ［７］周培德．计算几何＿算法分析与设计［Ｍ］．北京：清华大学出版 社，２０００：８８—１３２． ［８］ ＣＬＡＲＫＳＯＮ Ｋ Ｌ，ＭＥＨＬＨＯＲＮ Ｋ，ＳＥＩＤＥＬ Ｒ Ｆｏｕｒ ｒｅｓｕｌｔｓ ｏｎ ｒａｎｄｏｍｉｚｅｄ ｉｎｃｒｅｍｅｎｔａｌ ｃｏｎｓｔｒｕｃｔｉｏｎｓ［Ｊ］．Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｇｅｏｍｅｔｒｙ，１９９３，３（４）：１８５—２１２． ［９］ ＫＬＥＩＮ Ｒ，ＭＥＨＬＨＯＲＮ Ｋ，ＭＥＩＳＥＲ Ｓ．Ｒａｎｄｏｍｉｚｅｄ ｉｎｃｒｅ— ｍｅｎｔａｌ ｏｃｎｓｔｕｒｃｔｉｏｎ ｏｆ ａｂｓｔｒａｃｔ Ｖｏｒｏｎｏｉ ｄｉａｇｒａｍｓ［Ｊ］．Ｃｏｍｐｕ－ ｔａｔｉｏｎａｌ Ｇｅｏｍｅｔｒｙ，１９９３，３（３）：１５７－１８４． ［１Ｏ］ 李俊琛，李旭东，任淮辉．海量平面点集Ｖｏｒｏｎｏｉ图的构造算 法［Ｊ］．兰州理工大学学报，２００７，３３（４）：１０２—１０５．
