计算几何

计算几何公式大全：https://blog.csdn.net/clasky/article/details/9990235

矢量叉积：

计算矢量叉积是与直线和线段相关算法的核心部分。设矢量P = （x1,y1） ，Q = (x2,y2)，则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积，即：P × Q = x1*y2 - x2*y1，其结果是一个标量。显然有性质 P × Q = - ( Q × P ) 和 P × ( - Q ) = - ( P × Q )。一般在不加说明的情况下，本文下述算法中所有的点都看作矢量，两点的加减法就是矢量相加减，而点的乘法则看作矢量叉积。

叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系：

若 P × Q > 0 , 则P在Q的顺时针方向。 若 P × Q < 0 , 则P在Q的逆时针方向。 若 P × Q = 0 , 则P与Q共线，但可能同向也可能反向。

折线段的拐向判断：

折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段p0p1和p1p2，通过计算(p2 - p0) × (p1 - p0)的符号便可以确定折线段的拐向：

若(p2 - p0) × (p1 - p0) > 0,则p0p1在p1点拐向右侧后得到p1p2。

若(p2 - p0) × (p1 - p0) < 0,则p0p1在p1点拐向左侧后得到p1p2。

若(p2 - p0) × (p1 - p0) = 0,则p0、p1、p2三点共线。

判断点是否在线段上：

设点为Q，线段为P1P2 ，判断点Q在该线段上的依据是：( Q - P1 ) × ( P2 - P1 ) = 0 且 Q 在以 P1，P2为对角顶点的矩形内。前者保证Q点在直线P1P2上，后者是保证Q点不在线段P1P2的延长线或反向延长线上

计算直线的交点

int dblcmp(double r) {

    if(fabs(r)<EPS) return 0;

    return r>0?1:-1;

}

double cross(Point p1, Point p2, Point p3, Point p4)
{
    return (p2.x - p1.x) * (p4.y - p3.y) - (p2.y - p1.y) * (p4.x - p3.x);
}

double area(Point p1, Point p2, Point p3)
{
    return cross(p1, p2, p1, p3);
}

double farea(Point p1, Point p2, Point p3)
{
    return fabs(area(p1, p2, p3));
}

bool meet(Point p1, Point p2, Point p3, Point p4)
{
    return max(min(p1.x, p2.x), min(p3.x, p4.x)) <= min(max(p1.x, p2.x), max(p3.x, p4.x))
    && max(min(p1.y, p2.y), min(p3.y, p4.y)) <= min(max(p1.y, p2.y), max(p3.y, p4.y))
    && dblcmp(cross(p3, p2, p3, p4) * cross(p3, p4, p3, p1)) >= 0
    && dblcmp(cross(p1, p4, p1, p2) * cross(p1, p2, p1, p3)) >= 0;
}

Point inter(Point p1, Point p2, Point p3, Point p4)
{
    double k = farea(p1, p2, p3) / farea(p1, p2, p4);
    return Point((p3.x + k * p4.x) / (1 + k), (p3.y + k * p4.y) / (1 + k));
}

排序

对于计算几何有时候要对点进行排序

有两种方式 极角序 水平序

极角序

以一个点作为极点，做一个极坐标系

其余点按照在极坐标中的位置来排序   如果碰到极角相同的点，距离近的排前面

这样可以得到一个简单的多边形

水平序

所有点按照y坐标递增 y相同 x坐标递增

第一个点为A 最后一个点为B

按顺序取出AB右侧的点，反向取出AB左侧的点 连起来得到最终的序列

不涉及三角函数 精度比极角序好

判断点Q在多边形内

过Q做一条沿x轴的射线。

如果射线与多边形的边的交点个数是奇数，则Q在内部

如果射线与多边形的边的交点个数是偶数，则Q在外部

要注意射线会不会和多边形的边重合 或者射线和多边形交于某个顶点