计算几何---ToLeftTest
计算几何—ToLeftTest
标签（空格分隔）： 计算几何
问题场景
ToLeftTest用于片段一个点在一个向量的左侧还是右侧(或者在向量所在的直线上)。
《计算几何–算法与应用》第一章中用于确定凸包的边。如图，灰色的线段即为凸包的边，也称为极边。
极边都会有一个性质，那就是：除了极边的两个端点，其余的顶点全部都在极边的左边/右边(或者上)。
如何判断其余所有顶点在边的一侧呢。这就是ToLeftTest所解决的。
ToLeftTest思路
该方法通过向量叉乘求解。
如图，已知向量PQ 和点 R，当沿着逆时针方向叉乘，如：PQ X QR，所得到的向量的模的值
- 若为正，则代表点R 在 PQ左侧
- 若为负值，点R在PQ右侧
- 若为0，点R在直线PQ上
由此我们只需要求叉乘的值，就可以判断点R相对PQ的方位。
计算
而这个结果又可以用这样一个三维行列式表示：
从几何意义来说，向量叉乘的向量的模的绝对值等于这两个向量所围成的平行四边形的面积。因此 abs(D) = 2 * S△PQR
通过百度百科三角形的有向面积我们可以验证这个结论
优点
使用三维行列式来计算，首先是方便GPU的计算。其次是避免了除法和一些三角函数的调用。可以降低误差。
参考
【1】计算几何–算法与应用（第二版）以及学堂在线‘计算几何’课程
【2】3Blue1Brown 的‘线性代数’系列：bilibili熟肉
【3】百度百科