碰撞檢測：分離軸定理 - 圓與多邊形

Question

我一直試圖根據Randy Gaul's C++ Impulse Engine基於Randy Gaul's C++ Impulse Engine來實現圓和多邊形之間的碰撞檢測，緊跟在代碼後面，但算法從不返回true。這個是JSFiddle。 （該機構正在使用的方便HTML5的Canvas API渲染）

代碼（只是碰撞檢測）的一個片段：

const circPoly = (a, b) => { 
    let data = {}, 
    center = a.pos; 
    data.contacts = []; 
    center = b.mat.clone().trans().mult(center.clone().sub(b.pos)); 
    let sep = -Number.MAX_VALUE, 
    faceNorm = 0; 
    for (let i = 0; i < b.verts2.length; ++i) { 
    let sep2 = b.norms[i].dot(center.clone().sub(b.verts2[i])); 
    if (sep2 > a.radius) return data; 
    if (sep2 > sep) { sep = sep2; faceNorm = i; } 
    } 
    let v1 = b.verts2[faceNorm], 
    v2 = b.verts2[faceNorm + 1 < b.verts2.length ? faceNorm + 1 : 0]; 
    if (sep < 0.0001) { 
    data.depth = a.radius; 
    data.norm = b.mat.clone().mult(b.norms[faceNorm]).neg(); 
    data.contacts[0] = data.norm.clone().vmult(a.pos.clone().sadd(a.radius)); 
    return data; 
    } 
    let dot1 = center.clone().sub(v1).dot(v2.clone().sub(v1)), 
    dot2 = center.clone().sub(v2).dot(v1.clone().sub(v2)); 
    data.depth = a.radius - sep; 
    if (dot1 <= 0) { 
    if (center.dist2(v1) > a.radius * a.radius) return data; 
    let norm = v1.clone().sub(center); 
    norm = b.mat.clone().mult(norm); 
    norm.norm(); 
    data.norm = norm; 
    v1 = b.mat.clone().mult(v1.clone().add(b.pos)); 
    data.contacts[0] = v1; 
    } else if (dot2 <= 0) { 
    if (center.dist2(v2) > a.radius * a.radius) return data; 
    let norm = v2.clone().sub(center); 
    norm = b.mat.clone().mult(norm); 
    norm.norm(); 
    data.norm = norm; 
    v2 = b.mat.clone().mult(v2.clone().add(b.pos)); 
    data.contacts[0] = v2; 
    } else { 
    let norm = b.norms[faceNorm]; 
    if (center.clone().sub(v1).dot(norm) > a.radius) return data; 
    norm = b.mat.clone().mult(norm); 
    data.norm = norm.clone().neg(); 
    data.contacts[0] = data.norm.clone().vmult(a.pos.clone().sadd(a.radius)); 
    } 
    return data; 
}; 

注意b.verts2指多邊形的頂點在現實世界中的座標。

我知道一個事實，即Vector類沒有問題，但由於我對轉換矩陣並沒有太多的經驗，所以這個類可能是這些錯誤的根源，儘管它的代碼很漂亮它也完全來源於脈衝引擎，因此它應該可以工作。如前所述，即使發生碰撞，該算法也總是返回false。我在這裏做錯了什麼？我試着拿出早期的回報，但這只是返回奇怪的結果，例如帶有負座標的接觸點，這顯然不太正確。

編輯：修改了我的矢量類的垂直函數，以與脈衝引擎相同的方式工作（兩種方式都是正確的，但我認爲一個是順時針的而另一個是逆時針的 - 我還修改了頂點以反映逆時針方向，岬）。不幸的是，它仍然沒有通過測試。

https://jsfiddle.net/khanfused/tv359kgL/4/

Answer 1

好了很多問題，我真的不明白你正在嘗試做的，因爲它似乎過於複雜。例如爲什麼矩陣有trans ???爲什麼你使用Y屏幕作爲變換的座標系？ （修辭）

在第一個循環中。

• 首先是您正在測試每個垂直的法向矢量 的距離，應該測試垂直位置。
• 此外，您還可以使用vec.dot函數找到距離，即 返回距離的平方。但是你測試半徑，你 應該測試爲if(sep2 < radius * radius)
• 和你有比較你周圍的錯誤的方式應該是 測試，如果小於半徑的平方（不大於）
• 然後，當你做檢測vert在半徑範圍內返回數據 對象，但忘記將在 ,data.contacts數組中的圓圈內發現的垂直。
• 我不知道維持最 遙遠VECT指數的意圖是什麼，但隨後該函數的其餘部分使零意義 我???? :(我試圖理解它。

所有你需要做的是

的檢查，如果在聚任何綠黨比半徑更近，如果是的話那麼你有一個攔截（或完全是內部）

然後，你需要檢查每個線段

可以與以下每條線段來完成的距離，如果你不需要的攔截（或下方，如果你需要攔截）只使用一個或另一個。

// circle is a point {x:?,y:?} 
// radius = is the you know what 
// p1,p2 are the start and end points of a line 
     checkLineCircle = function(circle,radius,p1,p2){ 
      var v1 = {}; 
      var v2 = {}; 
      var v3 = {}; 
      var u; 
      // get dist to end of line 
      v2.x = circle.x - p1.x; 
      v2.y = circle.y - p1.y; 
      // check if end points are inside the circle 
      if(Math.min(
        Math.hypot(p2.x - circle.x, p2.y - circle.y), 
        Math.hypot(v2.x, v2.y) 
       ) <= radius){ 
       return true; 
      } 
      // get the line as a vector 
      v1.x = p2.x - p1.x; 
      v1.y = p2.y - p1.y; 
      // get the unit distance of the closest point on the line 
      u = (v2.x * v1.x + v2.y * v1.y)/(v1.y * v1.y + v1.x * v1.x); 
      // is this on the line segment 
      if(u >= 0 && u <= 1){ 
       v3.x = v1.x * u; // get the point on the line segment 
       v3.y = v1.y * u; 
       // get the distance to that point and return true or false depending on the 
       // it being inside the circle 
       return (Math.hypot(v3.y - v2.y, v3.x - v2.x) <= radius); 
      } 
      return false; // no intercept 
     } 

對於每一行都這樣做。爲了節省時間，將圓心轉換爲多邊形局部，而不是轉換多邊形上的每個點。

如果您需要截取的點，然後使用以下功能

// p1,p2 are the start and end points of a line 
// returns an array empty if no points found or one or two points depending on the number of intercepts found 
// If two points found the first point in the array is the point closest to the line start (p1) 
function circleLineIntercept(circle,radius,p1,p2){ 
     var v1 = {}; 
     var v2 = {}; 
     var ret = []; 
     var u1,u2,b,c,d; 
     // line as vector 
     v1.x = p2.x - p1.x; 
     v1.y = p2.y - p1.y; 
     // vector to circle center 
     v2.x = p1.x - circle.x; 
     v2.y = p1.y - circle.y; 
     // dot of line and circle 
     b = (v1.x * v2.x + v1.y * v2.y) * -2; 
     // length of line squared * 2 
     c = 2 * (v1.x * v1.x + v1.y * v1.y); 
     // some math to solve the two triangles made by the intercept points, the circle center and the perpendicular line to the line. 
     d = Math.sqrt(b * b - 2 * c * (v2.x * v2.x + v2.y * v2.y - radius * radius)); 
     // will give a NaN if no solution 
     if(isNaN(d)){ // no intercept 
      return ret; 
     } 
     // get the unit distance of each intercept to the line 
     u1 = (b - d)/c; 
     u2 = (b + d)/c; 

     // check the intercept is on the line segment 
     if(u1 <= 1 && u1 >= 0){ 
      ret.push({x:line.p1.x + v1.x * u1, y : line.p1.y + v1.y * u1 }); 
     } 
     // check the intercept is on the line segment 
     if(u2 <= 1 && u2 >= 0){ 
      ret.push({x:line.p1.x + v1.x * u2, y : line.p1.y + v1.y * u2}); 
     } 
     return ret; 
    } 

我把它留給你做的多邊形迭代。