二维计算几何基础
Summary
二维计算几何以平面直角坐标系为基础，核心工具是向量：用点的差表示方向与长度，再由点积和叉积导出几乎所有几何关系。点积等于两向量模长与夹角余弦之积，用于判夹角、投影与垂直；叉积的绝对值是两向量张成的平行四边形面积，符号表示旋转方向。浮点比较用 sgn 统一处理正负零三态。在此之上给出判点在直线哪侧、线段相交的快速排斥与跨立、多边形面积、两直线交点等基本操作，并附相应例题。
参考资料
简介
二维计算几何以平面直角坐标系为基础，核心工具是 向量（Vector）：用点的差 表示方向与长度，再通过点积和叉积导出几乎所有几何关系。
点积（Dot Product），用于判断夹角、投影、垂直（点积为 0）。
叉积（Cross Product），其绝对值为以 、 为邻边的平行四边形面积，符号表示旋转方向（正值逆时针，负值顺时针）。
由于浮点数比较需要容差 ，用函数 sgn 统一处理正负零三态。
实现
#include <bits/stdc++.h>
using namespace std;
const double pi=acos(-1);
const double eps=1e-10;
int sgn(double x){return (x>eps)-(x<-eps);}
struct Point
{
double x,y;
Point(){}
Point(double _x,double _y):x(_x),y(_y){}
Point operator+(Point B){return Point(x+B.x,y+B.y);}
Point operator-(Point B){return Point(x-B.x,y-B.y);}
Point operator*(double k){return Point(x*k,y*k);}
Point operator/(double k){return Point(x/k,y/k);}
bool operator==(Point B){return sgn(x-B.x)==0&&sgn(y-B.y)==0;}
};
double Dis(Point A,Point B){return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}
double Dis2(Point A,Point B){return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}
typedef Point Vector;
double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}
double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}
double Len(Vector A){return sqrt(Dot(A,A));}
double Len2(Vector A){return Dot(A,A);}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}
基本操作
常用操作均由上述基础推出：
- 判断点在直线哪侧：设直线过点 ，方向向量 ，待判点 ，则 的符号即为所在侧（正值在左，负值在右，零值在线上）。
- 线段相交：先做快速排斥实验（检查包围盒是否重叠），再做跨立实验（两端点叉积异号）。
- 多边形面积：逆时针标记顶点 ，选辅助点 ，面积为 。
- 两直线交点：利用叉积构造正弦定理，计算参数 ，交点为 。