計算線段之間的交點

關於stackowerflow線段之間的交點有很多問題，這裏還有一個問題！對不起，我需要幫助才能瞭解如何計算交叉點。我在這裏閱讀了幾個問題，並在其他網站上查看了幾個示例，但我仍然感到困惑，不明白！我不喜歡在沒有事情的情況下複製和粘貼代碼。計算線段之間的交點

到目前爲止，我知道我要比較像Ax，Ay，Bx，By，Cx，Cy，Dx，Dy等每個線段的點。有人可以向我解釋我要計算什麼，如果有交叉點，計算的結果是什麼？

這是我看到的示例代碼之一。我想我不需要相交點，只是爲了知道這些線是否相交。

public static Point lineIntersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) { 
    double denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1); 
    if (denom == 0.0) { // Lines are parallel. 
    return null; 
    } 
    double ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3))/denom; 
    double ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3))/denom; 
    if (ua >= 0.0f && ua <= 1.0f && ub >= 0.0f && ub <= 1.0f) { 
     // Get the intersection point. 
     return new Point((int) (x1 + ua*(x2 - x1)), (int) (y1 + ua*(y2 - y1))); 
    } 

    return null; 
    }

我是否還需要計算一些像這個代碼示例中的值？

For lines through points (x0,y0) and (x1,y1), let xm = (x0+x1)/2, ym = (y0+y1)/2 (median of line segment). 
Then a = (y1-y0) and b = (x0-x1). 
If you evaluate c = a(x-xm)+b(y-ym), c=0 for (x,y) on the line, and the sign(c) tells you which side a point is on

來源

2013-05-01 3D-kreativ

是你的點整數或浮點數？ – 2013-05-02 00:02:21

的告訴你第一段代碼是基於向量跨產品，已經在一個偉大的詳細解釋How do you detect where two line segments intersect?。

IMO，理解它的一種更簡單的方法是通過求解一個方程組。首先看一般的線條，然後從它們中剪切出線段。下面我使用符號給定段((x1, x2), (y1, y2))和((x3, x4), (y3, y4))。

檢查是否有任何行是垂直的（或x1 == x2x3 == x4）。

a。如果兩者都是垂直的並且x1 != x3，那麼沒有交集。

b。如果兩者都是垂直的並且x1 == x3，請檢查(y1, y2)和(y3, y4)是否重疊。

c。如果只有一個是垂直的（比如說第一個），然後建立第二條線的方程（如下所述），找出兩條線相交的點（通過將x1代入第二條線的方程）並檢查這一點在兩個分段內（類似於步驟5）。 d）。如果沒有，繼續。

使用點座標來構建y = a*x + b（如here）形式的線方程。

a1 = (y2-y1)/(x2-x1) 
b1 = y1 - a1*x1 
a2 = (y4-y3)/(x4-x3) 
b2 = y3 - a2*x3

檢查線平行（相同的斜率a）。如果是，請檢查它們是否具有相同的截距b。如果是，請檢查1D區段(x1, x2)和(x3, x4)是否重疊。如果是的話，你的部分確實重疊。線條平行的情況可能不明確。如果它們重疊，則可以將其視爲交叉點（如果它們的末端觸及，它甚至可以是一個點），或者不是。注意：如果你正在使用浮動，它會有點棘手，我估計你會忽略這一點。如果你只有整數檢查是否a1 = a2相當於：如果線不平行
```
if((y2-y1)*(x4-x3) == (x2-x1)*(y4-y3)) 
```
。交點相當於表示兩條線的方程組的解。真的，y = a1*x + b1和y = a2*x + b2相交基本意味着這兩個等式都成立。通過將兩個右側等同來解決這個問題，它會給你交點。其實，你只需要交點座標x（畫它，你就會明白爲什麼）：
```
x0 = -(b1-b2)/(a1-a2) 
```
最後一步是這兩個領域內檢查交點x0謊言。即，min(x1, x2) < x0 < max(x1, x2)和min(x3, x4) < x0 < max(x3, x4)。如果是的話，你的線條相交！

來源

2013-05-01 07:09:48 sashkello

嗯，只是另一個例子。之前我已經看到過，但與其他所有示例一樣，它就像一門外語！我想我的數學能力有點有限，但我不想阻止我學習。 – 2013-05-01 07:15:32

我已將所有位置存儲爲數組列表中的點，並且需要將它們傳遞給檢查是否存在交集的方法。但我不知道如何開始？我想我只需要檢查是否重疊！？ – 2013-05-01 07:16:53

一些示例代碼以及一些解釋將會得到真正的優化。 – 2013-05-01 07:23:44

public void fixData() 
{ 
    slope = (p2.getY() - p1.getY())/(p2.getX() - p1.getX()); 
    yInt = p1.getY() - slope * p1.getX(); 
    xInt = (-yInt)/slope; 
}

來源

2016-11-07 15:57:10 user7127290

我真的@ sashkello的答案，並發現它是更直觀，更容易比向量執行解釋。特別是在將這種代碼添加到代碼庫時。

我會告訴你說你可以使用Java的Line2D幫助器方法。

Line2D.linesIntersect(double x1, double y1, 
         double x2, double y2, 
         double x3, double y3, 
         double x4, double y4)

唯一的拉回是，它要求你要考慮段是相交，即使他們剛剛接觸（在兩個端點和線本身）。

例如，下面的幾行被認爲是相交的，因爲它們共享點（1,1）。

L1 = [(0,0),(1,1)] 
L2 = [(1,1),(2,3)]

如果這是一個問題，您可以添加4個檢查，看看點是否相等。

如果您擔心某個點落在某一點上，那麼您需要做更多的工作，並且您可能會更好地自行實施，以便您可以在算法本身中執行檢查。

如果這些邊緣情況都沒有影響到您，那麼Line2D.linesIntersect就是爲您服務的。 :)

來源

2016-12-21 19:34:34

計算線段之間的交點

回答

相關問題