计算几何 Computational Geometry 陈海丰 QQ:362339373 Email:chenhaifeng88888@gmail.com 2007-8-8

计算几何 计算几何研究几何模型和数据处理的学科，探讨几何形体的计算机表示。分析和综合，研究如何灵活、有效的建立几何形体的数学模型以及在计算机中更好地存储和管理这些模型数据 。 在ACM中，计算几何的知识点都比较简单，但是题目都不是那么好做，关键是靠平时积累经验。

基本概念 点 线（线段，直线） 面（三角形，圆，多变形（凸，凹）） 体

点 Point typedef struct TPoint { double x; double y; //double z; }TPoint;

线段 Segment typedef struct TSegment { TPoint t[2]; } TSegment；

直线 Line typedef struct TLine { //直线方程的系数 double a, b, c; }TLine;

三角形 Triangle typedef struct TTriangle { TPoint t[3]; }TTriangle;

圆 Circle typedef struct TCircle { double r; TPoint centre; }TCircle;

多边形 Polygon typedef struct TPolygon { TPoint p[MaxNode]; int n; }TPolygon;

点线面之间的关系 点与点 点与线 点与面 点与圆 点与多边形 线与线 线与面 面与面

点与点（距离） double distance(TPoint p1, TPoint p2) { //计算平面上两个点之间的距离 return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)); } 多维矢量（空间）点的距离与此类似

点关于点的对称点 TPoint symmetricalPoint(TPoint p1, TPoint p2) { //求p1关于p2的对称点 TPoint p3; p3.x = 2 * p2.x - p1.x; p3.y = 2 * p2.y - p1.y; return p3; }

点与线 点是否在直线上 点是否在线段上 点到直线的距离 点关于直线的对称点

点是否在直线上（一） 判断p0点是否在点p1，p2决定的的直线上 1.根据p1, p2求出直线的方程 2.将p0代入直线方程（注意精度问题）

直线方程 TLine lineFromSegment(TPoint p1, TPoint p2) { //线段所在直线,返回直线方程的三个系数 TLine tmp; tmp.a = p2.y - p1.y; tmp.b = p1.x - p2.x; tmp.c = p2.x * p1.y - p1.x * p2.y; return tmp; } 两点求直线方程

点是否在直线上（二） 根据矢量的叉积来判断 先看一下矢量（Vector）的叉积

矢量叉积

三维矢量的叉积

点是否在直线上（二） double multi(TPoint p1, TPoint p2, TPoint p0) { //求矢量[p0, p1], [p0, p2]的叉积 //p0是顶点 return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y); //若结果等于0，则这三点共线 //若结果大于0，则p0p2在p0p1的逆时针方向 //若结果小于0，则p0p2在p0p1的顺时针方向 }

点是否在线段上（一） 判断p0点是否在以点p1，p2点为端点的线段上

点是否在线段上（二） 判断p点是否在线段p1p2上 1.p是否在直线p1p2上 2.p是否在以p1p2为对角线的矩形中

点是否在线段上（二） bool isPointOnSegment(TPoint p, TPoint p1, TPoint p2) { if(multi(p1, p2, p) != 0) return false ; if((p.x > p1.x && p.x > p2.x) || (p.x < p1.x && p.x < p2.x)) return false; if((p.y > p1.y && p.y > p2.y) || (p.y < p1.y && p.y < p2.y)) return false; return true; }

点到直线的距离 求p0点到直线Line的距离

点关于直线的对称点 TPoint symmetricalPointofLine(TPoint p, TLine L) { //p点关于直线L的对称点 TPoint p2; double d; d = L.a * L.a + L.b * L.b; p2.x = (L.b * L.b * p.x - L.a * L.a * p.x - 2 * L.a * L.b * p.y - 2 * L.a * L.c) / d; p2.y = (L.a * L.a * p.y - L.b * L.b * p.y - 2 * L.a * L.b * p.x - 2 * L.b * L.c) / d; return p2; }

点关于线段的对称点 点关于线段的对称点 首先可以根据线段的两个端点求出线段所在的直线L，然后再来求指定点关于直线L的对称点 Reflections http://acm.fzu.edu.cn/problem.php?pid=1035 求一条射线遇到圆后的反射光， 即圆和直线求交点，求点关于交点法线的对称点。

点与面 点是否在平面 点到平面的距离

点与面（判断点是否在面上） 判断d点是否在a , b, c三点确定一个平面 1.三点可以确定一个平面 2.同时，平面上一点和平面的法线也可以确定这个平面 平面的法线可以通过平面上两条不平行的矢量的叉积确定

点与面（点到面的距离） ab.x = b.x - a.x; ab.y = b.y - a.y; ab.z = b.z - a.z; ac.x = c.x - a.x; ac.y = c.y - a.y; ac.z = c.z - a.z;

点与面（点到面的距离） 三维矢量的叉积 abc.x = ab.y * ac.z - ab.z * ac.y; abc.y = -(ab.x * ac.z - ab.z * ac.x); abc.z = ab.x * ac.y - ab.y * ac.x;

平面方程 //abc.x * (x - a.x) + abc.y * (y - a.y) + abc.z * (z - a.z) = 0; if(fabs(abc.x * (d.x - a.x) + abc.y * (d.y - a.y) + abc.z * (d.z - a.z)) < eps) eps = 1e-6(控制精度)

延伸：输入n个点，判断这n个点是否在同一平面内 1.选取三个不在同一直线上的点（如果所有点都在同一直线上， 则所有点都在同一平面），求出平面方程 2.根据平面方程，判断其他点是否在这一平面上 Coplanar Points http://acm.fzu.edu.cn/problem.php?pid=1393 利用差积判断4点共面。

点到面的距离

点与多边形 点是否在圆内（到圆心的距离） 点是否在多边形内 判断点q是否在多边形（凸或凹多边形）P内

点是否在多边形内 设多边形P的顶点序列为p1, p2, …,pn. 过q作水平射线L与P的边界不相交，则q在P的外部。否则，L和P的边界相交，计数交点的数目，并依据交点的奇偶性可以判断q是否在P的内部，具体地说就是，交点数为奇（偶）数时，点q 在P的内（外）部。

点是否在多边形内 由于这里的多边形不一定是凸点，所以上述的判断方法对某些情况是不适合的，要注意区分（射线经过多边形的某条边时不成立）。

点是否在多边形内 特殊情况1：多边形的水平边不作考虑 P

特殊情况2：若射线经过多边形顶点，则仅对边上纵坐标较大端点进行计数 点是否在多边形内 特殊情况2：若射线经过多边形顶点，则仅对边上纵坐标较大端点进行计数 P P P 计数一次 计数一次 计数一次

点是否在多边形内 特殊情况3：射线与多边形边重合的情况 p

点是否在多边形内 另一种方法： 如果所作的射线经过多边形的某条边， 则重新作一条射线，以此类推，避开这种情况。

点是否在多边形内 A Pilot in Danger! http://acm.fzu.edu.cn/problem.php?pid=1120 判断点在区域内

线与线 判断两条线段是否相交 判断线段与直线是否相交 判断直线与直线是否相交 若相交求交点

判断两条线段是否相交 判断线段[s1, e1]和[s2, e2]是否相交 两个步骤： 1.快速排斥试验（以两条线段为对角线的两个矩形是否相交） 2.跨立试验

判断两条线段是否相交 bool isIntersected(TPoint s1, TPoint e1, TPoint s2, TPoint e2) { if( (max(s1.x, e1.x) >= min(s2.x, e2.x)) && (max(s2.x, e2.x) >= min(s1.x, e1.x)) && (max(s1.y, e1.y) >= min(s2.y, e2.y)) && (max(s2.y, e2.y) >= min(s1.y, e1.y)) && (multi(s2, e1, s1) * multi(e1, e2, s1) >= 0) && (multi(s1, e2, s2) * multi(e2, e1, s2) >= 0) ) return true; return false; } 线段相交_直线相交 coj_1078

判断线段与直线是否相交 有了判断直线相交的基础，判断线段和直线是否相交就很简单了。比如判断线段[s2, e1]和直线L是否相交，只需要在直线L上取横坐标X无穷大和无穷小的两点s1, e1，然后判断线段[s1, e1]和线段[s2, e2]是否相交即可。

判断直线与直线是否相交 1.根据叉积判断这两条直线是否平行 2.求出两条直线的方程，然后解方程组

线与面 线与圆（线与圆的关系） 直线划分多边形 Hotter Colder http://acm.fzu.edu.cn/problem.php?pid=1014 求线段的中位线，线段相交求交点，求凸多边形的面积，

面积 三角面积

多边形面积

多边形面积

多边形面积 计算多边形的面积，即可把多边切割成若干个三角形分别计算各个三角形的面积再求和即可。多边形有n个顶点P1(x1,y1),P2(x2,y2),…,Pn(xn,yn),则

多边形面积

多边形面积 double polygonArea(TPolygon p, int n) { //已知多边形各顶点的坐标，求其面积 double area; int i; area = 0; for(i = 1;i <= n;i++){ area += (p.p[i - 1].x * p.p[i % n].y - p.p[i % n].x * p.p[i - 1].y); } return fabs(area) / 2;

三角形的外接圆

三角形的内切圆

多边形的重心 计算几何_多边形的重心（FZU1331） http://acm.fzu.edu.cn/problem.php?pid=1331 题目描述： 有一个密度均匀的平面N多边形(3 <= N <= 1000000)，可能凹也可能凸，但没有边相交叉， 另外已知N个有序(顺时针或逆时针)顶点的坐标值，第j个顶点坐标为（Xi ， Yi ），且满足 (|Xi|, |Yi| <= 20000)，求这个平面多边形的重心。

多边形的重心 解题过程： 从第1个顶点出发，分别连接第i, i+1个顶点组成三角形Ti,1 < i < n, 一共n-2个三角形正好是多连形的一个划分，分别求出每个三角形的面积Si， 总面积为各个面积相加根据物理学知识得：n个点(xi,yi)每个重量是mi,则重心是 X = (x1*M1+x2*M2+...+xn*Mn) /(M1+M2+....+Mn) Y = (y1*M1+y2*M2+...+yn*Mn) /(M1+M2+....+Mn) 由于密度均匀，所以这里重量都用面积代替。

凸包 convex hull 凸包是对平面是上的某个点集而言的，凸包是一个最小凸多边形，满足点集 中的所有点都在该凸多边形内（或在该多边形的边上）

凸包 convex hull 凸包是对平面是上的某个点集而言的，凸包是一个最小凸多边形，满足点集中的所有点都在该凸多边形内（或在该多边形的边上）。通常，我们采用Graham扫描法来求点集的凸包。首先，排序选出点集中最左下角点（先取y坐标最小的点，若有多个再在其中取x坐标最小的点），设该点为p0；然后，将其余的按以p0为中心的极角坐标逆时针排序，多于相同极角的点只保留距离p0最远的一个，这样就可以得到一个点的序列p1,p2, p2.....,pn;接下来，将p0, p1, p2压入栈，一次处理pi（i >= 2 && i <= n），不断让栈顶的元素出栈，直到栈顶的下一个元素，栈顶元素，以及pi构成的折线不拐向左侧，将pi压入栈中；最后栈中的元素即为所求的凸包的顶点序列

对于一个有三个或以上点的点集Q，Graham扫描法的过程如下： 1. 令p0为Q中Y-X坐标排序下最小的点

凸包的求法 （Graham扫描法） <p1,p2,...pm>为对其余点按以p0为中心的极角逆时针排序所得的点集（如果有多个点有相同的极角，除了距p0最远的点外全部移除 Pm P2 P1 P0 被移除

凸包的求法 （Graham扫描法） 保存P0，P1，P2三个点为凸包初始点入堆栈 Pm P2 P1 P0

若P3在矢量(P1->P2)的顺时针方向，则P2出栈保存P3入栈 凸包的求法 （Graham扫描法） 若P3在矢量(P1->P2)的顺时针方向，则P2出栈保存P3入栈 Pm P3 P1 P0

凸包的求法 （Graham扫描法） 每个点最多进栈一次，出栈一次，故算法复杂度为O(N) O(N) 比排序复杂度还要底， 故Graham扫描法的复杂度为 O(N*logN)

《计算几何》（算法分心与设计）周培德，卢开澄 国际大学生程序设计竞赛例题解（一）（计算几何部分） 参考书籍 《计算几何》（算法分心与设计）周培德，卢开澄 国际大学生程序设计竞赛例题解（一）（计算几何部分） Rotating Calipershttp://cgm.cs.mcgill.ca/~orm/rotcal.frame.html Computational Geometry http://dev.gameres.com/Program/Abstract/Geometry.htm http://www.cs.uu.nl/geobook/ http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html http://learn.tsinghua.edu.cn:8080/2001315450/cg.html Computational Geometry Code http://compgeom.cs.uiuc.edu/~jeffe/compgeom/code.html

坚持就是胜利！ 加油AC！ Thanks！