计算几何：算法设计与分析（第4版） pdf epub mobi txt 电子书 下载 2025

简体网页||繁体网页

☆☆☆☆☆

周培德 著

图书标签:

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

出版社： 清华大学出版社

ISBN：9787302259978

版次：4

商品编码：10843052

品牌：清华大学

包装：平装

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

开本：16开

出版时间：2011-09-01

用纸：胶版纸

页数：608

字数：761000

正文语种：中文

编辑推荐

面对棘手的构造性几何问题，怎么办？
从本书中可以找到有效方法，帮助你排忧解难！
《计算几何--算法设计与分析（第4版）》（作者周培德）系统地介绍了计算几何中的基本概念、求解诸多问题的算法及复杂性分析，概括了求解几何问题所特有的许多思想方法、几何结构与数据结构。

内容简介

《计算几何：算法设计与分析（第4版）》系统地介绍了计算几何中的基本概念、求解诸多问题的算法及复杂性分析，概括了求解几何问题所特有的许多思想方法、几何结构与数据结构。全书共分10章，包括：预备知识，几何查找（检索），多边形，凸壳及其应用，Voronoi图、三角剖分及其应用，交与并及其应用，多边形的获取及相关问题，几何体的划分与等分，路径与回路，几何拓扑网络设计等。
《计算几何：算法设计与分析（第4版）》可作为高等院校计算机、自动化等专业研究生或本科高年级学生的教材或教学参考书，也可供软件开发人员、相关专业科技工作者参考。

作者简介

周培德，1941年生，湖北省武穴市人。1956年毕业于武汉大学数学系。任北京理工大学计算机系教授。
2001年9月退休。长期担任本科生“算法设计与分析”及研究生“计算理论”等课程的教学工作。主要精力集中于计算机算法分析与设计、计算几何等方面的研究。以个人名义在多种学术刊物和全国学术交流会上发表论文60篇，出版学术专著一部、全国统编高等学校教材一部、校"九五"规划研究生教材一部、内部教材八部。主要论著有《计算几何--算法分析与设计》、《算法设计与分析》、《计算中的基本理论与方法》。代表性论文有《求解K-中心问题的快速算法》、《平面散乱点线集三角剖分的算法》、《平面线段集三角剖分的算法》、《连接不相交线段成简单多边形的算法》等。《算法设计与分析》获第三届全国普通高校部级优秀教材一等奖。退休以来，专心从事计算几何及其应用领域的研究工作，为6个课题组，公司设计了20来个算法，在多种期刊上发表学术论文20来篇，提出一批新的问题及解决相应问题的算法。

目录

第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 点□是否在多边形P内
1.1.2 确定点□在平面剖分中的位置
1.1.3 Z□算法(判定点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章 凸壳及其应用
3.1 凸壳的基本概念
3.2 计算平面点集凸壳的算法
3.3 计算平面多边形顶点凸壳的算法
3.4 计算平面多边形链顶点凸壳的算法
3.4.1 概念、算法思想与描述
3.4.2 解释与时间复杂性
3.5 计算平面线段集凸壳的算法
3.6 计算三维空间点集凸壳的算法
3.6.1 基本概念
3.6.2 Z粥算法(三维凸壳)
3.7 时间复杂性低于下界O(nlogn)的凸壳算法
3.8 凸壳的应用
3.8.1 确定任意多边形的凸、凹顶点
3.8.2 利用凸壳求解货郎担问题
3.8.3 凸多边形直径
3.8.4 连接两个多边形成一条回路

第4章 Voronoi图、三角剖分及其应用
4.1 Voronoi图的基本概念
4.2 构造Voronoi图的算法
4.2.1 z□算法(计算平面点集的Voronoi图)
4.2.2 构造最远点意义下Voronoi图的算法
4.3 平面点集的三角剖分
4.3.1 Delaunay三角剖分与多边形内部点集的三角剖分
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.7 Voronoi图与凸壳的关系
4.9.8 Voronoi图的推广
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 点集增(删)点之后的三角剖分

第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 特定射线询问

第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 线锯问题
6.16 多边形(链)的匹配(1)
6.17 多边形(链)的匹配(2)
6.18 构造凸多边形
6.19 具有属性点集的控制区域
6.20 多边形内区域的划分及多边形(点集)中心点的确定
6.21 满足一定条件的多边形划分
6.22 特定条件下凸多边形的缩小与放大

第7章 几何体的划分与等分
7.1 平面上不同类型点集的划分
7.2 多边形内不同类型点集的等分
7.3 平面上不同类型线段集的划分
7.4 平面上不同类型线段集的等分
7.5 平面上不同类型点线集的划分与等分
7.6 链、多边形的划分与等分

第8章 路径与回路
8.1 最短路径
8.1.1 可视图及其构造
8.1.2 Z□算法(寻求网络中任意两点间最短路径的算法
8.1.3 多面体面上任意两点之间的最短路径
8.1.4 货运汽车调度及行驶路径问题
8.2 最短路径问题的变型
8.3 满足一定条件的运动规划
8.4 多边形内点之间的可视图
8.5 多边形内任意两点之间的最短路径
8.6 自主车自动定位及确定行车方向
8.7 迷宫问题
8.8 棋盘上的路径与回路
8.9 选择道路及判定道路的通过能力
8.10 多边形内中心区域的确定

第9章 几何拓扑网络设计
9.1 G(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.8 2-中心问题
9.1.9 k-中心问题
9.1.10 最近对问题(CPP)
9.1.11 所有最近邻近问题(ANNP)
9.1.12 邮局问题(POFP)
9.1.13 寻找具有属性点集的最近点对或点团
9.2 G(E)问题
9.2.1 EMST问题
9.2.2 线段集、点线集的最小生成树
9.2.3 直线最小生成树及其相关问题
9.2.4 欧几里得TSP
9.2.5 欧几里得最大生成树问题(EMXT)
9.2.6 最小生成网络
9.3 G(S，E)问题
9.3.1 欧几里得Steiner最小树问题(ESMT)
9.3.2 直线Steiner最小树问题(RSMT)
9.3.3 求解ESMT问题的算法
9.4 G(□)问题
9.4.1 有障碍物的最大空隙问题(MAX G(□)
9.4.2 多边形集中最大空隙问题
9.4.3 具有障碍物的欧几里得最短路径问题(ESPO)
9.4.4 求解E3中ESPO问题的算法
9.4.5 具有障碍物的Steiner最小树问题(ESMTO)
待解决的问题
算法一览
参考文献
名词索引

前言/序言

现代计算科学的基石：探索算法的奥秘与设计的艺术 在信息技术飞速发展的浪潮中，算法设计与分析的重要性日益凸显，它们是构建高效、可靠、智能计算系统的基石。本书旨在深入浅出地剖析算法的世界，带领读者踏上一段探索计算科学核心魅力的旅程。我们将从最基础的算法概念出发，逐步深入到复杂的数据结构和高级的算法设计范式，并通过严谨的分析方法，揭示算法的性能秘密，为读者打下坚实的理论基础，并培养解决实际问题的能力。 一、算法的本质：清晰的指令，高效的执行 算法，顾名思义，是解决特定问题的一系列明确、有限的指令。理解算法的本质，是掌握计算科学的关键第一步。本书将首先阐释算法的核心要素：输入、输出、明确性、有限性和有效性。我们将通过一系列直观的例子，例如查找、排序、求和等简单问题，来具象化算法的概念。读者将学习如何用伪代码清晰地描述算法步骤，理解算法的逻辑流程，并初步认识到不同算法在解决同一问题时的效率差异。 二、数据结构：组织信息的智慧，算法的载体 算法的效能很大程度上取决于它所操作的数据结构。本书将系统地介绍各种基本和高级的数据结构，以及它们在算法设计中的关键作用。我们将从最基础的数组（Array）、链表（Linked List）、栈（Stack）、队列（Queue）入手，深入理解它们的存储方式、操作特性及其适用场景。 数组： 连续存储的强大，快速访问的优势，以及动态大小的挑战。 链表： 灵活的插入与删除，序列化访问的代价，单向与双向链表的区别。 栈： 后进先出（LIFO）的特性，在函数调用、表达式求值中的应用。 队列： 先进先出（FIFO）的特性，在任务调度、广度优先搜索中的应用。 在此基础上，我们将进一步探索更为复杂和强大的数据结构： 树（Tree）： 分层结构的精妙，二叉树（Binary Tree）、二叉搜索树（Binary Search Tree）、平衡二叉搜索树（如AVL树、红黑树）的构建与操作。我们将详细解析它们如何在保持有序性的同时，实现高效的查找、插入和删除。 图（Graph）： 节点与边的抽象，表示现实世界中的复杂关系。我们将介绍图的各种表示方法（邻接矩阵、邻接表），以及它们在路径查找、网络分析等问题中的应用。 哈希表（Hash Table）： 利用哈希函数实现平均O(1)的查找速度，其原理、冲突解决策略（链地址法、开放寻址法）以及在数据库索引、缓存等场景的应用。 堆（Heap）： 特殊的树形结构，支持高效的最值查找和删除，在优先队列、堆排序中的核心作用。 通过对这些数据结构的深入学习，读者将能理解如何根据问题的特点选择最合适的数据结构，从而为高效算法的设计奠定坚实基础。 三、算法设计范式：解决问题的通用策略 算法设计并非凭空想象，而是建立在一些成熟的设计范式和策略之上。本书将引导读者掌握这些强大的工具，以便能够系统地解决更广泛的问题。 分治法（Divide and Conquer）： 将大问题分解为若干个相似的子问题，递归地解决子问题，然后将子问题的解合并起来得到原问题的解。我们将通过快速排序（Quick Sort）、归并排序（Merge Sort）、二分查找（Binary Search）等经典算法，深入理解分治法的思想和递归的应用。 动态规划（Dynamic Programming）： 解决具有重叠子问题和最优子结构的问题。我们将学习如何通过定义状态转移方程，避免重复计算，从而获得最优解。背包问题（Knapsack Problem）、最长公共子序列（Longest Common Subsequence）、最短路径问题（Shortest Path Problem）等经典问题将帮助读者掌握动态规划的精髓。 贪心算法（Greedy Algorithm）： 在每一步选择局部最优解，希望最终能得到全局最优解。我们将探讨贪心算法适用的条件，并分析其在活动选择问题（Activity Selection Problem）、霍夫曼编码（Huffman Coding）等问题中的应用。 回溯法（Backtracking）： 一种系统搜索问题的算法，当发现当前路径不可能得到解时，就“回溯”到上一步，尝试其他路径。我们将通过解决N皇后问题、数独求解等问题，理解回溯法的搜索策略。 分支限界法（Branch and Bound）： 类似于回溯法，但在搜索过程中，通过限界函数剪枝，排除那些不可能包含最优解的子树，从而提高搜索效率。我们将探讨其在旅行商问题（Traveling Salesperson Problem）等优化问题中的应用。 四、算法分析：度量效率，优化性能 设计出算法只是第一步，理解其性能并进行优化同样至关重要。本书将深入讲解算法分析的方法和技术。 渐进复杂度分析（Asymptotic Complexity Analysis）： 学习使用大O符号（O）、大Ω符号（Ω）和大Θ符号（Θ）来描述算法的时间复杂度和空间复杂度。我们将重点分析常数时间O(1)、对数时间O(log n)、线性时间O(n)、对数线性时间O(n log n)、平方时间O(n^2)等常见复杂度，并理解它们对算法性能的影响。 最坏情况、最好情况与平均情况分析： 理解不同场景下的算法性能表现，以及如何进行平均情况分析（尽管通常更具挑战性）。 递归方程的求解： 学习使用主定理（Master Theorem）等方法求解递归算法的时间复杂度。 实践中的性能考量： 除了理论分析，我们还将讨论实际编程中的性能瓶颈，例如缓存效应、数据局部性等，以及如何通过代码优化来进一步提升算法的执行效率。 五、高级算法与应用：拓展视野，解决前沿问题 在掌握了基础算法设计与分析的理论和方法后，本书还将触及一些更高级的算法主题，以拓展读者的视野，并展示算法在各个领域的强大应用。 图算法的深入探索： 包括最短路径算法（Dijkstra算法、Floyd-Warshall算法）、最小生成树算法（Prim算法、Kruskal算法）、拓扑排序（Topological Sort）等，它们在网络路由、项目管理等领域有着广泛的应用。 字符串匹配算法： KMP算法、Boyer-Moore算法等，用于高效地在文本中查找特定模式。 计算几何基础： 介绍一些基础的计算几何概念和算法，例如凸包（Convex Hull）、点定位（Point Location）等，它们是计算机图形学、机器人学等领域的重要组成部分。 NP完全性理论简介： 了解NP-hard和NP-complete概念，理解一类难以在多项式时间内解决的问题，以及我们如何应对它们。 六、实践出真知：编码实现与案例分析 理论的学习最终需要通过实践来巩固。本书将提供大量的编程练习和实例，鼓励读者将所学的算法和数据结构付诸实践。读者将有机会使用熟悉的编程语言（如Python、Java、C++等）实现各种算法，并对它们的性能进行实际测试和分析。通过解决一系列具有代表性的问题，读者将能更深刻地理解算法的设计思路和分析方法，并逐步培养出独立解决复杂计算问题的能力。 目标读者： 本书适合所有对计算科学感兴趣的读者，包括计算机科学专业的本科生、研究生，以及对算法设计和分析有需求的软件工程师、数据科学家和研究人员。无论您是初学者还是有一定基础的开发者，都能从本书中获得宝贵的知识和启发，为您的计算之旅奠定坚实而有力的基础。 通过本书的学习，您将不仅掌握一套强大的算法设计工具箱，更能培养一种严谨的逻辑思维和解决问题的系统性方法，这对于在日新月异的科技领域不断进取、脱颖而出至关重要。

评分☆☆☆☆☆

作为一名业余的算法爱好者，我一直对计算几何抱有浓厚的兴趣，但常常苦于找不到一本真正“入门友好”但又不失深度的书籍。听说《计算几何：算法设计与分析（第4版）》内容非常详实，但我也担心它是否过于理论化，难以理解。我希望这本书能像一位耐心循循善诱的老师，从最基本的几何概念讲起，循序渐进地引入各种算法。我特别期待书中能够通过生动的例子和图解，将抽象的数学概念变得易于消化。如果书中能对一些经典算法的推导过程进行简化和说明，让我能够真正理解其背后的数学原理，而不是死记硬背，那将是极大的福音。我也希望书中能有一些关于算法复杂度分析的直观解释，让我能明白为什么某个算法会快，而另一个会慢。如果能有一些趣味性的编程挑战或者小项目，让我能够亲手实践，那将更能激发我的学习热情。

评分☆☆☆☆☆

我是一名研一的学生，主攻方向是计算机图形学。计算几何是我的必修课程之一，也是我最感兴趣也觉得最难的部分。老师推荐了《计算几何：算法设计与分析》这本教材，并且已经是第四版了，这说明它肯定经过了长时间的打磨和更新，内容应该是非常成熟和权威的。我目前最需要的是能够帮助我理解抽象概念的清晰解释和直观的图示。我希望能在这本书里找到对诸如多边形布尔运算、Delaunay三角剖分、Voronoi图等核心概念的详尽阐述，并且希望它能提供不同算法的伪代码，方便我理解其实现步骤。此外，我对算法的渐进复杂度分析很感兴趣，希望能通过书中细致的推导，掌握如何分析一个计算几何算法的效率，并理解为什么某些算法比其他算法更优。如果书中还能包含一些练习题，并提供解答的思路，那对我巩固知识将非常有帮助。

评分☆☆☆☆☆

作为一名资深的软件工程师，我一直在寻找一本能够真正帮助我提升工程实践能力的参考书。虽然我处理的项目并非纯粹的计算几何领域，但在很多涉及三维建模、碰撞检测、路径规划等场景时，底层的几何算法知识是不可或缺的。我了解到《计算几何：算法设计与分析（第4版）》在理论深度上非常扎实，这对于我来说尤为重要。我希望能从中学习到严谨的数学证明，理解各种算法背后的逻辑和精妙之处，而不仅仅是停留在“知道有这么个算法”的层面。特别是关于某些算法的优化技巧和实现细节，如果书中能够有所涉及，那将极大地方便我将理论转化为代码。我关注的重点还包括算法的鲁棒性问题，例如浮点数精度带来的误差如何处理，以及在实际工程中如何选择最适合特定场景的算法。我希望这本书能提供一些实用的建议，帮助我避免在实现过程中遇到不必要的麻烦，并最终写出高效、可靠的几何处理代码。

评分☆☆☆☆☆

对于我这样的研究人员来说，一本优秀的计算几何书籍不仅仅是算法的罗列，更重要的是它能够激发新的研究思路。我希望《计算几何：算法设计与分析（第4版）》能够提供一个全面而深刻的视角，让我了解到计算几何的最新发展趋势和前沿问题。我尤其关注书中是否涵盖了一些在现代应用中日益重要的方向，例如大规模点云处理、不规则网格生成、以及与机器学习结合的几何分析方法。我希望它能够不仅仅停留在二维几何，而是深入到三维甚至更高维度的空间。同时，我也期待书中能够探讨一些算法的局限性和开放性问题，这对于我的科研选题非常有启发意义。如果书中能够提供一些算法实现的工具库或者框架的介绍，甚至是一些跨学科的应用示例，比如在生物信息学、机器人学、虚拟现实等领域的应用，那将使这本书的价值得到极大的提升。

评分☆☆☆☆☆

这本书我早就想入手了，尤其听说更新到了第四版，更是让我期待满满。我平时工作涉及一些图形处理和空间数据分析，虽然不直接以算法研究为主，但扎实的理论基础总是能带来事半功倍的效果。之前看过一些零散的资料，总觉得不够系统，也常常因为概念不清而浪费不少时间。这本《计算几何：算法设计与分析》名字就很有分量，算法设计和分析这两个关键词，正是我迫切需要的。我特别希望它能对一些经典问题，比如凸包、三角剖分、点定位、最近点对等，提供清晰的数学推导和详尽的算法描述。同时，我也很关心它在分析部分，是如何讲解这些算法的时间复杂度和空间复杂度的，以及是否有对不同算法进行性能比较的讨论。毕竟，在实际应用中，效率是至关重要的考量因素。我希望这本书不仅能让我理解“是什么”，更能让我明白“为什么”以及“怎么做得更好”。如果其中能穿插一些实际应用的案例，那就更完美了，这样我就可以直接把学到的知识迁移到我的工作场景中去。

评分☆☆☆☆☆

学习三角剖分等计算几何算法买的，很不错……

评分☆☆☆☆☆

看了几页，觉得还可以，慢慢研究

评分☆☆☆☆☆

okokokokokokokok

评分☆☆☆☆☆

非常不错，特价购入！！

评分☆☆☆☆☆

这个算是专业的必读书目了。

评分☆☆☆☆☆

给别人买的

评分☆☆☆☆☆

不错。。。。。。。。。。。。。。|可以。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

评分☆☆☆☆☆

书中的算法大多为作者的算法集成，内容很全面。对于算法这类，最好图多，图的讲解多，才能让初学者学到心头，才能120％发挥其价值

评分☆☆☆☆☆

终于把这本书找到了，好好学习