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