快速檢查實體是否相交？

Question

我有一系列實體（Manager.Scene.Entities），技術上是圈子。
和我有一個方法，返回實體數組與當前實體相交：

var Intersected = Manager.Scene.Entities.filter(function (another) { 
     //check cases that not initiate intersection to prevent extra calculations 
     if (self.radius < another.radius 
      || another.id == self.id 
      || self.className == another.className) 
      return false; 

     //check circles intersections 
     var dx = self.x - another.x; 
     var dy = self.y - another.y; 
     dx = dx * dx + dy * dy; 
     dy = self.radius + another.radius; 

     return dx < dy * dy; 
    }); 

我型材，並注意到，該方法需要的執行時間，28％（看照片）。


是否有可能以某種方式進行優化？

---

PS。我修改了交點檢查，現在它找到了附近的實體，並且檢查了交點。它需要ex的21％。時間，而不是28％。

var Nearest = Manager.Scene.Entities.filter(function (another) { 
     return self.x * 2 > another.x || self.x/2 < another.x || self.y * 2 > another.y || self.y/2 < another.y; 
    }); 

    var Intersected = Nearest.filter(function (another) { 
     if (self.radius < another.radius || another.id == self.id || self.className == another.className) 
      return false; 

     var dx = self.x - another.x; 
     var dy = self.y - another.y; 
     dx = dx * dx + dy * dy; 
     dy = self.radius + another.radius; 

     return dx < dy * dy; 
    }); 

Answer 1

通過預先計算可能相交的夫婦，您只需花費很少的努力就可以贏得大量時間。每次添加/刪除實體時，都要保持這樣的數組是最新的，並且您可以避免第一次測試。
提供您的身份證是在行動上一個id，代碼可能看起來像：

var colliders []; 
var possibleCollisions = []; 

function addCollider(newCollider) { 
    if (colliders.indexOf(newCollider)>=0) throw('collider already added'); 
    colliders.forEach(function(c) { 
     if ((c.radius>newCollider.radius) && (c.class!=newCollider.class)) 
      possibleCollision.push([ c, 
            newCollider, 
          Math.pow(c.radius + newCollider.radius,2) ]); 
    }); 
    colliders.push(newCollider); 
} 

function removeColliders(deadCollider) { 
    var deadColliderIndex = colliders.indexOf(deadCollider); 
    if (deadColliderIndex==-1) throw('collider already removed'); 
    possibleCollision = possibleCollision.filter(
     function(pc) { return ((pc[0]!=deadCollider)&&(pc[1]!=deadCollider)); 
    }); 
    colliders.splice(deadColliderIndex, 1); 
} 

我們測試的所有碰撞，迭代裏面possibleCollisions。

請注意，您可以存儲半徑（或其平方）的總和以進一步優化事物。

function detectCollision(possibleCollision) { 
    var a = possibleCollision[0], b = possibleCollision[1], 
      radiusSumSq = possibleCollision[3]; 
    var dx = a.x - b.x; 
    var dy = a.y - b.y; 
    return dx*dx + dy*dy <= radiusSumSq; 
}