计算几何：C语言描述（英文版·第2版）

　　preface
　　1. polygon trisngulation
　　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 definitions 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 additional exercises
　　5. voranoi diagrams
　　5.1 applications： preview
　　5.2 definitions and basic properties
　　5.3 delannay triangulations
　　5.4 algorithms
　　5.5 applications in detail
　　5.6 medial axis
　　5.7 connection to convex hulls
　　5.8 connection to arrangements
　　6. arrangements
　　6.1 introduction
　　6.2 combinatorics 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 additional exercises
　　7. search and intersection
　　7.1 introduction
　　7.2 segment-segment intersection
　　7.3 segment-triangle intersection
　　7.4 point in polygon
　　7.5 point in polyhedron
　　7.6 intersection of convex polygons
　　7.7 intersection of segments
　　7.8 intersection of nonconvex polygons
　　7.9 extreme point of convex polygon
　　7.10 extremal polytope queries
　　7.11 planar point location
　　8. motion planning
　　8.1 introduction
　　8.2 shortest paths
　　8.3 moving a disk
　　8.4 translating a convex polygon
　　8.5 moving a ladder
　　8.6 robot ann motion
　　8.7 separability
　　9. sources
　　9.1 bibliographies and faqs
　　9.2 textbooks
　　9.3 book collections
　　9.4 monographs
　　9.5 journals
　　9.6 conference proceedings
　　9.7 software
　　bibliography
　　index

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

　　在计算机图形学、机器人和工业设计领域逐渐兴起的几何算法的设计和实现。计算几何中使用的基本技术包括多边形三角剖分、凸包、Voronoi图、排列、几何查找、运动计划等。虽然自主处理只涉及数学基础知识领域的一部分，但是它却和当今该研究领域的前沿课题相关。因此，专业的程序员会发现本书是一本不可多得的参考书。
　　与上一版相比，本版包括以下几方面的新内容：多边形三角剖分的随机化算法、平面点定位、3D凸包的构造、关于射线段和射线三角的相交算法、多面体中的点等。此外，本版还增加新的一章——“资料来源”，提供了关于各个主题的更详尽的补充资料。
　　本书的一个新特点就是为很多算法增加了可运行的C语言代码，以及如何在现实中实现它们的相关讨论。与第1版相比，本版中的代码有了大幅度的改善（更高效、更稳定），同时本版中还增加了4个新的例程。此外，本书还提供了所有代码的Java版本，读者可以从本书的网站http：//cs.smith.edu/~orourke/）上下载这些免费提供的代码。