计算几何：算法设计、分析及应用（第5版） pdf epub mobi txt 电子书 下载 2025

简体网页||繁体网页

☆☆☆☆☆

周培德 著

图书标签:

• 计算几何
• 算法
• 数据结构
• 几何算法
• 图形学
• 计算机图形学
• 算法设计
• 分析
• 应用
• 计算几何学

出版社： 清华大学出版社

ISBN：9787302441601

版次：5

商品编码：12058712

包装：平装

丛书名： 中国计算机学会学术著作丛书

开本：16开

出版时间：2016-10-01

用纸：胶版纸

页数：845

字数：1054000

正文语种：中文

编辑推荐

　　经典中的经典”，“中国计算机教授力作”，“计算几何算法的百科全书

内容简介

　　本书系统地介绍了计算几何中的基本概念、求解诸多问题的算法及复杂性分析，概括了求解几何问题所特有的许多思想方法、几何结构与数据结构。全书共分11章，包括：预备知识，几何查找（检索），多边形，凸壳及其应用，Voronoi图、三角剖分及其应用，交与并及其应用，多边形的获取及相关问题，几何体的划分与等分，路径与回路，几何拓扑网络设计，图形学习、推理及判定等。

　　本书可作为高等院校计算机、自动化等专业研究生或本科高年级学生的教材或教学参考书，也可供软件开发人员、相关专业科技工作者参考。

内页插图

目录

第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通过学习及或运算寻找规律

待解决的问题

算法一览

参考文献

空间之舞：探索计算几何的奥秘 在浩瀚的数字世界中，形状、位置、大小和相互关系构成了我们理解和交互的基础。从精密的工程设计到生动的虚拟现实，从高效的物流规划到逼真的图形渲染，这一切都离不开对空间几何信息的精确处理和高效计算。本书将带您踏上一段引人入胜的旅程，深入探索计算几何这一迷人的领域，揭示其算法设计的智慧、分析的严谨以及在众多前沿应用中的强大力量。 穿越二维平面：点、线、圆的交织 计算几何的根基在于对基本几何元素的理解和操作。想象一下，在二维的纸面上，我们如何准确地判断两个点是否重合？如何计算一条线段的长度？如何判断一个点是否位于一个三角形内部？这些看似简单的问题，在计算机科学的语言中，却需要严谨的算法来解决。 本书将从最基础的几何对象出发，探讨点、线段、射线、多边形以及圆等二维元素的表示方法。我们将学习如何利用代数方法来描述这些几何体，例如点可以用坐标对 $(x, y)$ 表示，线段可以通过两个端点的坐标来定义。在此基础上，我们将深入研究一系列经典而重要的算法。 点的位置判断： 如何判断一个点是在一条直线的左侧、右侧还是线上？这对于理解多边形的内外关系至关重要。我们会学习利用向量的叉积（cross product）来高效地解决这个问题。 线段相交检测： 在设计电路板布局或规划城市交通网络时，我们需要知道两条线段是否会交叉，以及交叉点在哪里。我们将学习如何结合点的位置判断和线段的参数方程，设计出可靠的相交检测算法。 凸包（Convex Hull）： 想象一下，你用一根绳子围绕着一群钉子，拉紧绳子所形成的最小凸多边形，就是这群钉子的凸包。在数据可视化、模式识别和地理信息系统中，凸包算法有着广泛的应用。本书将介绍求解凸包的几种经典方法，如Gift Wrapping（卷包裹法）和Graham Scan（格雷厄姆扫描法），并分析它们的效率。 三角剖分（Triangulation）： 将一个多边形分解成若干个三角形的过程称为三角剖分。在计算机图形学中，对模型进行三角剖分是渲染的基础。我们将探讨不同的三角剖分算法，例如Delaunay三角剖分，它具有良好的“最不尖锐”的特性，在插值和网格生成方面表现出色。 最近点对和最远点对： 在大规模数据集中，找到距离最近或最远的两个点，可以帮助我们理解数据的分布特性，例如聚类分析和离群点检测。我们将学习分治（divide and conquer）策略如何应用于解决这些问题，从而获得高效的算法。 迈向三维空间：挑战与机遇 当我们将视野从二维平面拓展到三维空间时，几何的复杂性呈指数级增长。点、直线、平面、球体、多面体，每一个对象的表示和操作都变得更加微妙。三维模型的构建、碰撞检测、表面重建等任务，都对计算几何提出了更高的要求。 本书将逐步引导您理解三维几何的处理。我们将学习如何表示三维空间中的点、向量和平面，以及如何利用向量运算（点积、叉积）来判断方向、角度和垂直关系。 三维凸包： 与二维类似，三维凸包是在一组点集之外的最小凸多面体。在科学计算和CAD软件中，三维凸包扮演着重要角色。我们将探讨求解三维凸包的算法，例如增量法（incremental method）和分治法。 布尔运算（Boolean Operations） on Polygons/Polyhedra： 在CAD和3D建模软件中，对三维模型进行合并（union）、减去（difference）和交集（intersection）等布尔运算是核心功能。这些运算在三维几何中实现起来具有相当的挑战性，本书将介绍处理多面体布尔运算的基本思路和关键技术。 表面重建（Surface Reconstruction）： 从离散的点云数据中重建出平滑、连续的三维表面，是计算机视觉和逆向工程的关键技术。我们将介绍一些常见的表面重建方法，例如基于Delaunay三角剖分的方法和基于隐式曲面的方法。 算法的深度剖析：效率与严谨 理解几何概念固然重要，但计算几何的核心在于如何高效、准确地实现这些概念。本书将不仅介绍算法的“是什么”，更会深入探讨“为什么”以及“如何”做得更好。 渐进复杂度分析（Asymptotic Complexity Analysis）： 我们将学习如何使用大O表示法（Big O notation）来分析算法的时间复杂度和空间复杂度。理解算法的渐进复杂度，能够帮助我们预测算法在处理大规模数据时的性能表现，并选择最优的算法方案。 分治策略（Divide and Conquer）： 许多计算几何的经典问题，如最近点对问题，都可以通过分治策略得到高效的解决。我们将学习如何将一个大问题分解成若干个小问题，然后递归地解决这些小问题，最后将它们的解合并起来。 扫描线算法（Sweep-line Algorithm）： 扫描线算法是一种强大的解决几何问题的技术。想象一条线在几何区域上“扫描”，在扫描过程中记录和更新信息，从而解决问题。我们将学习扫描线算法如何应用于线段相交问题、多边形覆盖问题等。 随机算法（Randomized Algorithms）： 有时，引入随机性可以简化算法设计，并获得期望上的高效性。本书将介绍一些基于随机化的计算几何算法，例如随机增量法（randomized incremental construction），它在构建凸包等问题上表现出色。 无处不在的应用：计算几何的现实力量 计算几何并非仅仅是理论的探索，它的思想和算法早已渗透到我们生活的方方面面，驱动着无数现代技术的进步。 计算机图形学（Computer Graphics）： 从电影中的特效到电子游戏中的虚拟世界，再到交互式可视化，计算机图形学都依赖于计算几何来渲染三维模型、进行光线追踪、实现动画和碰撞检测。 机器人学（Robotics）： 机器人需要在复杂的环境中导航、规划路径、避开障碍物，这些都离不开对空间几何的精确计算。例如，机器人的运动规划、传感器数据的处理，都广泛应用了计算几何的算法。 地理信息系统（GIS）与空间数据处理： 地图的绘制、地理特征的分析、空间查询、路径规划等GIS的核心功能，都建立在计算几何的基础之上。如何高效地存储、检索和分析大量的地理空间数据，是GIS领域的重要课题。 计算机视觉（Computer Vision）： 图像识别、物体检测、三维重建、运动估计等计算机视觉任务，都与几何信息的提取和分析密切相关。例如，从图像中识别出物体的轮廓，或者从不同视角的照片中重建出物体的三维形状，都需要计算几何的支撑。 科学计算与工程设计： 在航空航天、汽车制造、生物工程等领域，计算几何被用于进行有限元分析、流体力学模拟、药物分子设计等。精确的几何建模和分析是这些复杂模拟的基础。 模式识别与机器学习： 在一些模式识别任务中，例如聚类和分类，我们可能会将数据点映射到高维空间，然后利用几何方法来寻找数据之间的关系和结构。 展望未来：持续演进的计算几何 计算几何是一个充满活力且不断发展的领域。随着计算能力的提升和新问题的出现，新的算法和技术也在不断涌现。例如，处理大规模点云、动态几何、不确定性几何，以及与机器学习的深度融合，都是当前研究的热点。 本书将为您搭建坚实的理论基础，培养严谨的算法思维，并引导您领略计算几何在现实世界中的无限可能。无论您是希望深入理解计算机图形学的底层原理，还是致力于解决复杂三维空间中的问题，亦或是对数据分析和算法设计充满热情，这本书都将是您不可或缺的伙伴，带领您在空间的舞蹈中，发现智慧与创新的火花。

评分☆☆☆☆☆

刚拿到这本书的时候，我还有些犹豫，毕竟计算几何这个主题听起来就有点枯燥，而且我不是一个科班出身的计算机专业学生，我更多的是一种跨界学习的需求，更侧重于实际问题解决。然而，这本书的第一印象却完全颠覆了我的看法。它的内容组织非常有条理，从最基本概念入手，循序渐进，一点点地带领读者进入计算几何的奇妙世界。书中大量的图例和伪代码，让原本抽象的概念变得生动形象，更容易理解。我尤其喜欢书中对算法的讲解方式，不仅仅是给出公式，还会深入分析算法的思路、各种情况的考虑以及性能的权衡，这让我感觉不是在死记硬背，而是在学习一种解决问题的思维方式。对于我来说，虽然不是直接在做图形学或者机器人学的研究，但很多领域都需要处理几何信息，比如地理信息系统（GIS）、医学图像处理、甚至一些数据可视化应用。这本书提供了理解这些应用背后数学和算法原理的钥匙。它并没有一开始就抛出复杂的理论，而是通过一些实际的例子来引出计算几何的概念，比如地图绘制中的线段相交问题，或者游戏中物体碰撞检测的原理。这种从应用出发的讲解方式，对于我这样希望将理论知识与实际问题联系起来的读者来说，非常有吸引力，也极大地激发了我深入学习的兴趣，我感觉这本书能很好地满足我这种“实用派”读者的需求。

评分☆☆☆☆☆

这本书的封面设计就透着一股严谨和厚重感，纯白底色配上深蓝色的标题，让人一看就觉得这是一本值得细细品味的学术著作。拿到手沉甸甸的，纸张的质感也相当不错，印刷清晰，装订牢固，这对于需要频繁翻阅和做笔记的读者来说，是至关重要的。我是一名在读的计算机视觉方向研究生，平时接触最多的就是各种复杂的几何算法，比如点云处理、三维重建等等，这些都离不开扎实的计算几何基础。虽然这本书我还没有深入研读，但仅从目录和章节安排来看，就足以让我对接下来的学习充满期待。它涵盖了从基础的凸包、三角剖分，到更高级的平面分割、 Voronoi图和 Delaunay三角剖分，再到一些更贴近实际应用的领域，比如几何查询、碰撞检测等。我尤其对那些“算法设计、分析及应用”这几个关键词很感兴趣，这意味着它不仅仅会介绍算法本身，还会深入探讨其背后的设计思想、复杂度分析，以及如何在实际项目中落地应用，这正是我们这些实践者最看重的部分。我初步翻阅了几页，里面的数学公式和图示都非常规范，严谨的学术风格扑面而来，这让我对这本书的可靠性和权威性有了初步的信心。我期待着通过这本书，能够建立起一个清晰、系统、完整的计算几何知识体系，为我今后的学术研究和工程实践打下坚实的基础。

评分☆☆☆☆☆

这本书简直就是计算几何领域的“圣经”！我是一名资深的软件工程师，主要负责游戏开发中的物理引擎部分。在工作中，我们经常会遇到各种复杂的几何问题，比如碰撞检测、路径规划、地形生成等等，这些都直接关系到游戏的流畅度和真实感。之前我都是零散地学习一些相关的算法，遇到问题就查资料，效率不高，而且知识体系也比较混乱。拿到这本书后，我感觉像是找到了失散多年的宝藏。它非常全面地涵盖了计算几何的各个方面，从基础的点、线、面到更复杂的曲面和多边形，再到各种重要的算法，如扫描线算法、增量算法、随机算法等等。最让我惊喜的是，书中还详细讲解了如何分析算法的时间复杂度和空间复杂度，以及如何根据实际应用场景选择最优的算法，这对于我们这种需要优化性能的工程师来说，是无价的。我特别喜欢书中对于每一个算法都给出了严谨的数学证明和详细的分析，这让我能够真正理解算法的原理，而不是仅仅停留在“知道怎么用”的层面。而且，书中还提供了丰富的应用案例，让我能够看到这些抽象的算法是如何在实际项目中发挥作用的。读完这本书，我感觉自己的知识体系得到了极大的完善，解决实际问题的能力也得到了显著提升，对于游戏中的各种几何挑战，我现在充满了信心。

评分☆☆☆☆☆

作为一名在机器学习领域深耕多年的研究者，我深知几何概念和算法在很多前沿研究中的重要性，尤其是在三维视觉、点云分析、以及一些图神经网络（GNN）的应用中，计算几何的基础知识是不可或缺的。我一直想找一本能够系统性地梳理计算几何核心概念和经典算法的权威性著作，这本书无疑满足了我的这一需求。它的内容覆盖面非常广，从最基本的几何原语到复杂的计算几何问题，都进行了深入的探讨。我非常欣赏书中对算法的分析，不仅仅停留在理论层面，而是非常注重算法的设计思路、效率分析以及实际应用中的考量。比如，书中对Voronoi图和Delaunay三角剖分在插值、表面重建等方面的应用讲解，让我能够清晰地看到这些抽象概念的实际价值。此外，书中还提到了很多与我研究方向紧密相关的算法，例如最近邻查询、范围查询等，这些都是在处理大规模点云数据时必不可少的工具。我尤其期待书中关于计算几何在机器人学和计算机视觉中的应用章节，这些内容能够为我打开新的研究思路，并为我解决实际的科学问题提供有力的算法支持。这本书的严谨性和全面性，让我对进一步深入研究计算几何领域充满了信心。

评分☆☆☆☆☆

我是一位对计算机图形学充满热情的独立开发者，平时喜欢自己动手制作一些小游戏和交互式应用。虽然我不是科班出身，但对背后的数学和算法原理一直非常好奇。这本书的出版，对我来说简直是一场及时雨。我之前尝试过阅读一些其他的计算几何书籍，但往往因为概念过于抽象或者缺乏直观的例子而感到难以深入。这本书的不同之处在于，它不仅仅是枯燥的理论堆砌，更注重算法的设计思想和实际应用。我尤其喜欢书中用大量的图示来解释复杂的几何概念，这对于视觉型的学习者来说，简直是福音。比如，书中对各种多边形剖分算法的讲解，都有非常直观的图形演示，让我一下子就能抓住算法的核心思想。而且，它不仅仅是介绍算法，还深入探讨了算法的分析过程，比如如何分析它的时间复杂度，以及在什么情况下会遇到一些“边界情况”或者“退化情况”，并且给出了相应的处理方法。这一点对于我这种需要自己实现算法的开发者来说，是非常宝贵的经验。我目前还在学习书中关于计算几何数据结构的部分，比如 kd-tree、 quadtree 等，这些对于优化查询效率非常有帮助，我相信这本书能帮助我更有效地解决我在开发过程中遇到的各种几何相关的技术难题，并为我的项目带来更高级的功能和更好的用户体验。

评分☆☆☆☆☆

很不错的书

评分☆☆☆☆☆

物流态度超好，书也挺不错的，物超所值

评分☆☆☆☆☆

很不错的书

评分☆☆☆☆☆

逗我呢？新书连个包装都木有？而且有点脏了！明显是别人退的书籍！严重差评！！！！

评分☆☆☆☆☆

经典好书，内容丰富，值得学习

评分☆☆☆☆☆

很不错的书

评分☆☆☆☆☆

好书，内容很好！！

评分☆☆☆☆☆

书还不错。算法比较全，很具体，以后做规划会用上！

评分☆☆☆☆☆

这本书略有些深奥，不太详细