计算几何（Computational Geometry），即以计算为主的几何。主要研究几何形体的计算机表示、分析与综合。计算几何在数字可视化、图形学、辅助设计、机器人、地理信息、集成电路、计算机视觉等领域被广泛使用。
1、点
点一般表示成P(x,y)，其中x,y为点的坐标。如上图4个点的坐标分别为：
P1(3,2) P2(-2,-2) P3(2,4) P4(4,0)。
过两点可连成一线段，两点之间的距离记为：
假设点的坐标为：
由勾股定理可知：
例如：
2、直线
直线的方程：
一般形式为：ax+by+c=0，或y=kx+b。k称为直线的斜率，b称为截矩。
如上图中，直线L1的方程为：0.75x-y+1=0，L2：y=3，L3：x=4。
直线的斜率：
如上图中，直线L1的斜率为0.75。
特别地：当y1=y2时，斜率k=0(如上图中的L2)，
当 x1=x2时，k不存在(如上图中的L3)。
过两点P1，P2可以决定一条直线。斜率为：
而当x1与x2无限接近时，斜率k趋于无穷大，这在编程时要特别小心。
3、向量（矢量）
简单的说，向量（vector）就是有大小有方向的量，如速度、位移等物理量都是向量。
如：有方向的线段，即P1和P2的顺序是有关系的，记为：
如果P1是坐标原点，则
向量的斜率：既然向量是有方向的，那么向量的斜率k就是有正负之分的，具体如下：
设
夹角：两个非0向量a、b，在空间任取一点O，作
4、向量的加减法
以点O为起点、A为端点作向量a，以点A为起点、B为端点作向量b，则以点O为起点、B为端点的向量称为a与b的和a+b，如下中图。
若从A点作
5、向量的数量积（点乘）
两个向量的数量积是一个数，大小等于这两个向量的模的乘积再乘以它们夹角的余弦。
a·b＝|a||b|cos<a,b>
用上面讲到的向量的分解可以证明，数量积等于两个向量的对应支量乘积之和。
a·b＝axbx＋ayby＋azbz
数量积的性质：
a·e=|a||e|cos<a,e>=|a|cos<a,e>
a⊥b 等价于 a·b＝0,即axbx＋ayby＋azbz=0
自乘：|a|2 ＝ a·a
结合律：（λ·a）·b = λ(a·b)
交换律：a·b ＝ b·a
分配律：a·(b + c) ＝ a·b + a·c
6、向量的向量积（叉乘、叉积）
向量积的一般含义：两个向量a和b的向量积是一个向量，记作a×b，其模等于由a和b作成的平行四边形的面积，方向与平行四边形所在平面垂直，当站在这个方向观察时，a逆时针转过一个小于π的角到达b的方向。这个方向也可以用物理上的右手螺旋定则判断：右手四指弯向由A转到B的方向（转过的角小于π），拇指指向的就是向量积的方向。如下左图。
我们给出叉积的等价而更有用的定义，把叉积定义为一个矩阵的行列式：
如上右图，如果
也可以用向量的分解证明：
即:
注：i,j,k分别为x,y,z方向上的单位向量
现在探讨一个重要的问题：给定两个向量：
方法：如上图，把P0作为原点，得出向量P1’=P1-P0和P2’=P2-P0，因此，这两个向量的叉积为：
如果该叉积为正，则
讨论另一个重要问题：确定连续线段是向左转还是向右转，如下图，即两条连续线段
方法：叉积，同上。
向量的叉积对于计算几何有着重要的意义，是很多算法的核心。用叉积可以判断从一个向量到另一个向量的旋转方向，可以求同时垂直于两个向量的直线（向量）方向，还能用来计算面积……。
向量的旋转：实际应用中，经常需要从一个向量转到另一个向量，这个过程称为向量的旋转，旋转的方向由叉积判定。很多例子都用到向量的旋转这个方法和相应特性。
7、坐标系中的矩形
若矩形边平行坐标轴，如(a)图，此时给出2个点的坐标：P1(x1,y1),P2(x2,y2),则其它两点坐标为：P3(x2,y1),P4(x1,y2)；
若矩形边不平行坐标轴，如(b)图，此时给出三点坐标：P1(x1,y1), P2(x2,y2),P3(x3,y3),则第4点坐标可以推得，利用切割法可以得到：
8、圆
设圆心的坐标为(x0,y0)，半径为r。则圆的一般方程为：
若O1(x0,y0)为原点（0，0），则方程为：
若：
若：
若：
9、多边形面积
在计算几何里，我们知道，△ABC的面积就是“向量AB”和“向量AC”两个向量叉积的绝对值的一半。其正负表示三角形顶点是在右手系还是左手系。
特别注意：以上得到是有向面积（有正负）！
凸多边形的三角形剖分
以 P1为扇面中心，连接P1Pi就得到N-2个三角形，由于凸性，保证这些三角形全在多边形内，那么，这个凸多边形的有向面积：
A=sigma(Ai) (i=1…N-2)
任意点为扇心的三角形剖分
以多边形内部的一个点为扇心，就可以把多边形剖分成 N个三角形。
我们可以得到：A=sigma(Ai) （ i=1…N ），即：
点在多边形内的判定
方法一：射线法
从判定点任意引一条射线，如果和边界的交点是奇数次，说明点在多边形内，如果交点为偶数个，点在多边形外。在多边形上需另外判断。
方法二：转角法
计算多边形每条边的转角的和，如果为360度，则点在多边形内，如果为0度，则在多边形外，如果为180度则点在多边形上（也适合非简单多边形）。
如果按照上面的定义实现，需要计算大量的反三角函数，不仅速度慢，而且容易产生精度误差。我们一般假设一条向右的射线，统计多边形穿过这条射线的正反次数，把这个数记为绕数wn（Winging Number），逆时针穿过是wn++，顺时针穿过wn–。
注意在程序现实的时候，判断是否穿过，以及穿过方向时，需要用叉积判断输入点在边的左边还是右边。
10、计算几何的经典算法—凸包
凸包就是把给定点包围在内部、面积最小的图多边形，它在计算几何里有着极其重要的作用。解决凸包问题一般有：斜率逼近法、数学构造法（Jarvis算法）和Graham算法。
可通过设置一个关于侯选点的堆栈S来解决凸包问题，设输入点集Q中的每个点都被压入堆栈一次，不是凸包中的点最终将被弹出堆栈。当算法终止时，堆栈S中仅包含凸包中的顶点，其从下往上的顺序为各点在边界上出现的逆时针方向排列的顺序。如下图：
支付宝扫一扫
