二维基础

点

可以用 int 解决的尽量用 int 解决。

如果用处不多的时候可以用 pair<double,double>，但是更多时候还是：

struct Point {double x,y;};

向量

点积：\vec{a} · \vec{b} = a_xb_x+a_yb_y 几何意义：\vec{a}·\vec{b} = |\vec{a}||\vec{b}|\cos \theta

求长度：|\vec{a}| = \sqrt{\vec{a}·\vec{a}} 投影：|\vec{a}| \cos\theta= \frac{\vec{a}·\vec{b}}{|\vec{b}|}

叉积：\vec{a}\times \vec{b} = (a_xb_y-a_yb_x) 几何意义：\vec{a}\times \vec{b} = |\vec{a}| |\vec{b}| \sin\theta

求平行四边形面积：直接 | \vec{a}\times \vec{b} | = | |\vec{a}| |\vec{b}| \sin\theta | 三角形的面积记得带上 \frac{1}{2}

判断向量平行：\vec{a}\times\vec{b} = \vec{0}

to-left 测试：判断点和直线的位置关系

  • \vec{AB}\times \vec{AP} > 0，P 在有向直线 AB 左侧。
  • \vec{AB}\times \vec{AP} < 0，P 在有向直线 AB 右侧。
  • \vec{AB}\times \vec{AP} = 0，P 在有向直线 AB 上。

本质：右手法则

image-20241217191835325

向量旋转：把向量 \vec{a} 逆时针旋转 \theta 是什么？

image-20241217192023284

a_x = \cos\theta a_x-\sin{\theta}a_y,a_y = \sin\theta a_x+\cos{\theta}a_y''

点和线段的关系：考虑 P 与线段 AB 的关系

P 在 AB 所在直线上：\vec{PA}\times\vec{PB} = \vec{0}

P 在 AB 之间：\vec{PA}\times\vec{PB} \leq \vec{0}

线段与线段的关系：考虑线段 AB 与线段 CD 的关系，判断二者是否相交

考虑跨立实验，判断 A,B 是否在 CD 的不同侧， C,D 是否在 AB 的不同侧

image-20241217195009694

但是关键在于，可能存在 AB,CD 共线的情况。记得判断点是否在线段上，以及区间是否相交。

直线

点向式：记直线上一点 P，方向向量 \vec{v}，(x,y) = \vec{OP} + \lambda \vec{v}

struct Line {Point p,v;};

点到直线的距离：image-20241217200152840

利用一下简单的高中数学：|\vec{AB}| = |\vec{PA}| |\sin\theta| = \frac{|\vec{v}\times\vec{PA}|}{|\vec{v}|}

点在直线上的投影点：image-20241217200152840

如何避免开方？

image-20241217200838833

多边形

struct Polygon {vector <Point> p;};

注意首尾两个点。

面积：分解成若干三角形的面积

S = \frac{1}{2}|\sum\limits_{i=0}^{n-1} \vec{OP_i}\times \vec{OP_{i+1 \bmod n}}| 注意到即使 O 在多边形外，实际上也依然成立：image-20241217201424272

图中 O 与 P_1,P_0,P_4 的叉积是正的， 然后注意到 OP_2,OP_3 的叉积是负的，利用割补法面积仍然成立。

判断点是否在多边形内：光线投射算法

从点引出一条射线，如果射线与多边形有奇数个交点，那么该点在多边形内部，否则该点在多边形外部。

image-20241217203948103