计算几何 算法设计.分析及应用(第5版) 本书特色
本书系统地介绍了计算几何中的基本概念、求解诸多问题的算法及复杂性分析，概括了求解几何问题所特有的许多思想方法、几何结构与数据结构。全书共分11章，包括: 预备知识，几何查找（检索）,多边形,凸壳及其应用,Voronoi图、三角剖分及其应用，交与并及其应用，多边形的获取及相关问题，几何体的划分与等分，路径与回路，几何拓扑网络设计，图形学习、推理及判定等。
本书可作为高等院校计算机、自动化等专业研究生或本科高年级学生的教材或教学参考书,也可供软件开发人员、相关专业科技工作者参考。
计算几何 算法设计.分析及应用(第5版) 内容简介
经典中的经典”，“中国计算机教授力作”，“计算几何算法的百科全书
计算几何 算法设计.分析及应用(第5版) 目录
第0章预备知识
0.1算法与数据结构
0.1.1算法
0.1.2数据结构
0.2相关的几何知识
0.2.1基本定义
0.2.2线性变换群下的不变量
0.2.3几何对偶性
0.3计算模型
第1章几何查找(检索)
1.1点定位问题
1.1.1点q是否在多边形P内
1.1.2确定点q在平面剖分中的位置
1.1.3Z1?3算法(判定点q在哪个三角形的
第0章预备知识0.1算法与数据结构0.1.1算法0.1.2数据结构0.2相关的几何知识0.2.1基本定义0.2.2线性变换群下的不变量0.2.3几何对偶性0.3计算模型第1章几何查找(检索)1.1点定位问题1.1.1点q是否在多边形P内1.1.2确定点q在平面剖分中的位置1.1.3Z1?3算法(判定点q在哪个三角形的算法)1.2判定点集是否在多边形内1.3平面网络的处理与点q的定位1.4平面上链的处理与点q的定位1.5平面上线段的处理与点q的定位1.6判定点是否在多边形内部的新算法第2章多边形2.1凸多边形2.2简单多边形2.3多边形的三角剖分2.4多边形的凸划分2.5对多边形链的监视2.6线段划分多边形2.7凸多边形的内接*大三角形及外切*小三角形〖〗目录〖〗〖3〗〖〗〖〗〖2〗〖〗计算几何——算法设计、分析及应用〖〗第3章凸壳及其应用3.1凸壳的基本概念3.2计算平面点集凸壳的算法3.3计算平面多边形顶点凸壳的算法3.4计算平面多边形链顶点凸壳的算法3.4.1概念、算法思想与描述3.4.2解释与时间复杂性3.5计算平面线段集凸壳的算法3.6计算三维空间点集凸壳的算法3.6.1基本概念3.6.2Z3?8算法（三维凸壳）3.7时间复杂性低于下界O（nlogn）的凸壳算法3.8凸壳的应用3.8.1确定任意多边形的凸、凹顶点3.8.2利用凸壳求解货郎担问题3.8.3凸多边形直径3.8.4连接两个多边形成一条回路3.8.5三维空间中平面群的重建3.8.6构造平面曲线3.8.7某些机型的识别及其他应用第4章Voronoi图、三角剖分及其应用4.1Voronoi图的基本概念4.2构造Voronoi图的算法4.2.1Z′4?1算法（计算平面点集的Voronoi图）4.2.2构造*远点意义下Voronoi图的算法4.3平面点集的三角剖分4.3.1Delaunay三角剖分与多边形内部点集的三角剖分4.3.2平面点集三角剖分的算法4.4平面线段集的三角剖分4.5平面点线集的三角剖分4.6平面点集的伪三角剖分4.7伪三角形的产生4.8三角剖分的表示4.9推广及应用4.9.1*近邻近4.9.2*大化*小角的三角剖分4.9.3*大空圆4.9.4*小生成树4.9.5货郎担问题4.9.6中轴4.9.7Voronoi图与凸壳的关系4.9.8Voronoi图的推广4.9.9有约束的Voronoi图4.9.10线段集的Voronoi图4.9.11关联于多边形的Voronoi图4.9.12点线集的Voronoi图4.9.13点、水平、垂直正交线段集的Voronoi图4.9.14几何数据压缩4.9.15车辆定位导航系统的新定位算法4.9.16调色4.9.17点集增（删）点之后的三角剖分4.9.18点云的处理及相关问题的求解4.9.19点云曲面边界线的提取及相关问题的求解4.9.20关联于圆的Voronoi图4.9.21曲面上点集的三角剖分4.9.22指纹识别算法第5章交与并及其应用5.1线段交的算法5.2多边形的交5.2.1凸多边形交的算法5.2.2星形多边形交的算法5.2.3任意简单多边形交的算法5.3半平面的交及其应用5.3.1半平面的交5.3.2两个变量的线性规划5.4多边形的并5.5凸多面体的交5.6应用5.6.1地图匹配5.6.2地图数据的处理5.6.3线段与凸多面体面的交5.6.4与线段集中线段均相交的直线及其存在区域5.6.5特定射线询问5.6.6水平、垂直边多边形逼近椭圆5.6.7紧致边界5.6.8射线与隐形凸多面体的交第6章多边形的获取及相关问题6.1连接不相交线段成简单多边形(链)6.2红外图像边缘提取6.3提取可见光图像的边缘6.4图像边界点行排列转换为顺序排列6.5数字图像中目标边界的多边形表示6.6包含密集点、线集多边形的获取6.7满足特定条件的多边形划分6.8多边形与多边形链6.9圆弧、直线段组成的多边形顶点凸、凹性的确定6.10多边形放大、缩小及移动6.11带状多边形的处理6.12下料问题(1)6.13下料问题（2）6.14下料问题（3）6.15线锯问题(1)6.16多边形（链）的匹配（1）6.17多边形（链）的匹配（2）6.18构造凸多边形6.19具有属性点集的控制区域6.20多边形内区域的划分及多边形（点集）中心点的确定6.21满足一定条件的多边形划分(1)6.22特定条件下凸多边形的缩小与放大6.23下料问题（4）6.24线锯问题（2）6.25线锯问题（3）6.26线锯问题（4）6.27满足一定条件的多边形划分（2）6.28隐形几何体（线段、多边形、长方体）6.29海洋划界第7章几何体的划分与等分7.1平面上不同类型点集的划分7.2多边形内不同类型点集的等分7.3平面上不同类型线段集的划分7.4平面上不同类型线段集的等分7.5平面上不同类型点线集的划分与等分7.6链、多边形的划分与等分7.7平面上点集划分的推广7.8用圆集划分平面点集7.9正方形内2k个点的划分第8章路径与回路8.1*短路径8.1.1可视图及其构造8.1.2Z8?1算法（寻求网络中任意两点间*短路径的算法）8.1.3多面体面上任意两点之间的*短路径8.1.4货运汽车调度及行驶路径问题8.2*短路径问题的变型8.3满足一定条件的运动规划8.4多边形内点之间的可视图8.5多边形内任意两点之间的*短路径8.6自主车自动定位及确定行车方向8.7迷宫问题(1)8.8棋盘上的路径与回路8.9选择道路及判定道路的通过能力8.10多边形内中心区域的确定8.11迷宫问题（2）8.12网络中路径问题求解的一种搜索方法及回路问题的求解8.13多边形集合中任意两点之间*短路径（含多边形数目*少）8.14点、多边形、多面体之间的*短距离8.15球面上货郎担问题的求解及DNA双螺旋结构长链起源的探索
第9章几何拓扑网络设计9.1G（S）问题9.1.1*大间隙问题（MAX G）9.1.2点集中*大空凸多边形问题及*大空矩形问题9.1.3线段集中*大空凸多边形问题9.1.4点线集中*大空凸多边形问题9.1.5*小覆盖问题（MIN C）9.1.6包含平面点集的*小正方形9.1.7子点集包含问题9.1.82?中心问题9.1.9k?中心问题9.1.10*近对问题（CPP）9.1.11所有*近邻近问题（ANNP）9.1.12邮局问题（POFP）9.1.13寻找具有属性点集的*近点对或点团9.2G（E）问题9.2.1EMST问题9.2.2线段集、点线集的*小生成树9.2.3直线*小生成树及其相关问题9.2.4由单点或线段端点起始的生成树9.2.5欧几里得*大生成树问题（EMXT）9.2.6*小生成网络9.2.7等长线段构成网格的变形9.3G（S，E）问题9.3.1欧几里得Steiner*小树问题（ESMT）9.3.2直线Steiner*小树问题（RSMT）9.3.3求解ESMT问题的算法9.4G（Ω）问题9.4.1有障碍物的*大空隙问题（MAX G（Ω））9.4.2多边形集中*大空隙问题9.4.3具有障碍物的欧几里得*短路径问题（ESPO）9.4.4求解E3中ESPO问题的算法9.4.5具有障碍物的Steiner*小树问题（ESMTO）第10章图形的学习、推理及判定10.1旋转与翻转10.2图形的运算10.3对称性10.4相似性10.5不同子域内的配对及正多边形的构造10.6由边数、子域数、子图位置间关系等寻找规则10.7图形序列及组合10.8由图形组成寻找规则10.9通过学习及或运算寻找规律待解决的问题算法一览参考文献
信息
