角上的圓線段碰撞

Question

我發現這2個神奇的教程如何檢測和處理圓與線段碰撞。

seb.ly
tuts plus

我實現了它在C＃中沒有任何問題。 我喜歡這個解決方案，因爲它是一個乾淨而簡單的解決方案。
但是沒有解釋如何處理線端/拐角上的碰撞。
添加此功能的最佳方式是什麼？

左側說明了我的函數如何表現如此。 在右邊，我想表現得如何。 案件和工作很好，正是我想要的。 但是，如果圓圈不會發生碰撞。 我必須執行類似於右側的操作。 但我不知道這可以如何工作。
到目前爲止，我有這樣的：

// A line is defined by two points. 
// A circle is define by a point and a radius. 
public static bool CircleVsLine(Circle circle, Vector2d circleDirection, ref Vector2d circleSolved, Line line) 
{ 
    // Circle position before movement. 
    Vector2d circle0 = circle.Position; 

    // Circle position after movement. 
    Vector2d circle1 = circle.Position + circleDirection; 

    Vector2d lineDirection = line.Position1 - line.Position0; 
    Vector2d lineNormal = new Vector2d(lineDirection.Y, -lineDirection.X).Normalized(); 

    Vector2d circle0ToLine0Direction = line.Position0 - circle0; 
    Vector2d circle1ToLine0Direction = line.Position0 - circle1; 

    // Calculate distance to line before movement. 
    double circle0DistanceToLine = Vector2d.Dot(lineNormal, circle0ToLine0Direction); 

    // Calculate distance to line after movement. 
    double circle1DistanceToLine = Vector2d.Dot(lineNormal, circle1ToLine0Direction); 

    // The time when the circle radius equals the distance to the line. 
    double t = (circle.Radius - circle0DistanceToLine)/(circle1DistanceToLine - circle0DistanceToLine); 

    // If true collision on endless line occured. 
    if (t >= 0 && t <= 1) 
    { 
     // EPSILON is a very small double number to prevent bugs caused by rounding errors. 
     circleSolved = circle0 + circleDirection * t - lineNormal * EPSILON; 

     Vector2d line0ToPlayerSolved = circleSolved - line.Position0; 
     Vector2d line1ToPlayerSolved = circleSolved - line.Position1; 

     // If true collision happened on the line sgment. 
     if (Vector2d.Dot(lineDirection, line0ToPlayerSolved) >= 0 && Vector2d.Dot(lineDirection, line1ToPlayerSolved) < 0) 
     { 
      return true; 
     } 
    } 

    // No collision so circle can be moved. 
    circleSolved = circle1; 
    return false; 
} 

Answer 1

你的代碼的第一部分承擔無限線。然後，第二部分試圖糾正第一個決定。但是，這並不總是可能的，因爲你的例子顯示。所以我們需要在第一步中考慮線路長度。

首先，我們分析線端點。我們要查找的參數t其中圓觸及端點：

|| circle0 + t * circleDirection - endpoint || == r 

解決的辦法是：

discriminant = 4 * (dot(circle0, circleDirection) - dot(circleDirection, endpoint))^2 
       -4 * circleDirection^2 * (circle0^2 - 2 * dot(circle0, endpoint) + endpoint^2 - r^2) 

t = (-dot(circle0, circleDirection) + dot(circleDirection, endpoint) 
     -1/2 * sqrt(discriminant))/circleDirection^2 

的符號someVector^2表示向量的平方長度。如果判別式是否定的，圓將永遠不會觸及終點。然後，要麼完全通過線路，要麼將其打到中間的某個地方。你的代碼已經可以處理這種情況，所以我跳過這個。基本上，你會檢查，它是哪種情況，然後繼續。

如果判別式是肯定的，圓可以觸及終點。如果t大於1，則不會在當前模擬時間步驟中發生。所以你可以忽略它。但如果它介於0和1之間，則必須採取行動。

首先，您必須檢查它是否會停止圓或線段的終點。您可以通過圓心投影到線檢查：

circleCollisionPosition = circle0 + t * circleDirection 
directionToCollisionPosition = circleCollisionPosition - line.Position0 
s = dot(directionToCollisionPosition, lineDirection)/lineDirection.SquaredLength 

現在，如果s是0和1之間，圓由線段停止。不是由一個端點。然後，您可以從無限行重新計算t（如您在代碼中所做的那樣）。如果s小於0，則圓圈將由第一個端點停止，您應該使用第一個端點的t。如果s大於1，則圓圈由第二個端點停止，您應該使用根據t。如果一個端點產生s < 0和一個s > 1，則使用t中的較小者。

然後通過計算circleSolved，你在你的代碼沒有繼續。這將是它不再移動的圓圈的最終位置。隨後的檢查不再需要，因爲它已經發生。