【计算几何】基础知识

前言

这章早在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

大概就是这样吧~

转载于:https://www.cnblogs.com/BrokenString/p/9279491.html