学习进度:40/197(分钟)
Wannafly计算几何教程
向量的叉积和点积
cmath
- acos(-1.0) π
- atan2(y,x) 算角度
直角坐标和极坐标互化
$$
(x,y) => (sqrt(x^2+y^2),atan2(y,x))
$$
求一个点绕原点旋转x度后的坐标
判断一个点与一条直线的关系(线上，左/右侧)
- 叉积 正 => 左边
- 叉积 负 => 右边
判断两条线段的关系
- 四次叉积
求两条直线的交点坐标(保证不平行)
设
$$
a1(x1, y1), a2(x2,y2), b1(x3,y3), d(x4,y4)
=>(((b1-b2)/(s1+s2) * s2) + b2)
$$
注意：所有运算都是基于向量
求一个封闭不自交多边形面积
按照顺时针给出每个点的坐标
设$n$个点
$$
p1(x1, y1), p2(x2, y2), p3(x3,y3),…,pn(xn,yn)
$$
$$
S=|(p1×p2+p2×p3+…pn-1×pn+pn×p1)/2|
$$
多边形面积交
极角排序
概述：把二维问题转化为极角上的一维问题