计算几何：C语言描述

图书标准信息

• 作者 [美]奥罗克 著
• 出版社 机械工业出版社
• 出版时间 2005-04
• 版次 1
• ISBN 9787111160519
• 定价 49.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 376页
• 正文语种 英语
• 丛书 经典原版书库

【内容简介】

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

【作者简介】

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

【目录】

preface
1.polygontrisngulation
1.1artgallerytheorems
1.2triangulation：theory
1.3areaofpolygon
1.4implementationissues
1.5segmentintersection
1.6triangulation：implementation

2.polygonpartitioning
2.1monotonepartitioning
2.2trapezoidalization
2.3partitionintomonotonemountains
2.4linear-timetriangulation
2.5convexpartitioning

3.convexhullsintwodimensions
3.1definitionsofconvexityandconvexhulls
3.2naivealgorithmsforextremepoints
3.3giftwrapping
3.4quickhull
3.5graham'salgorithm
3.6lowerbound
3.7incrementalalgorithm
3.8divideandconquer
3.9additionalexercises

4.convexhullsinthreedimensions
4.1polyhedra
4.2hullalgorithms
4.3implementationofincrementalalgorithm
4.4polyhedralboundaryrepresentations
4.5randomizedincrementalalgorithm
4.6higherdimensions
4.7additionalexercises

5.voranoidiagrams
5.1applications：preview
5.2definitionsandbasicproperties
5.3delannaytriangulations
5.4algorithms
5.5applicationsindetail
5.6medialaxis
5.7connectiontoconvexhulls
5.8connectiontoarrangements

6.arrangements
6.1introduction
6.2combinatoricsofarrangements
6.3incrementalalgorithm
6.4threeandhigherdimensions
6.5duality
6.6higher-ordervoronoidiagrams
6.7applications
6.8additionalexercises

7.searchandintersection
7.1introduction
7.2segment-segmentintersection
7.3segment-triangleintersection
7.4pointinpolygon
7.5pointinpolyhedron
7.6intersectionofconvexpolygons
7.7intersectionofsegments
7.8intersectionofnonconvexpolygons
7.9extremepointofconvexpolygon
7.10extremalpolytopequeries
7.11planarpointlocation

8.motionplanning
8.1introduction
8.2shortestpaths
8.3movingadisk
8.4translatingaconvexpolygon
8.5movingaladder
8.6robotannmotion
8.7separability

9.sources
9.1bibliographiesandfaqs
9.2textbooks
9.3bookcollections
9.4monographs
9.5journals
9.6conferenceproceedings
9.7software
bibliography
index