前言.Preface
一般来说，计算几何是研究在计算机上求解几何问题的算法。本书重点介绍此类算法的设计，不怎么关注性能分析。我将一些算法用 C 程序实现了一遍，在这里进行详细讨论。
几何学有很多分支，本书所涵盖的"计算几何"主要指离散(discrete)几何和组合(combinatorial)几何。因此，多边形在本书中扮演着比曲面边界区域更重要的角色。
关于连续曲线和曲面的大量研究都属于"几何建模geometric modeling"或"实体建模solid modeling"的范畴，这是一个拥有自身会议和教材的领域，与计算几何有所区别。
当然，两者之间存在大量的重叠，而且这种划分方式并没有依据。事实上，它们似乎在某种程度上正在融合。
如果以M. I. Shamos的论文（Shamos 1978）作为其开端的话，截至本书撰写之时，计算几何领域仅有二十年的历史。
如今，该领域已发展出年度会议、期刊、教材，以及一个拥有共同兴趣的蓬勃发展的科研人员社群。
主题(Topics Covered)
我认为计算几何的"核心"关注点包括多边形分割(包括三角分割)、凸包(convex hulls)、Voronoi图、直线排列、几何搜索(geometric searching)和运动规划。
这些主题均出自本书各章节。该领域尚未完全定论，因此这份清单尚不能被视为共识，其他研究者对核心的定义可能有所不同。
许多教科书包含的内容远远超过一个学期所能涵盖的范围。但本书并非如此。我通常在一个40课时的学期里，给本科生讲授本书约80%的内容，给研究生讲授全部内容。
为了涵盖每个核心主题，我认为有必要在细节上有所调整，有些算法只做简要概述，有些则进行详细讲解。
至于哪些算法简要概述，哪些算法详细讲解，完全取决于我个人的选择，而这种选择也只能从我的课堂教学经验中得出。
预备(Prerequisites)
实现(Prerequisites)
练习(Exercises)
第二版(Second Edition Improvements)
致谢(Acknowledgments)
我收到了六百多封来自本书第一版读者的电子邮件，我实在难以准确地列出他们对本版做出的具体贡献。
我衷心感谢以下人士的建议，他们中许多人是我的专业同事，二十九位是我的学生，但大多数人我只在网上见过面：
Pankaj Agarwal, Kristy Anderson, Bill Baldwin,
Michael Baldwin, Pierre Beauchemin, Ed Bolson, Helen Cameron, Joanne Cannon, Roy
Chien, Satyan Coorg, Glenn Davis, Adlai DePano, Matthew Diaz, Tamala Dirlam, David
Dobkin, Susan Dorward, Scot Drysdale, Herbert Edelsbrunner, John Ellis, William
Flis, Steve Fortune, Robert Fraczkiewicz, Reinaldo Garcia, Shannilli Ghosh, Carole
Gitlin, Jacob E. Goodman, Michael Goodrich, Horst Greiner, Suleyman Guleyupoglu,
Eric Haines, Daniel Halperin, Eszter Hargittai, Paul Heckbert, Claudio Heckler, Paul
Heffernan, Kevin Hemsteter, Christoph Hoffmann, Rob Hoffmann, Chun-Hsiung Huang,
Knut Hunstad, Ferran Hurtado, Joan Hutchinson, Andrei lones, Chris Johnston,
Martin Jones, Amy Josefczyk, Martin Kerscher, Ed Knorr, Nick Korneenko, John
Kutcher, Eugene Lee, David Lubinsky, Joe Malkevitch, Michelle Maurer, Michael
McKenna, Thomas Meier, Walter Meyer, Simon Michael, Jessica Miller, Andy
Mirzaian, Joseph Mitchell, Adelene Ng, Seongbin Park, Irena Pashchenko, Octavia
Petrovici, Madhav Ponamgi, Ari Rappoport, Jennifer Rippel, Christopher Saunders,
Catherine Schevon, Peter Schorn, Vadim Shapiro, Thomas Shenner, Paul Short, Saul
Simhon, Steve Skiena, Kenneth Sloan, Stephen Smeulders, Evan Smyth, Sharon Solms,
Ted Stem, Ileana Streinu, Vinita Subramanian, J.W.H. Tangelder, Yi Tao, Seth Teller,
Godfried Toussaint, Christopher Van Wyk, Gert Vetger, Jim Ward, Susan Weller, Wendy
Welsh, Rephael Wenger, Gerry Wiener, Bob Williamson, Stacia Wyman, Min Xu,
Dianna Xu, Chee Yap, Amy Yee, Wei Yinong, Lilla ZoIlei, and the Faculty Advancement
in Mathematics 1992 Workshop participants.
对于不可避免的遗漏，我深表歉意。
剑桥大学的 Lauren Cowles 是一位理想的编辑。我曾多次获得美国国家科学基金会的慷慨资助，用于我的计算几何研究，最近的一项资助项目编号为CCR-9421670。
Joseph O'Rourke
orourke@cs.smith.edu
http://cs.smith.edu/~orourke
Smith College, Massachusetts
December 23, 1997
关于封面
封面图像是一个分布在球面上的螺旋曲线，它是一个 5,000 个点的凸包。它是通过运行本书附带的 spiral.c 和 chull.c 代码生成的。
spiral 5000 -r1OOO | chull
