引言
计算几何的重要之处在于它是多门技术与学科的基础，例如图形学、CAD、GIS、路径规划等。这些技术的背后原理往往是基于计算几何的本质上。所以该门课程的学习对养成计算几何理论的总体认识很有帮助，这种认识将为学习者日后的研究工作提供几何的视角。
What can we learn from this course?
- Awareness of Computational Geometry theory that will help students incorporate Computational Geometry into their future research
- Comprehensive understanding on fundamental paradigms/strategies for solving geometric problems, incremental construction, plane sweeping
- Essential geometric structures and algorithms such as polygon decompositions, Voronoi diagrams, Delaunay triangulations
本课程的教学目标有三：
- 对计算几何理论的总体认识，在日后的研究工作中，这种认识为你提供几何的视角
- 对几何问题求解范式及策略的全面领会，包括递增式构造、平面扫描、分而治之、分层化、近似以及随机化等
- 对基本几何结构及其算法的透彻掌握，包括凸包、多边形细分、Voronoi图、Delaunay三角剖分，以及几何求交、点定位、范围查找、截窗查询等
Are you qualified for learning Computational Geometry?
Computational Geometry requires some skills of algorithm design and analysis as well as programming, but you don’t need to be an expert before learning this course. Actually, C/C++ programming experience and some basic knowledge of common data structures will be enough. To make sure whether you are qualified for learning this course, check the list below:
- C/C++ programming: variable, function, struct, class;
- Algorithm design and analysis: complexity, amortized analysis, recursion, divide and conquer, linked list, binary search tree, priority queue.
计算几何这门课对数据结构和算法基础和编程基础有一定的要求，但这并不意味着你需要精通所有相关课程。实际上，你只需掌握一些常见数据结构，拥有一定的算法分析能力，以及C/C++语言编程的基本技巧。为确认自己是否适宜选修这门课程，不妨对照以下清单做一清点：
- C/C++语言程序设计基础：变量，函数，结构体，类
- 数据结构与算法分析：复杂度、摊还分析、递归、分治法、链表、栈、二叉搜索树、优先队列
History of This Course
这门课已经开设 18 年之久，虽然国外诸多著名高校都开设了这门课程，但国内做计算几何方面的学校和机构屈指可数。
What’s Computational Geometry
说到计算几何，我们要做一个名词辨析。
如果你第一次听到 Computational Geometry，首先注意到的肯定是几何，脑海中浮现的是曲线、曲面诸如此类。事实上我国数学家苏步青八十年代就曾出版过一本《计算几何》的书。 此计算几何非彼计算几何，这门课更加强调的是计算。现代计算几何人们公认诞生于 1978 年 Shamos 那篇著名的博士论文，所以这门学科到现在也不过区区四十年的发展历史。
当然计算几何之所以很重要，就是因为它是很多学科尤其是技术学科的基础，包括典型的图形学、CAD、GIS、路径规划等等……最后都会回到计算几何这些基本的问题。
在学习之前如果一言以蔽之概括一下的话，计算几何就是就是”算法设计与分析”的几何版，它所讨论的对象、问题的表面形式都是几何的，它求解这些问题的方法、策略高到上面的方法论其实也都是几何的。尽管从这个方面讲计算几何只是算法设计与分析的一个分支，但是正因为它融入了很多古典的一些离散几何学、组合几何学等等精华的结论和方法，所以它不仅仅是一个几何和计算两个问题的物理反应，而是很深入的化学反应。
How to Learn CG Better
计算几何强调本质的东西就是要形象。
没有人喜欢复杂深奥的东西，所以这门课如果在学习过程中没办法很好理解推导和公式，不必拘泥于复杂深奥的泥潭，暂时放下它，将注意力放在图形和具体表现上。