javascript：在阵列中找到重叠的圆圈

Question

如何修复此代码以正确检测重叠的圆圈？ 第一个圆圈是通过测试起点的位置来指定的。这第一个圆应该是重叠圆图的基础。现在，如果测试圈在非分支线重叠，它只能......

（个人圈来为[X，Y，半径]）

var circles = [ 
    [6, 19, 1], 
    [6, 11, 4], 
    [8, 17, 3], 
    [19, 19, 2], 
    [19, 11, 4], 
    [15, 7, 6], 
    [12, 19, 4] 
]; 
var i = 0; 
var j = 0; 
var start = [10, 19]; 
var starts = false; 
var overlapping = []; 

var isInside = function(point, list, check, push) { 
    var temp = list.filter(function(item) { return Math.pow(item[0] - point[0], 2) + Math.pow(item[1] - point[1], 2) < item[2] * item[2] }); 
    if (push) { overlapping = overlapping.concat(temp) }; 
    return temp.length > 0 
}; 

starts = isInside(start, circles, starts, true); 

var overlappingCirclesTest = function() { 
    if (j < circles.length && overlapping.length > 0) { 
     var i = overlapping.length - 1; 
     var r0 = overlapping[i][2]; 
     var r1 = circles[j][2]; 
     var x0 = overlapping[i][0]; 
     var x1 = circles[j][0]; 
     var y0 = overlapping[i][1]; 
     var y1 = circles[j][1]; 
     if (Math.hypot(x0 - x1, y0 - y1) <= (r0 + r1)) { 
      overlapping.push(circles[j]); 
      circles.splice(circles.indexOf(circles[j]), 1); 
      j = 0; 
      overlappingCirclesTest(); 
     } 
     j++; 
     overlappingCirclesTest(); 
    } 
} 
overlappingCirclesTest(); 

编辑：澄清：我们有一组可能重叠的圆圈和两个点，开始和结束。我们想要产生一个重叠圆的路径，从开始的一个开始，到结束的一个结束。可能有几条潜在路径，我们只想知道是否有任何路径。

Answer 1

所以这里是一个非常基本的碰撞检查系统。无论何时更新，运行碰撞并传递您正在检查碰撞的圆的参数。

function Collision (x, y, r) { 
    for (i=0; i<circles.length; i++) { 
     //Distance formula 
     if (Math.sqrt((x-circles[i].x)(x-circles[i].x) + (y-circles[i].y)(y-circles[i].y) < r) { 
      return true; 
    } 
} 

下面是一个圆形物体的例子，以及如何调用它：

function Circle() { 
    this.x = Math.random()*100; 
    this.y = Math.random()*100; 
    this.r = Math.random()*50; 

    this.update = function() { 
     if (Collision(this.x, this.y, this.r) { 
      console.log("circle collided with another circle"); 
     } 
    } 
}; 

此外，您可以检查出我创建了一个使用大量圆的项目源，并检查碰撞在他们和玩家之间。 http://betaio.bitballoon.com

Answer 2

这是一个比较完整的答案，我没有试图想象这些圈子，所以我很难确定这是完全正确的，但我认为这会让你更接近。

我认为该算法是O（N^2），所以它不会很快，但我采取的策略是建立一个索引在每一个重叠的圆上，然后找到一个使用该点，然后基本递归通过重叠索引来查找它在一个组中与其相关的所有环路。

下面是代码：

function circleCollisionDetect (c1, c2) { 
    var dx = c1[0] - c2[0] 
    var dy = c1[1] - c2[1] 
    var distance = Math.sqrt(dx * dx + dy * dy) 
    return distance < c1[2] + c2[2] 
} 

function circlePointCollisionDetect (p, c) { 
    const dx = p[0] - c[0] 
    const dy = p[1] - c[1] 
    const distance = Math.sqrt(dx * dx + dy * dy) 
    return distance < c[2] 
} 

function search (i, circles, index) { 
    const group = [] 
    function follow(i) { 
    if (!~group.indexOf(i)) { 
     group.push(i) 
     const overlaps = index[i] 
     for (let x = 0, n = overlaps.length; x < n; x++) { 
     follow(overlaps[x]) 
     } 
    } 
    } 
    follow(i) 
    return group 
} 

const circles = [ 
    [6, 19, 1], 
    [6, 11, 4], 
    [8, 17, 3], 
    [19, 19, 2], 
    [19, 11, 4], 
    [15, 7, 6], 
    [12, 19, 4] 
] 
const overlaps = [] 
const p = [10, 19] 

// Find one that overlaps the starting point 
const c = circles.find(c => circlePointCollisionDetect(p, c)) 
const start = circles.indexOf(c) 

// Build an index of all overlapping circles 
for (let a = 0, n = circles.length; a < n; a++) { 
    for (let b = 0; b < n; b++) { 
    const c1 = circles[a] 
    const c2 = circles[b] 
    if (c1 === c2) continue; 
    if (!overlaps[a]) overlaps[a] = [] 
    if (circleCollisionDetect(c1, c2)) overlaps[a].push(b) 
    } 
} 

// Next search through the index recursively for unique overlapping circles 
const overlapping = search(start, circles, overlaps) 

console.log('start:', start) 
console.log('index:', overlaps) 
console.log('overlapping:', overlapping) 

它打印：

start: 2 
index: [ [ 2 ], [ 2, 5 ], [ 0, 1, 6 ], [], [ 5 ], [ 1, 4 ], [ 2 ] ] 
overlapping: [ 2, 0, 1, 5, 4, 6 ] 

所以基本上他们都互相重叠，除了[19, 19, 2]，是正确的？