在recast中遇到的一個(gè)操作，判斷點(diǎn)是在線段的左邊還是右邊
判斷在左邊和右邊在很多場(chǎng)景都有用到，是計(jì)算機(jī)幾何中比較基礎(chǔ)的概念。比如判斷是凹多邊形還是凸多邊形；判斷點(diǎn)是凹點(diǎn)還是凸點(diǎn)；判斷線段是否相交；判斷兩點(diǎn)是否在線段兩側(cè)等等。

如https://blog.csdn.net/qiushangren/article/details/90446381
這篇博客所說，順時(shí)針方向 三點(diǎn)組成的向量的叉積z值為負(fù)，逆時(shí)針方向三點(diǎn)組成的向量的叉積z值為正。這個(gè)可以反過來用于求點(diǎn)在線段的左右。
首先左右不能用客觀的視角來定，應(yīng)該從向量的角度去判斷。所以先將線段轉(zhuǎn)換成向量，需要注意的是向量是有方向的有起止的。

如上，在xy平面上有線段AB（注意A為起點(diǎn)，B為終點(diǎn)）組成向量AB，存在點(diǎn)C1和C2，組成三角形ABC2和三角形ABC1。很明顯ABC2組成一個(gè)順時(shí)針方向的三個(gè)點(diǎn)，ABC1 組成了逆時(shí)針方向的三個(gè)點(diǎn)（注意這里的三角形必須包含了 向量AB）。
根據(jù)上面鏈接的博客可以很輕松的看出，

ABxAC2>0 而 ABxAC1<0 (叉乘，不是點(diǎn)乘)，（注意都是以A為起點(diǎn)，也就是以已知向量的起點(diǎn)為起點(diǎn)）。

如果線段AB組成向量為BA，則
BAxBC2<0 而 BAxBC1 >0（注意這里都是以B為起點(diǎn)，以已知向量的起點(diǎn)為起點(diǎn)）。

總結(jié)：如果以AB的方向來判定，那么C1就是在AB的右邊，C2就是在AB的左邊，假設(shè)三角形頂點(diǎn)順序?yàn)锳BC ，可以看到如果用ABC1組裝三角形，那么就是順時(shí)針的，如果ABC2組裝三角形，那就是逆時(shí)針的；如果以BA來判定，那C2在BA右邊，C1在BA的左邊，假設(shè)三角形頂點(diǎn)順序?yàn)锽AC，BAC1為逆時(shí)針，BAC2位順時(shí)針。可以推斷如果在左邊，那么順序就是逆時(shí)針；如果在右邊，那么順序就是順時(shí)針。反過來也一樣，順時(shí)針表示在右邊，逆時(shí)針表示在左邊。ABxAC（注意A為起始點(diǎn)），使用右手定則，順時(shí)針為求出的結(jié)果（z）為負(fù)數(shù)，逆時(shí)針為求出的結(jié)果（z）正數(shù)。

//判斷線段是否相交 static int overlapSegSeg2d(const float* a, const float* b, const float* c, const float* d) {const float a1 = vcross2(a, b, d); const float a2 = vcross2(a, b, c);if (a1*a2 < 0.0f) { //相乘結(jié)果為負(fù)，說明一左一右。 說明c和d分別分布在ab的兩側(cè)。c和d沒有分布在兩側(cè)，肯定是不相交。float a3 = vcross2(c, d, a);float a4 = a3 + a2 - a1; //a4 = vcross2(c,d,b)。可以用四個(gè)點(diǎn)坐標(biāo)計(jì)算一下，確實(shí)相等。if (a3 * a4 < 0.0f)return 1;//如果a和b也分布在cd兩側(cè)就說明相交}return 0; }//假設(shè)a（x1,y1） b(x2,y2) c(x3,y3) d(x4,y4) //b-a = (x2-x1),(y2-y1) ,d-a=(x4-x1),(y4-y1) => //a1 = (b-a)x(d-a) = (x2-x1)*(y4-y1)-(x4-x1)*(y2-y1) //a2 = (b-a)x(c-a) = (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1) //a3 = (d-c)x(a-c) = (x4-x3)*(y1-y3)-(x1-x3)*(y4-y3) //a4 = a3+a2-a1 =a3 + (x2-x1)*(y3-y4)-(x3-x4)*(y2-y1) // =a3 + (x4-x3)*(y2-y1)-(x2-x1)*(y4-y3) = (x4-x3)*(y2-y3)-(x2-x3)*(y4-y3)

判斷點(diǎn)是凹點(diǎn)還是凸點(diǎn)：取目標(biāo)點(diǎn)和目標(biāo)點(diǎn)相鄰的兩個(gè)點(diǎn)，按逆時(shí)針方向，將目標(biāo)點(diǎn)與前面的點(diǎn)相連成線段，判斷目標(biāo)點(diǎn)后面的點(diǎn)是否在線段的左邊還是右邊，如果在左邊，則說明是凸點(diǎn)，否則是凹點(diǎn)。

判斷是凹多邊形還是凸多邊形：按逆時(shí)針方向判斷所有 邊的下一個(gè)點(diǎn)（逆時(shí)針方向與邊相鄰的點(diǎn)） 是否都在邊的左邊，如果都在左邊說面是凸多邊形。也可以按順時(shí)針方向來，判斷是否在右邊。

判斷兩點(diǎn)是否在線段兩側(cè)：直接判斷一個(gè)點(diǎn)在左邊一個(gè)點(diǎn)在右邊。

判斷線段是否相交：假設(shè)兩條線段a,b。先計(jì)算兩線段的bound是否相交做個(gè)快速排除，再判斷線段a的兩個(gè)頂點(diǎn)是否都在線段b的兩側(cè)，再判斷線段b的兩個(gè)頂點(diǎn)是否在線段a的兩側(cè)，如果兩個(gè)條件都滿足，則a b相交，否則不相交。（求交點(diǎn)）

?

?

總結(jié)

以上是生活随笔為你收集整理的判断点在线段的左边还是右边 判断线段是否相交的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。