计算几何：C语言描述 英文版

　　本书介绍了在计算机图形学、机器人和工业设计领域逐渐兴起的几何算法的设计和实现。计算几何中使用的基本技术包括多边形三角剖分、凸包、Voronoi图、排列、几何查找、运动计划等。虽然自主处理只涉及数学基础知识领域的一部分，但是它却和当今该研究领域的前沿课题相关。因此，专业的程序员会发现本书是一本不可多得的参考书。与上一版相比，本版包括以下几方面的新内容：多边形三角剖分的随机化算法、平面点定位、3D凸包的构造、关于射线段和射线三角的相交算法、多面体中的点等。此外，本版还增加新的一章——“资料来源”，提供了关于各个主题的更详尽的补充资料。本书的一个新特点就是为很多算法增加了可运行的C语言代码，以及如何在现实中实现它们的相关讨论。与第1版相比，本版中的代码有了大幅度的改善（更高效、更稳定），同时本版中还增加了4个新的例程。此外，本书还提供了所有代码的Java版本，读者可以从本书的网站http：//cs.smith.edu/~orourke/）上下载这些免费提供的代码。作者简介：JosephO'Rourke美国马萨诸塞州史密斯学院计算机科学系主任、数学系教授。自1980年从宾夕法尼亚大学获得计算机科学专业博士学位以后，他就一直致力于该领域的教学与研究。研究方向主要为计算几何，除了本书外，他还著有ArtGalleryTheoremsandAlgorithms一书，并与J.E.Goodman一起编写了1000页的HandbookofDiscreteandComputationalGeonetry，此外，还发表了70多篇关于计算机几何方面的论文以及为“计算机几何专栏”写过30多篇文章，由于对该领域的卓越贡献，2001年他儿美国国家基金会来出教师奖。

　　Joseph ORourke 美国马萨诸塞州史密斯学院计算机科学系主任、数学系教授。自1980年从宾夕法尼亚大学获得计算机科学专业博士学位以后，他就一直致力于该领域的教学与研究。研究方向主要为计算几何，除了本书外，他还著有Art Gallery Theorems and Algorithms一书，并与J.E.Goodman一起编写了1000页的Handbook of Discrete and Computational Geonetry，此外，还发表了70多篇关于计算机几何方面的论文以及为“计算机几何专栏”写过30多篇文章，由于对该领域的卓越贡献，2001年他儿美国国家基金会来出教师奖。

Preface
1. Polygon triangulation; 
 1.1 Art Gallery Theorems
 1.2 Triangulation:Theory
 1.3 Area of Polygon
 1.4 Implementation Issues
 1.5 Segment Intersection
 1.6 Triangulation:Implementation
2. Polygon partitioning; 
 2.1 Monotone Partitioning
 2.2 Trapezoidalization
 2.3 Partition into Monotone Mountains
 2.4 Linear-Time Triangulation
 2.5 Convex partitioning 
3. Convex hulls in two dimensions; 
 3.1 Definitons of Convexity and Convex Hulls
 3.2 Naive Algorithms for Extreme Points
 3.3 Gift Wrapping
 3.4 QuickHull
 3.5 Graham's Algorithm
 3.6 Lower Bound
 3.7 Incremental Algorithm
 3.8 Divide and Conquer
 3.9 Additional Exercises
4. Convex hulls in three dimensions; 
 4.1 Polyhedra
 4.2 Hull Algorithms
 4.3 Implementation of Incremental Algorithm
 4.4 Polyhedral Boundary Representations
 4.5 Randomized Incremental Algorithm
 4.6 Higher Dimensions
 4.7 Addditional Exercises
5. Voronoi diagrams; 
 5.1 Applications:Preview
 5.2 Defintions and Basic properties
 5.3 Delaunay Triangulations
 5.4 Algorithms
 5.5 Applications in Detail
 5.6 Medial Axis
 5.7 Connection to Conves Hulls
 5.8 Connection to Arrangements
6. Arrangements; 
 6.1 Introduction
 6.2 Combilnatorics of Arrangements
 6.3 Incremental Algorithm
 6.4 Three and Higher Dimensions
 6.5 Duality
 6.6 Higher_Order Voronoi Diagrams
 6.7 Applications
 6.8 Sdditional Exercises
7. Search and intersection; 
……
8. Motion planning; 
9. Sources. 
Bibliography
Index