快速检查实体是否相交？

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; 
}