序言

• 還是那句話，學(xué)習(xí)是為了應(yīng)用。書(shū)到用時(shí)方恨"用得少"

1. 計(jì)算兩條直線的交點(diǎn)

• 直線一般式方程

$$Ax+By+C=0$$

• 設(shè)線段p1-p2對(duì)應(yīng)的直線方程：a1 * x + b1 * y + c1 = 0
• 設(shè)線段p3-p4對(duì)應(yīng)的直線方程：a2 * x + b2 * y + c2 = 0

• 求解方程系數(shù)：

  A = y2 - y1 = p2.y() - p1.y() B = x1 - x2 = p1.x() - p2.x() C = x2 * y1 - x1 * y2 = p2.x() * p1.y() - p1.x() * p2.y()

• 聯(lián)立方程式求交點(diǎn)坐標(biāo)

  a1 * x + b1 * y + c1 = 0 -- (1) a2 * x + b2 * y + c2 = 0 -- (2)(1) * b2 - (2) * b1得到： a1 * b2 * x + b1 * b2 * y + c1 * b2 = 0 a2 * b1 * x + b1 * b2 * y + c2 * b1 = 0兩式相減： x = (c2 * b1 - c1 * b2) / denominator(1) * a2 - (2) * a1得到： a1 * a2 * x + b1 * a2 * y + c1 * a2 = 0 a1 * a2 * x + b2 * a1 * y + c2 * a1 = 0兩式相減： y = (c1 * a2 - c2 * a1) / denominator(注：denominator = a1 * b2 - a2 * b1)

• 即交點(diǎn)坐標(biāo)：

$$(x,y)=(\frac{c2?b1?c1?b2}{a1?b2?a2?b1},\frac{c1?a2?c2?a1}{a1?b2?a2?b1})$$

• 兩條直線的夾角(兩條直線所形成的不大于90°的角)：

  double denominator = a1 * a2 + b1 * b2; double numerator = a1 * b2 - a2 * b1; if (fabs(denominator) < 0.0000001) {return PI / 2.0; // 兩直線垂直 } return fabs(std::atan(numerator / denominator)); // 返回的是弧度值

2. 判斷兩條線段是否相交：方法1

• 直線一般式常規(guī)方法求解。

• 證明兩條線段相交：

  • (1) 證明denominator != 0，denominator == 0表示兩條直線平行
  • (1) 根據(jù)1中公式求解交點(diǎn)坐標(biāo)
  • (2) 證明交點(diǎn)既在線段p1-p2上，也在線段p3-p4上。即如下關(guān)系成立
  r_x0 = (p.x() - p1.x()) / (p2.x() - p1.x()); r_y0 = (p.y() - p1.y()) / (p2.y() - p1.y()); r_x1 = (p.x() - p3.x()) / (p4.x() - p3.x()); r_y1 = (p.y() - p3.y()) / (p4.y() - p3.y()); bool condition_1 = (r_x0 >= 0.0 && r_x0 <= 1.0) || (r_y0 >= 0.0 && r_y0 <= 1); bool condition_2 = (r_x1 >= 0.0 && r_x1 <= 1.0) || (r_y1 >= 0.0 && r_y1 <= 1.0); if (condition_1 && condition_2) {return true; }

• 線段比例計(jì)算：

$$\begin{array}{rl}rati{o}_{x0}& =\frac{p.x?p_1.x}{p_2.x?p_1.x}\\ rati{o}_{y0}& =\frac{p.y?p_1.y}{p_2.y?p_1.y}\\ rati{o}_{x1}& =\frac{p.x?p_3.x}{p_4.x?p_3.x}\\ rati{o}_{y1}& =\frac{p.y?p_3.y}{p_4.y?p_3.y}\end{array}$$

3. 判斷兩條線段是否相交：方法2

• 快速排斥實(shí)驗(yàn)和跨立實(shí)驗(yàn)計(jì)算。

• 證明兩條線段相交：

  • (1) 通過(guò)快速排斥實(shí)驗(yàn)
  • (2) 且通過(guò)跨立實(shí)驗(yàn)
  /* 1. 快速排斥實(shí)驗(yàn) */ bool cond_1 = max(p1.x, p2.x) < min(p3.x, p4.x); bool cond_2 = max(p1.y, p2.y) < min(p3.y, p4.y); bool cond_3 = max(p3.x, p4.x) < min(p1.x, p2.x); bool cond_4 = max(p3.y, p4.y) < min(p2.y, p2.y); if (cond_1 || cond_1 || cond_1 || cond_1) {return false; // 有一個(gè)條件為真，表示兩線段必不相交 } /* 2. 跨立實(shí)驗(yàn) */ if(cross(p3 - p1,p2 - p1) * cross(p4 - p1, p2 - p1) > 0|| cross(p2 - p3, p4 - p3) * cross(p1 - p3, p4 - p3) > 0) {return false; // 叉積 == 0可能共線，但已通過(guò)快速排斥實(shí)驗(yàn)過(guò)濾 } return true;

• 快速排斥實(shí)驗(yàn)：即驗(yàn)證線段的橫坐標(biāo)或縱坐標(biāo)是否總小于或大于另一線段的橫坐標(biāo)或縱坐標(biāo)

• 跨立實(shí)驗(yàn)：通過(guò)叉積證明點(diǎn)p1和p2在p3-p4的兩側(cè)，以及p3和p4在p1-p2的兩側(cè)

  • 兩向量叉積表示向量所在平面的法向量

  • 叉積有一個(gè)非常重要的性質(zhì)，可通過(guò)叉積的符號(hào)來(lái)判斷兩向量的順逆時(shí)針關(guān)系：

    P x Q > 0, 則向量P在向量Q的順時(shí)針?lè)较?#xff1b; P x Q < 0, 則向量P在向量Q的逆時(shí)針?lè)较?#xff1b; P x Q = 0，表示P與Q共線，可能同向也可能反向

  • 若向量P = (x1, y1), Q = (x2, y2)，則向量叉積P x Q = x1 * y2 - x2 * y1

  • 如果兩線段相交，則線段端點(diǎn)相互跨立，即p1, p2分別在p3-p4兩側(cè)，p3, p4分別在p1-p2兩側(cè)

  • 判斷p3、p4分別在p1-p2的兩側(cè)：$(p_1{p}_3\times p_1{p}_2)?(p_1{p}_4\times p_1{p}_2)\le 0$

  • 判斷p1、p4分別在p3-p4的兩側(cè)：$(p_3{p}_2\times p_3{p}_4)?(p_3{p}_1\times p_3{p}_4)\le 0$

4. 總結(jié)

• 方法2比較直觀，方法1判斷兩條線段是否相交比方法2實(shí)現(xiàn)上復(fù)雜一點(diǎn)；
• 方法1能直接計(jì)算線段夾角；
• 方法2叉積可調(diào)用Eigen庫(kù)函數(shù)實(shí)現(xiàn)（待補(bǔ)充）

---

《參考文章》
快速排斥實(shí)驗(yàn)和跨立實(shí)驗(yàn)-1
快速排斥實(shí)驗(yàn)和跨立實(shí)驗(yàn)-2
直線一般式判斷線段相交-1
直線一般式判斷線段相交-2
直線一般式計(jì)算兩直線夾角-1
直線一般式計(jì)算兩直線夾角-2

created by shuaixio, 2022.10.7

總結(jié)

以上是生活随笔為你收集整理的【数学计算】判断两条线段是否相交+计算两条线段的交点和夹角的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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