C++/STL如何實(shí)現(xiàn)判斷平面內(nèi)兩條線段的位置關(guān)系

小編給大家分享一下C++/STL如何實(shí)現(xiàn)判斷平面內(nèi)兩條線段的位置關(guān)系，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

概念

平面內(nèi)兩條線段位置關(guān)系的判定在很多領(lǐng)域都有著廣泛的應(yīng)用，比如游戲、CAD、圖形處理等，而兩線段交點(diǎn)的求解又是該算法中重要的一環(huán)。本文將盡可能用通俗的語言詳細(xì)的描述一種主流且性能較高的判定算法。

外積，又稱叉積，是向量代數(shù)（解析幾何）中的一個(gè)概念。兩個(gè)二維向量v1(x1,y1)和v2(x2,y2)的外積v1×v2=x1y2-y1x2。如果由v1到v2是順時(shí)針轉(zhuǎn)動(dòng)，外積為負(fù)，反之為正，為0表示二者方向相同（平行）。此外，文中涉及行例式和方程組的概念，請參閱線性代數(shù)的相關(guān)內(nèi)容。

為方便計(jì)算，對坐標(biāo)點(diǎn)的大小比較作如下定義：x坐標(biāo)較大的點(diǎn)為大，x坐標(biāo)相等但y坐標(biāo)較大的為大，x與y都相等的點(diǎn)相等。一條線段中較小的一端為起點(diǎn)，較大的一端為終點(diǎn)。

問題

給定兩條線段的端點(diǎn)坐標(biāo)，求其位置關(guān)系，并求出交點(diǎn)（如果存在）。

分析

兩條線段的位置關(guān)系大體上可以分為三類：有重合部分、無重合部分但有交點(diǎn)（相交）、無交點(diǎn)。為避免精度問題，首先要將所有存在重合的情況排除。

重合可分為：完全重合、一端重合、部分重合三種情況。顯然，兩條線段的起止點(diǎn)都相同即為完全重合；只有起點(diǎn)相同或只有終點(diǎn)相同的為一端重合（注意：坐標(biāo)較小的一條線段的終點(diǎn)與坐標(biāo)較大的一條線段的起點(diǎn)相同時(shí)應(yīng)判定為相交）。要判斷是否部分重合，必須先判斷是否平行。設(shè)線段L1(p1->p2)和L2(p3->p4)，其中p1(x1,y1)為第一條線段的起點(diǎn)，p2(x2,y2)為第一條線段的終點(diǎn)，p3(x3,y3)為第二條線段的起點(diǎn)，p4(x4,y4)為第二段線段的終點(diǎn)，由此可構(gòu)造兩個(gè)向量：

v1(x2-x1,y2-y1)，v2(x4-x3,y4-y3)

若v1與v2的外積v1×v2為0，則兩條線段平行，有可能存在部分重合。再判斷兩條平行線段是否共線，方法是用L1的一端和L2的一端構(gòu)成向量vs并與v2作外積，如果vs與v2也平行則兩線段共線（三點(diǎn)共線）。在共線的前提下，若起點(diǎn)較小的線段終點(diǎn)大于起點(diǎn)較大的線段起點(diǎn)，則判定為部分重合。

沒有重合，就要判定兩條線是否相交，主要的算法還是依靠外積。然而外積的計(jì)算開銷比較大，如果不相交的情況比較多，可先做快速排斥實(shí)驗(yàn)：將兩條線段視為兩個(gè)矩形的對角線，并構(gòu)造出這兩個(gè)矩形。如果這兩個(gè)矩形沒有重疊部分（x坐標(biāo)相離或y坐標(biāo)相離）即可判定為不相交。

然后執(zhí)行跨立試驗(yàn)。兩條相交的線段必然相互跨立，簡單的講就是p1和p2兩點(diǎn)位于L2的兩側(cè)且p3和p4兩點(diǎn)位于L1的兩側(cè)，這樣就可利用外積做出判斷了。分別構(gòu)造向量s1(p3,p1),s2(p3,p2)，如果s1×v2與s2×v2異號(hào)(s1->v2與s2->v2轉(zhuǎn)動(dòng)的方向相反），則說明p1和p2位于L2的兩側(cè)。同理可判定p3和p4是否跨立L1。如果上述四個(gè)叉積中任何一個(gè)等于0，則說明一條線段的端點(diǎn)在另一條線上。

當(dāng)判定兩條線段相交后，就可以進(jìn)行交點(diǎn)的求解了。當(dāng)然，求交點(diǎn)可以用平面幾何方法，列點(diǎn)斜式方程來完成。但這樣作會(huì)難以處理斜率為0的特殊情況，且運(yùn)算中會(huì)出現(xiàn)多次除法，很難保證精度。這里將使用向量法求解。

設(shè)交點(diǎn)為(x0,y0)，則下列方程組必然成立：

x0-x1=k1(x2-x1)

y0-y1=k1(y2-y1)

x0-x3=k2(x4-x3)

y0-y3=k2(y4-y3)

其中k1和k2為任意不為0的常數(shù)（若為0，則說明有重合的端點(diǎn)，這種情況在上面已經(jīng)被排除了）。1式與2式聯(lián)系，3式與4式聯(lián)立，消去k1和k2可得：

x0(y2-y1)-x1(y2-y1)=y0(x2-x1)-y1(x2-x1)

x0(y4-y3)-x3(y4-y3)=y0(x4-x3)-y3(x4-x3)

將含有未知數(shù)x0和y0的項(xiàng)移到左邊，常數(shù)項(xiàng)移動(dòng)到右邊，得：

(y2-y1)x0+(x1-x2)y0=(y2-y1)x1+(x1-x2)y1

(y4-y3)x0+(x3-x4)y0=(y4-y3)x3+(x3-x4)y3

設(shè)兩個(gè)常數(shù)項(xiàng)分別為b1和b2：

b1=(y2-y1)x1+(x1-x2)y1

b2=(y4-y3)x3+(x3-x4)y3

系數(shù)行列式為D，用b1和b2替換x0的系數(shù)所得系數(shù)行列式為D1，替換y0的系數(shù)所得系數(shù)行列式為D2，則有：

|D|=(x2-x1)(y4-y3)-(x4-x3)(y2-y1)

|D1|=b2(x2-x1)-b1(x4-x3)

|D2|=b2(y2-y1)-b1(y4-y3)

由此，可求得交點(diǎn)坐標(biāo)為：

x0=|D1|/|D|,y0=|D2|/|D|

解畢。

C++/STL實(shí)現(xiàn)

#include <iostream>
#include <cmath>
using namespace std;
struct POINTF {float x; float y;};
bool Equal(float f1, float f2) {
  return (abs(f1 - f2) < 1e-4f);
}
//判斷兩點(diǎn)是否相等
bool operator==(const POINTF &p1, const POINTF &p2) {
  return (Equal(p1.x, p2.x) && Equal(p1.y, p2.y));
}
//比較兩點(diǎn)坐標(biāo)大小，先比較x坐標(biāo)，若相同則比較y坐標(biāo)
bool operator>(const POINTF &p1, const POINTF &p2) {
  return (p1.x > p2.x || (Equal(p1.x, p2.x) && p1.y > p2.y));
}
//計(jì)算兩向量外積
float operator^(const POINTF &p1, const POINTF &p2) {
  return (p1.x * p2.y - p1.y * p2.x);
}
//判定兩線段位置關(guān)系，并求出交點(diǎn)(如果存在)。返回值列舉如下：
//[有重合] 完全重合(6)，1個(gè)端點(diǎn)重合且共線(5)，部分重合(4)
//[無重合] 兩端點(diǎn)相交(3)，交于線上(2)，正交(1)，無交(0)，參數(shù)錯(cuò)誤(-1)
int Intersection(POINTF p1, POINTF p2, POINTF p3, POINTF p4, POINTF &Int) {
  //保證參數(shù)p1!=p2，p3!=p4
  if (p1 == p2 || p3 == p4) {
    return -1; //返回-1代表至少有一條線段首尾重合，不能構(gòu)成線段
  }
  //為方便運(yùn)算，保證各線段的起點(diǎn)在前，終點(diǎn)在后。
  if (p1 > p2) {
    swap(p1, p2);
  }
  if (p3 > p4) {
    swap(p3, p4);
  }
  //判定兩線段是否完全重合
  if (p1 == p3 && p2 == p4) {
    return 6;
  }
  //求出兩線段構(gòu)成的向量
  POINTF v1 = {p2.x - p1.x, p2.y - p1.y}, v2 = {p4.x - p3.x, p4.y - p3.y};
  //求兩向量外積，平行時(shí)外積為0
  float Corss = v1 ^ v2;
  //如果起點(diǎn)重合
  if (p1 == p3) {
    Int = p1;
    //起點(diǎn)重合且共線(平行)返回5；不平行則交于端點(diǎn)，返回3
    return (Equal(Corss, 0) ? 5 : 3);
  }
  //如果終點(diǎn)重合
  if (p2 == p4) {
    Int = p2;
    //終點(diǎn)重合且共線(平行)返回5；不平行則交于端點(diǎn)，返回3
    return (Equal(Corss, 0) ? 5 : 3);
  }
  //如果兩線端首尾相連
  if (p1 == p4) {
    Int = p1;
    return 3;
  }
  if (p2 == p3) {
    Int = p2;
    return 3;
  }//經(jīng)過以上判斷，首尾點(diǎn)相重的情況都被排除了
  //將線段按起點(diǎn)坐標(biāo)排序。若線段1的起點(diǎn)較大，則將兩線段交換
  if (p1 > p3) {
    swap(p1, p3);
    swap(p2, p4);
    //更新原先計(jì)算的向量及其外積
    swap(v1, v2);
    Corss = v1 ^ v2;
  }
  //處理兩線段平行的情況
  if (Equal(Corss, 0)) {
    //做向量v1(p1, p2)和vs(p1,p3)的外積，判定是否共線
    POINTF vs = {p3.x - p1.x, p3.y - p1.y};
    //外積為0則兩平行線段共線，下面判定是否有重合部分
    if (Equal(v1 ^ vs, 0)) {
      //前一條線的終點(diǎn)大于后一條線的起點(diǎn)，則判定存在重合
      if (p2 > p3) {
        Int = p3;
        return 4; //返回值4代表線段部分重合
      }
    }//若三點(diǎn)不共線，則這兩條平行線段必不共線。
    //不共線或共線但無重合的平行線均無交點(diǎn)
    return 0;
  } //以下為不平行的情況，先進(jìn)行快速排斥試驗(yàn)
  //x坐標(biāo)已有序，可直接比較。y坐標(biāo)要先求兩線段的最大和最小值
  float ymax1 = p1.y, ymin1 = p2.y, ymax2 = p3.y, ymin2 = p4.y;
  if (ymax1 < ymin1) {
    swap(ymax1, ymin1);
  }
  if (ymax2 < ymin2) {
    swap(ymax2, ymin2);
  }
  //如果以兩線段為對角線的矩形不相交，則無交點(diǎn)
  if (p1.x > p4.x || p2.x < p3.x || ymax1 < ymin2 || ymin1 > ymax2) {
    return 0;
  }//下面進(jìn)行跨立試驗(yàn)
  POINTF vs1 = {p1.x - p3.x, p1.y - p3.y}, vs2 = {p2.x - p3.x, p2.y - p3.y};
  POINTF vt1 = {p3.x - p1.x, p3.y - p1.y}, vt2 = {p4.x - p1.x, p4.y - p1.y};
  float s1v2, s2v2, t1v1, t2v1;
  //根據(jù)外積結(jié)果判定否交于線上
  if (Equal(s1v2 = vs1 ^ v2, 0) && p4 > p1 && p1 > p3) {
    Int = p1;
    return 2;
  }
  if (Equal(s2v2 = vs2 ^ v2, 0) && p4 > p2 && p2 > p3) {
    Int = p2;
    return 2;
  }
  if (Equal(t1v1 = vt1 ^ v1, 0) && p2 > p3 && p3 > p1) {
    Int = p3;
    return 2;
  }
  if (Equal(t2v1 = vt2 ^ v1, 0) && p2 > p4 && p4 > p1) {
    Int = p4;
    return 2;
  } //未交于線上，則判定是否相交
  if(s1v2 * s2v2 > 0 || t1v1 * t2v1 > 0) {
    return 0;
  } //以下為相交的情況，算法詳見文檔
  //計(jì)算二階行列式的兩個(gè)常數(shù)項(xiàng)
  float ConA = p1.x * v1.y - p1.y * v1.x;
  float ConB = p3.x * v2.y - p3.y * v2.x;
  //計(jì)算行列式D1和D2的值，除以系數(shù)行列式的值，得到交點(diǎn)坐標(biāo)
  Int.x = (ConB * v1.x - ConA * v2.x) / Corss;
  Int.y = (ConB * v1.y - ConA * v2.y) / Corss;
  //正交返回1
  return 1;
}
//主函數(shù)
int main(void) {
  //隨機(jī)生成100個(gè)測試數(shù)據(jù)
  for (int i = 0; i < 100; ++i) {
    POINTF p1, p2, p3, p4, Int;
    p1.x = (float)(rand() % 10); p1.y = (float)(rand() % 10);
    p2.x = (float)(rand() % 10); p2.y = (float)(rand() % 10);
    p3.x = (float)(rand() % 10); p3.y = (float)(rand() % 10);
    p4.x = (float)(rand() % 10); p4.y = (float)(rand() % 10);
    int nr = Intersection(p1, p2, p3, p4, Int);
    cout << "[(";
    cout << (int)p1.x << ',' << (int)p1.y << "),(";
    cout << (int)p2.x << ',' << (int)p2.y << ")]--[(";
    cout << (int)p3.x << ',' << (int)p3.y << "),(";
    cout << (int)p4.x << ',' << (int)p4.y << ")]: ";
    cout << nr;
    if (nr > 0) {
      cout << '(' << Int.x << ',' << Int.y << ')';
    }
    cout << endl;
  }
  return 0;
}

關(guān)于stl，貌似用的不多了，不是過時(shí)了，而是有控制的使用，每個(gè)項(xiàng)目都有自己的使用場景，根據(jù)自己的需要選擇合適的技術(shù)。

以上是“C++/STL如何實(shí)現(xiàn)判斷平面內(nèi)兩條線段的位置關(guān)系”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！