《Voronoi图及其应用》在介绍Voronoi图相关概念和性质的基础上，侧重介绍Voronoi图的构造和应用方面的算法。本书主要内容包括离散点集的Voronoi图与Delaunay三角部分、多边形的Voronoi图、约束Delaunay三角部分以及重心Voronoi图的基本概念、性质、构造算法，及其在多边形剖分、几何搜索、多边形求交、可见性计算、路径规划、碰撞检测、骨架计算、文字特征提取、半色调图像生成以及信息可视化等方面的应用。
    《Voronoi图及其应用》可以供从事相关研究的高校教师、科研人员参考，也可作为高等院校计算机相关专业研究生的教材和参考书。本书由杨承磊、吕琳、杨义军以及孟祥旭合著而成。

　　Voronoi图是一种重要的几何结构，也是计算几何领域重要的研究内容之一。 Voronoi图既是一种行之有效的空间剖分和聚类方法，又具有骨架的特性。它按照站点（ sites）集合中元素的最近邻属性将空间划分成许多单元区域。在不同应用背景下，根据生成空间、测量距离以及站点等定义条件的不同，又产生了不同类型的 Voronoi图。这些都使得 Voronoi图在机器人、 CAD、模式识别、虚拟现实、地理信息系统、数据挖掘、生物计算以及无线传感网络等领域得到广泛应用，也是解决碰撞检测、路径规划、可见性计算、骨架计算以及凸包计算等计算几何领域中其他问题的有效工具。
　　本书在介绍 Voronoi图的概念、性质以及一些经典构造算法的基础上，侧重介绍我们近十年的相关研究成果。本书主要内容包括离散点集的 Voronoi图与 Delaunay 三角剖分、多边形的 Voronoi图、约束 Delaunay三角剖分以及重心 Voronoi图的基本概念、性质、构造算法，及其在几何搜索、多边形求交、可见性计算、路径规划、碰撞检测、骨架计算、字符特征提取、骨架匹配与模型分割、半色调图像生成以及信息可视化等方面的应用。
　　本书在注重介绍 Voronoi图相关基础理论的同时，尽量提供一些简洁、实用和易编程的算法，目的是力求让读者易读、易懂，在学习了本书以后，能解决在各种应用领域中遇到的相关问题。
　　本书成果与写作过程得到了国家自然科学基金委项目（ 69873028， 60703028，61070093，61272243，61202147）的持续资助。我们在此表示衷心的感谢。
　　本书由杨承磊、吕琳、杨义军以及孟祥旭合著而成，杨承磊、孟祥旭统稿和审定。由于时间仓促，编者水平有限，书中欠妥和纰漏之处在所难免，恳请读者和同行不吝指正。
　　作者 2013年 5月

    杨承磊，男，于1995、1998、2004年先后获得山东大学计算机应用专业理学学士学位、计算机软件与理论专业工学硕士和博士学位。目前为山东大学计算机科学与技术学院教授。2007年1～7月在香港大学计算机科学系开展合作研究，2010年6月至2011年6月在哈佛大学做访问学者。研究主要围绕工业CAD、文化与自然遗产保护、数字娱乐与远程教育等应用领域，重点开展离散计算几何、人机交互与虚拟现实等方面的理论研究与项目研发工作。先后主持国家自然科学基金3项、国家支撑计划课题1项和省部级项目4项，并作为学术骨干参与完成了国家973计划、863计划等10多项国家级、省部级科研课题，作为骨干成员参与研发出“集成化计算机辅助图案设计与制版系统”等系统软件，获得国家科技进步奖二等奖1项、教育部科技进步奖二等奖1项以及山东省科技进步奖三等奖1项。

第1章 引论 1.1 Voronoi图概述 1.2 相关基础概念第2章 离散点集的Voronoi图及其应用 2.1 定义与性质 2.1.1 定义 2.1.2 性质 2.2 构造方法 2.2.1 逐点插入法生成Voronoi图 2.2.2 扫描线法生成Voronoi图 2.2.3 基于扫描线的逐点插入法生成Voronoi图 2.2.4 基于GPU生成Voronoi图 2.2.5 基于网格生长的Delaunay三角剖分 2.3 应用实例 2.3.1 半色调图像生成 2.3.2 基于GPU的半色调图像生成 2.3.3 带状图像的骨架计算第3章 多边形的Voronoi图及其应用 3.1 定义与性质 3.1.1 定义 3.1.2 性质 3.2 构造方法 3.3 应用实例 3.3.1 两个凸多边形的求交计算 3.3.2 两个分离凸多边形的距离计算 3.3.3 简单多边形中的最短路径计算 3.3.4 复杂多边形中的可见性计算 3.3.5 虚拟室内场景设计与漫游系统第4章 约束Delaunay三角剖分及其应用 4.1 定义与性质 4.2 构造方法 4.3 应用实例 4.3.1 带状图像的骨架计算 4.3.2 在线手写体识别 4.3.3 点定位 4.3.4 简单多边形中的最短路径与可见性计算 4.3.5 复杂多边形中的可见性计算第5章 重心Voronoi图及其应用 5.1 定义与性质 5.1.1 定义 5.1.2 性质 5.2 构造方法 5.2.1 Lloyd方法 5.2.2 MacQueen方法 5.2.3 牛顿法 5.3 应用实例 5.3.1 基于无向图的重心Voronoi图的骨架匹配与模型分割 5.3.2 基于流线重心Voronoi图的流场可视化参考文献