【计算几何】基础知识
前言
这章早在2017年寒假就在培训的时候由来自清华的hta老师上过了
但是本蒟蒻那时候并不是懂的太多
所以这周ww老师又上了一遍
大概记录一下
start
点积
大概就跟高中必修4的平面向量差不多（有上过的应该都会）
a = (x1, y1) b = (x2, y2)
a · b = x1x2 + y1y2
a · b = |a||b|cos< a, b>
运用：
若a与b垂直，则a · b = 0
一个与a垂直的向量： (y1, –x1)
叉积
a = (x1, y1) b = (x2, y2)
a×b = x1y2 – x2y1
|a×b| = |a||b|sin< a, b>
a×b = – b×a
讨论x1y2 – x2y1符号
当=0，b与a共线（可以反向）
当>0，b在a逆时针方向
当<0，b在a顺时针方向
运用
折线段的拐向判断：
折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段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三点共线。
三角形面积
- absinC/2
- 底乘高
- 海伦公式：S=根号下p(p-a)(p-b)(p-c) (p为三角形周长的一半,即p=1/2（a+b+c）)
判断两个线段是否相交
跨立实验：判断一条线段的两端是否在另一条线段的两侧（两个端点与另一线段的叉积乘积为负）。需要正反判断两侧。
( P1 – Q1 ) × ( Q2 – Q1 ) * ( Q2 – Q1 ) × ( P2 – Q1 ) >= 0
( Q1 – P1 ) × ( P2 – P1 ) * ( P2 – P1 ) × ( Q2 – P1 ) >= 0
判断点在多边形的内外
随机向一个方向射出一条射线，
这个点在多边形内仅当射线与多边形奇数条边相交。
end
大概就是这样吧~