计算几何实践1：基础

2017-11-27

计算几何在CAD开发，游戏开发中比较重要，可能只有机械和CAD方向的研究生才把这门课作为基础课程，很多做游戏的同学未必专门学习过这门课程。我觉得专门学习一下还是非常有必要的。我这两年多基本上在做CAD的开发，或多或少都需要涉及到这门课程里的知识。只是，一直没有系统的总结一下。我这两年虽然也做了很多的杂活儿，但是，主要还是在CAD组的工作。我个人对于CAD没有那么感兴趣，把更多的精力放在了OpenGL，Vulkan，数学基础上。我相信CAD的工作最好由机械专业的同学来做才最专业（这是一个大坑，深度可以非常深）。
  我手头上有一本Computational Geometry，是一本很不错的教材。我时常拿来参考。也推荐给想要在计算机图形学入门的同学。如果没有想深入的去学习，也可以在网上找到PDF版本，翻看一下。对于游戏开发的同学，也有一些参考意义。国内的教材也有很多，从排名靠前的几个中选择，应该都是不错的。这一系列blog，可以算作我自己的经验总结和对Computational Geometry 的读书笔记总结。这一个系列的博客总结实在拖得太久了。
  第一章最重要的是告诉读者计算几何这门课程能够在工作中做到什么。有提及的计算机图形学，还有机器人，地理信息系统，CAD/CAM，另外，也可以应用于分子建模，模式识别。这门课中最为基础的概念：点线面，vertex, edge, polygon, convex, intersection等。其实很少的。与机器学习比起来，那简直就是小儿科。
  对于应用，最为基础的就是Convex Hull，这里用一个例子来讲解，用一个小程序从一系列的顶点中构建一个凸包。在widget任意点击，超过三个点就开始构造凸包。

这个算法其实相当简单：对所有点按照x坐标排序；把凸包分为上下两个部分，分为两段构造。伪代码如下：

Input：A set P of points in the plane

Output: A list containing the vertices of H(P) in clockwise order

Sort the points by x-coordinate, resulting in a sequence, p1, ..., pn

Put the points p1, p2 in a list Lupper, with p1 as the first point

for i <- 3 to n

Append pi to Lupper

while Lupper contains more than two points and the last three points in Lupper do not make a right turn

do Delete the middle of the last three points from Lupper

Put the points pn and pn-1 in a list Llower, with pn as the first point

for i <- n-2 downto 1

Append pi to Llower

while Llower contains more than two points and the last three points in Llower do not make a right turn

do Delete the middle of the last three points from Lupper

Remove the first pint from Llower to avoid the duplication of the points where the upper and lower hull meet

Append Llower to Lupper, and call the resulting list L

return L

具体代码请参考 github computationalGeometry chapt1/convexhull.py 文件。关于构造凸包的算法的复杂度有一个定理：算法复杂度为 O( nlogn)。

关于计算几何中的问题求解，一般分为三个步骤：

对于问题，忽略特殊情况，排除干扰因素，明确是一个干净，准确的通用问题。
增加特殊情况的考虑因素，只不过在完全解决了通用问题之后，再补全所有的特殊情况
算法实现

这一系列的博文，将使用Python，PyQt来实现代码，或许，也会用到C++，毕竟一些lib可能没有python的版本。Python 版本2.7， PyQt4.11， numpy， sympy，bintrees，scipy。
numpy是最基础的数学计算lib，sympy 是符号计算的python 库，完全由Python写成，兼容Python2、3。pip install 即可，也可用使用whl安装。

Linux上环境搭建：
如果缺少什么lib，相信yum/apt，pip都应该能够解决。如pip install numpy scipy sympy

windows上：
一些lib是Python C拓展写的，用pip安装的时候需要编译C代码，可能不总是成功。最简单的方式是现在预编译的二进制lib，已经打包为whl包了，直接下载安装即可。pip install some.whl
https://download.lfd.uci.edu/pythonlibs/zhckc95n/PyQt4-4.11.4-cp27-cp27m-win_amd64.whl
https://download.lfd.uci.edu/pythonlibs/zhckc95n/sympy-1.1.1-py2.py3-none-any.whl

大家可以记住 https://www.lfd.uci.edu/~gohlke/pythonlibs/这个站点，它一直保持最常用python whl包的更新。对于windows上使用简直帮助很大。想当初，在学校的时候，那时候pip还没有兴起，easy_install 也常用，安装python lib那叫一个费劲啊。感谢做出这些工作的贡献者们。