计算几何基础知识

1：pi=acos(-1)
2：余弦定理：$c^2$=$a^2$$+$$b^2$$-2abcos\alpha$
3：符号函数：

double eps=1e-8;
int sign(double x)
{
     if(fabs(x)<eps) return 0;
     if(x<0) return -1;
     return 1;
}
1
2
3
4
5
6
7

4：比较函数：

int cmp(double x,double y)
{
    if(fabs(x-y)<eps) return 0;
    if(x-y) return -1;
    return 1;
}
1
2
3
4
5
6

5：向量：
A(内积/点积)B=|A |* |B|* cos=x1*x2 + y1 * y2
下面是代码：

double dot(Point a,Point b)
{
    return a.x*b.x+a.y*b.y;
}
1
2
3
4

A(外积/叉乘)B=|A |* |B|* sin=x1y2-x2y1（三角形面积的2倍），计算的时候是有正负的，应该保证A通过逆时针转到B，这才能保证式正的

double cross(Point a,Point b)
{
    return a.x*b.y-a.y*b.x;
}
1
2
3
4

6：求模长：

double getlength(double a)
{
    return sqrt(dot(a,a));
}
1
2
3
4

7：计算向量夹角：

double get_ angle(Point a,Point b)
{
    return acos(dot(a,b)/get_length(a)/get_length(b));
}
1
2
3
4

8：求由A，B构成的平行四边形面积：

//假设前面逆时针转到后面是正，反之是负
double area(Point a,Point b,Point c)
{
    return cross(b-a,c-a);//注意面积的方向性
}
1
2
3
4
5

9：向量A旋转一定的角度到达的点：

//Point在这里是坐标，一般是用pair
Point rotate(Point a, double angle)
{
    return Point(a.x * cos(angle) + a.y * sin(angle), -a.x * sin(angle) + a.y * cos(angle));
}
1
2
3
4
5

10：点与线的关系：
(1) 一般式 ax + by + c = 0
(2) 点向式 p0 + vt
(3) 斜截式 y = kx + b
11：判断点在直线上：A × B=0
两直线相交：
cross(v,w)==0表示两直线平行或重合
不平行重合就是相交

//利用相似进行证明
Point get_line_intersection(Point p, Vector v, Point q, Vector w)
{
    Vector u = p - q;
    double t = cross(w, u) / cross(v, w);
    return p + v * t;//交点
}
1
2
3
4
5
6
7

12：点到直线的距离

double distance_to_line(Point p, Point a, Point b)
{
    vector v1 = b - a, v2 = p - a;
    return fabs(cross(v1, v2) / get_length(v1));
}
1
2
3
4
5

13：点到线段的距离
三种情况：

double distance_to_segment(Point p, Point a, Point b)
{
    if (a == b)
        return get_length(p - a);
    Vector v1 = b - a, v2 = p - a, v3 = p - b;
    if (sign(dot(v1, v2)) < 0)
        return get_length(v2);
    if (sign(dot(v1, v3)) > 0)
        return get_length(v3);
    return distance_to_line(p, a, b);
}

1
2
3
4
5
6
7
8
9
10
11
12

14：点在直线上的投影：

Point get_line_projection(Point p, Point a, Point b)
{
    Vector v = b - a;
    return a + v * (dot(v, p - a) / dot(v, v));
}
1
2
3
4
5

15：点是否在线段上：

Point get_line_projection(Point p, Point a, Point b)
{
    Vector v = b - a;
    return a + v * (dot(v, p - a) / dot(v, v));
}
1
2
3
4
5

16：判断两线段是否相交（ 面积的正负）

bool segment_intersection(Point a1, Point a2, Point b1, Point b2)
{
    double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1);
    double c3 = cross(b2 - b1, a2 - b1), c4 = cross(b2 - b1, a1 - b1);
    return sign(c1) * sign(c2) <= 0 && sign(c3) * sign(c4) <= 0;
}
1
2
3
4
5
6

17：求任意多边形的面积（假设坐标是按逆时针或顺时针存取）

double polygon_area(Point p[], int n)
{
    double s = 0;
    for (int i = 1; i + 1 < n; i++)
        s += cross(p[i] - p[0], p[i + 1] - p[i]);
    return s / 2;
}
1
2
3
4
5
6
7

这时的cross算面积时所带的正负的优势就体现出来了
18：
(1) 外心：外接圆圆心 三边中垂线交点。到三角形三个顶点的距离相等
(2) 内心：内切圆圆心，角平分线交点，到三边距离相等
(3) 垂心：三条垂线交点
(4) 重心：三条中线交点（到三角形三顶点距离的平方和最小的点，三角形内到三边距离之积最大的点）
普通多边形：通常按逆时针存储所有点
(1) 多边形：由在同一平面且不再同一直线上的多条线段首尾顺次连接且不相交所组成的图形叫多边形
(2) 简单多边形：简单多边形是除相邻边外其它边不相交的多边形
(3) 凸多边形：过多边形的任意一边做一条直线，如果其他各个顶点都在这条直线的同侧，则把这个多边形叫做凸多边形
任意凸多边形外角和均为360°
任意凸多边形内角和为(n−2)180°
19：
判断点是否在多边形内（不一定是凸多边形）
射线法：从该点任意做一条和所有边都不平行的射线。交点个数为偶数，则在多边形外，为奇数，则在多边形内。
判断点是否在凸多边形内：只需判断点是否在所有边的左边（逆时针存储多边形）。
20：皮克定理：计算顶点都为整数的多边形的面积（任意多边形）
S=a+b/2-1
其中a表示在多边形内部的整数点， b表示边界上的整数点，S表示多边形的面积
21：三角形面积：
（1）：叉积
（2）：海伦公式
p=(a+b+c)/2;
S=sqrt(p * (p-a) * (p-b) * (p-c) )；