计算几何及应用

章节摘录

　　从多边形的定义可知（见第一章）一个多边形只有一条边界。在本章中，我们称之为单边界多边形。另外，我们将由多条简单的、封闭的、不相交的曲线围成的平面区域称为多边界多边形。这些曲线都是它的边界。一个多边界多边形有多个边界。　　在本章中，我们研究两种类型的多边界多边形：　　1）第一类多边界多边形是一些分离的单边界多边形的集合被另一个单边界多边形所包围，这一个最外面的边界，称之为外边界，其他的单边界多边形都在它的内部，我们称之为内边界。根据单边界多边形的定义，这些多边形内部不存在任何多边形。内边界和外边界之间的部分是我们感兴趣的部分，被称为多边形的关注区域，也是要绘制Voronoi图的区域。　　这类多边界多边形在机械加工中被称为pocket[6]　　（a）中实线部分。在数学上被称为多连通多边形。　　2）第二类多边界多边形可以想象成第一类多边界多边形外边界被不断放大并移向无穷，在平面上留下若干个分离的单边界多边形的集合[图5.2 1（b）中实线部分]。这些多边形的外部并延伸至无限的部分则是我们感兴趣的部分，被称为多边形的关注区域，也是要绘制Voronoi图的区域。　　相应的，对于多边界多边形的Voronoi图也分为两类：　　1）对于第一类多边界多边形，其Voronoi图位于外边界的内部和所有内边界的外部，并将这部分平面区域分割成许多单元。我们将这类多边界多边形的Voronoi图称为第一类Voronoi图。　　2）对第二类多边界多边形，其Voronoi图位于所有边界的外部，并将这部分平面区域分割成许多单元。我们将这类多边界多边形的Voronoi图称为第二类Voronoi图。　　图5.2 1（a）给出了第一类多边界多边形（实线部分）和它的Voronoi图（虚线部分），图5.2 1（b）中给出了第二类多边界多边形（实线部分）和它的Voronoi图（虚线部分）。 　　……

书籍目录

前言
第一章 引论
　1.1 几何基础知识
　1.1.1 基本概念
　1.1.2 几何对偶
　1.2 算法的复杂度
　1.2.1 算法复杂度的度量方法
　1.2.2 排序时间复杂度的下界
　1.3 数据结构
　习题
　参考文献　
第二章 二维凸包
　2.1 凸包的定义
　2.2 极端点和极端边
　2.3 礼品包裹算法
　2.4 凸包的快速算法
　2.5 Graham算法
　2.5.1 基于堆栈的初步算法
　2.5.2 算法实现细节的讨论
　2.5.3 改进的Graham算法
　2.6 下限
　2.7 增量算法
　2.8 分而治之算法
　2.8.1 算法描述
　2.8.2 算法分析
　习题
　参考文献　
第三章 凸包扩展
　3.1 多面体
　3.1.1 引言
　3.1.2 正则多面体
　3.1.3 多面体的欧拉公式
　3.2 三维凸包算法
　3.2.1 礼品包裹算法
　3.2.2 分而治之算法
　3.2.3 增量算法
　3.3 简单多边形的凸包计算
　3.3.1 计算简单多边形凸包的局部凸算法
　3.3.2 简单多边形凸包计算的“陷阱”算法
　3.3.3 简单多边形凸包的Melkman算法
　3.4 凸包的近似算法
　3.4.1 凸包的近似算法
　3.4.2 二维凸包近似算法精度的讨论及其在三维扩展
　3.4.3 近似凸包算法的应用
　3.5 点集的Maxima
　3.6 a-shapes
　3.7 点集的相关几何图结构
　习题
　参考文献　
第四章 Voronoi图
　4.1 基本概念
　4.2 半平面
　4.3 Voronoi图的基本性质
　4.4 Voronoi图的构造方法
　4.4.1 增量法
　4.4.2 分而治之法
　4.4.3 扫描线法
　习题
　参考文献　
第五章 广义Voronoi图
　5.1 加权Voronoi图
　5.1.1 能量图
　5.1.2 加法加权Voronoi图
　5.1.3 乘法加权Voronoi图
　5.1.4 圆与球的Voronoi图
　5.2 高阶Voronoi图
　5.2.1 基本概念
　5.2.2 基本性质
　5.3 最远点Voronoi图
　5.3.1 基本概念
　5.3.2 基本性质
第六章 点集的Delaunay三角剖分
第七章 多边形剖分
第八章 几何搜索
第九章 相交计算
第十一章 可见多边形与可见图
第十二章 机器人运动规划
第十三章 随机算法第十章 排列
第十四章 并行计算几何
第十五章 计算几何研究和应用举例
　　

编辑推荐

　　《计算几何及应用》可作为高等院校计算机及应用数学等学科的本科生、研究生学习计算几何的教材，也可作为从事计算几何研究或应用的其他科技工作者的参考用书。

作者简介

《计算几何及应用》比较全面地介绍了计算几何的基本问题、基础理论和算法。《计算几何及应用》前12章分别介绍了凸包、Voronoi图、三角剖分、多边形剖分、几何搜索、相交计算、排列、可见性计算、路径规划等基本计算几何问题和算法，第13、14章则分别探讨了若干随机和并行的计算几何算法，最后一章给出了关于计算几何的几个实际研究和应用中的例子。《计算几何及应用》在注重介绍计算几何基础理论的同时，也注意介绍简洁、实用和易编程的算法，力求易读、易懂，并使读者能够应用这些理论和算法。为便于消化和理解书中内容，每章末附有习题，以及大量参考文献。

《计算几何及应用》可作为高等院校计算机及应用数学等学科的本科生、研究生学习计算几何的教材，也可作为从事计算几何研究或应用的其他科技工作者的参考用书。

图书封面

---

 计算几何及应用下载

---