以線段爲中心點的邊界框的高效交集算法

對於在stackoverflow上列出的類似問題，有很多貼近而有用的答案，但是我還沒有發現任何與我的特例相匹配的答案。以線段爲中心點的邊界框的高效交集算法

我需要一個性能高效的算法來計算邊界框與從中心點發出的線段的交集。每個邊界框可能有多個線段發射。通過定義我的問題，每個線段將與Bounding Box邊線段中的一個（除了4個點以外）相交。

下面是一個例子。

Four Bounding Boxes connected with Line Segments emanating from center points

我要趕緊和計算「廉價」計算：

哪個邊界框緣的線相交段？
邊緣和線段相交的點是什麼？

謝謝。

來源

2013-05-21 Love and peace - Joe Codeswell

我假設你給出了線的起點和終點以及邊界框的大小？你目前使用什麼算法，速度如何？ –

爲什麼不開始計算你在學校學到的兩條線的交點。 – AlexWien

設C是邊界框的中心，P是段的另一個端點。假設V =（Vx，Vy）= P-C是從C指向P的矢量。

讓邊界框的高度= 2 * H和寬度= 2 * W。W和H是法線的一半高度和寬度，這將使得計算更簡單。

這裏有個想法：考慮一下V在第一象限的情況，所以Vx> 0且Vy> 0。然後該段與頂側或右側相交。我們可以通過比較V的斜率和從盒子中心到右上角的線段斜率來判斷哪一個。如果坡度較大，則它與頂部相交，否則與相交。因此，如果V處於第一象限，並且如果Vy/Vx> H/W，則該段與頂部相交。如果Vy/Vx < H/W，它與側面相交。如果它們相等，則它與角落相交。

一旦你知道它相交的一面，你可以使用類似的三角形來確定交點。如果它在點I =（Ix，H）處與頂部相交，則Vx/Vy = Ix/H或Ix = H * Vx/Vy。如果它與點I =（W，Iy）處的邊相交，則Vy/Vx = Iy/W或Iy = W * Vy/Vx。

相同的方法將在其他象限中工作;你只需要跟蹤Vx和Vy的跡象。通過聲明返回值滿足符號（Ix）==符號（Vx）和符號（Iy）==符號（Vy），可以使您的生活變得更輕鬆。

還要注意的是，如果你是小心的跡象，就可以避免師：VY/Vx的> H/W，相當於VY * W> Vx的* H，假定Vx的> 0

來源

2013-05-21 20:58:29

假設你有一個以（0,0）爲中心的方框，長度爲2的邊。假設您有一個從框中心向外輻射的矢量（dx，dy）。然後這將計算（xp，yp）光線與邊緣相交的點。

它執行兩個fabs，兩個比較，一個分區和兩個分配。然後，你只需要翻譯和縮放到你的特定方塊。

if (fabs(dx) > fabs(dy)){ 
    if (dx > 0){ 
    xp = 1;  // right side 
    yp = dy/dx; 
    } else { 
    xp = -1;  // left side 
    yp = -dy/dx 
    } 
} else { 
    if (dy > 0){ 
    yp = 1;  // top side 
    xp = dx/dy; 
    } else { 
    yp = -1;  // bottom side 
    xp = -dx/dy 
    } 
}

來源

2013-05-21 23:11:05

（在第一行代碼中缺少右括號） – beroe

以線段爲中心點的邊界框的高效交集算法

回答

相關問題