COMP9021作业引申的博客
1. 二维向量叉乘
参考:二维向量叉乘公式
a×b = (x1y2-x2y1)
参考:叉积(点线)判断法
(P叉乘Q)P^Q>0说明P在Q的顺时针方向,<0说明P在Q的逆时针方向,=0说明P和Q共线。
2. 判断点在多边形内部
参考:如何判定一点是否在给定顶点的不规则封闭区域内? - 知乎
任一射线穿过多边形,奇数段位于多边形之内,偶数段位于多边形之外。
注意:引出的线段与多边形某个边重合的情况,我用了一个诡异的角度,尽量不会出现重合吧^_^,同时需要考虑与顶点相交的可能性
3. 判断凸多边形
利用叉乘的性质,判断顺逆时针,可以用来判断一个多边形是否为凸多边形。
4. 判断两个线段相交
判断两个线段相交
具体实现:
设:线段 a :P1(x1, y1)、P2(x2, y2) 线段 b: Q1(x3, y3)、Q2(x4, y4)
d1 ====> (P2 - P1) x (Q1 - P1) (叉积)
d2 ====> (P2 - P1) x (Q2 - P1) (叉积)
d3 ====> (Q2 - Q1) x (P1 - Q1) (叉积)
d4 ====> (Q2 - Q1) x (P2 - Q1) (叉积)
首先,先判断端点是否在另一线段上。
然后,我们只需判断 d1 * d2 < 0 并且 d3 * d4 < 0 便可判断线段相交。
5. 计算凹凸多边形的面积
利用叉乘的方法计算
6. 判断线段在多边形内部
参考:判断线段是否在多边形内
不能只判断每个点在多边形内部,线段就在,这样不对,举例如下: