[toc]

# 二维计算几何

# 正弦定理

1. 在三角形 ABC 内，若角 A,B,C 所对的边分别为 a,b,c, 则:
   其中 R 为三角形 ABC 的外接圆半径

$$\\frac{a}{sinA}=\\frac{b}{sinB}=\\frac{c}{sinC}=2R$$

# 余弦定理

1. 在三角形 ABC 中，若角 A,B,C 所对边分别为 a,b,c, 则有:

a^2=b^2+c^2-2bcCosA $$ $$ b^2=a^2+c^2-2acCosB $$ $$ c^2=a^2+b^2-2abCosC

# 快速排斥实验与跨立实验 (两直线相交试验)

我们现在想判定两条直线是否相交 ​ 按照如下步骤进行试验

1. 平行必不相交 (斜率)
2. 是否有三点共线
3. 其余的情况就需要用到快速排斥试验与跨立实验 (即上图)
   1. 先计算出两个线段的 AABB
   2. 如果两个 AABB 不相交，则线段必不相交 (但线段不相交，AABB 不一定不相交)
   3. 如果两个 AABB 相交，且 A,B 分布在线 CD 的两边，则认为线必然相交

# 判断一个点是否在任意多边形内部 (Point in Polygon)

# 光线投射算法 (Ray casting algorithm)

1. 特判一些特殊情况
   1. 这个点离多边形太远了 (方法: AABB, 点不在 AABB 里，肯定不再多边形内)
   2. 点是否在边或顶点上
   3. 另外，以这个点引出一条射线，如果射线与多边形交点是奇数个，则在多边形内部，否则在多边形外部。(奇内偶外)，怎么判断射线交点捏，跨立实验！！

# 回转数算法

把点与多边形所有的顶点连接起来，把所有夹角加起来，(夹角有方向)，如果和为 0，则点在多边形外

# 求两条直线的焦点

1. 直线相交，判定是否平行即可
2. 从两条直线上分别选取一个点和在直线上的方向向量，通过这些信息来计算，计算方法:

已知：点 A,B 坐标，向量 u, 沿直线方向向量 EB/ED (方向化), 方向向量夹角 β，u 与 ED 夹角 θ 之后的计算方法: 实际上这个计算本质上就是计算三角形的第三边长，可以自己画图求证一下