计算几何

内容简介

    本书系统地介绍了计算几何中的基本概念、求解诸多问题的算法及复杂性分析,概括了求解几何问题所特有的许多思想方法、几何结构与数据结构。全书共分11章,包括:预备知识、几何查找、多边形等。

目录

前言 第0章 预备知识 0.l 算法与数据结构 0.l.l 算法 0.1.2 数据结构 0.2 相关的几何知识 0.2.1 基本定义 0.2.2 线性变换群下的不变量 0.2.3 几何对偶性 0.3 计算模型 第1章 几何查找（检索） 1.l 点定位问题 1.l.l 点q是否在多边形P内 1.l.2 确定点q在平面剖分中的位置 l.2 范围查找问题 1.2.1 多维二叉树（k－D树）的方法 l.22 直接存取方法 1.2.3 范围树方法 1.3 判定点集是否在多边形内 1.4 平面中线段集和空间中三角形集的正交询问 l.4.l 吊床询问及推广的吊床询问 l.4.2 正交限制 第2章 多边形 2.1 凸多边形 2.2 简单多边形 2.3 多边形的三角剖分 2.4 多边形的凸划分 第3章 凸壳 3.1 凸壳的基本概念 3.2 计算凸壳的算法（二维） 3.2.1 卷包裹法 3.2.2 格雷厄姆方法 3.2.3 分治算法 3.2.4 Z3-1算法和Z3-2算法 3.2.5 实时凸壳算法 3.2.6 增量算法 3.2.7 近似凸壳算法 3.3 计算凸壳的算法（三维） 3.3.l 基本概念 3.3.2 卷包裹法 3.3.3 分治算法 3.3.4 Z3-3算法 3.3.5 增量算法 3.4 凸壳的应用 3.4.l 确定任意多边形的凸. 凹顶点 3.4.2 利用凸壳求解货郎担问题 3.4.3 凸多边形直径 3.4.4 连接两个多边形成一条回路 第4章 Voronoi图及其应用 4.1 Voronoi图的基本概念 4.2 构造Voronoi图的算法 4.2.l 半平面的交 4.2.2 增量构造方法 4.2.3 分治法 4.2.4 减量算法 4.2.5 平面扫描算法 4.2.6 构造点意义下Voronoi图的算法 4.3 平面点集的三角剖分 4.3.l 平面点集三角刻分的贪心算法 4.3.2 Delaunay三角剖分与多边形内部点集的三角剖分 4.3.3 平面点集三角剖分的算法 4.4 Voronoi图与三角剖分的应用 4.4.l 邻近 4.4.2 化角的三角剖分 4.4.3 空圆 4.4.4 生成树 4.4.5 货郎担问题 4.4.6 中轴 4.4.7 Voronoi图与凸壳的关系 4.4.8 Voronoi图的推广 4.4.9 几何数据压缩 第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 凸多面体的交 第6章 矩形几何 6.l 判定垂直. 水平线段是否相交的算法 6.2 矩形几何问题的特征及解决问题的途径 6.3 矩形并的面积与周长 6.4 矩形并的轮廓 6.5 矩形并的闭包 6.6 矩形并的非平凡轮廓和外轮廓 6.7 矩形的交 6.8 应用举例 第7章 几何体的排列 7.1 基本概念 7.2 确定直线排列的算法 7.3 对偶性 7.4 Voronol图 7.4.1 一维情况 7.4.2 二维情况 7.5 应用 7.5.1 K-邻近 7.5.2 删去隐藏面 7.5.3 特征图 7.5.4 点集的分割 第8章 算法的运动规划 8.l 路径 8.1.l 可视图及其构造 8.1.2 Dijkstra算法 8.2 移动圆盘 8.3 平移凸多边形 8.4 移动杆状机器人 8.4.1 网格分解 8.4.2 收缩方法 8.5 机器人臂运动 8.5.l 可达性 8.5.2 构造可达性 8.6 可分高性 8.6.l 多种可分离住 8.6.2 借助于平移的可分高性 8.6.3 分离问题是NP一难的 8.6.4 模拟河内塔问题 第9章 几何拓扑网络设计 9.1 G（S）问题 9.1.l 间隙问题（MAX G） 9.1.2 覆盖问题（MIN C） 9.1.3 对问题（CPP） 9.l.4 所有邻近问题（ANNP） 9.l.5 邮局问题（POFP） 9.2 G（E）问题 9.2.1 EMST问题 9.2.2 欧几里德TSP 9.2.3 欧几里德生成树问题（EMXT） 9.3 G（S, E）问题 9.3.1 欧几里德Steiner树问题（ESMT） 9.3.2 直线 Steiner树问题（RSMT） 9.4 G（m问题 9.4.l 有障碍物的空隙问题（MAX G（Q）） 9 4.2 具有障碍物的