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(); 

EDIT作品潜在的にオーバーラップする円の配列と開始点と終了点の2点。私たちは、重複している円のパスを作成したいと思います。最初のものから始まり、終わりのもので終わります。いくつかの潜在的な経路が存在する可能性があります。経路があるかどうかを知りたいだけです。

Answer 1

ここでは非常に基本的な衝突チェックシステムを紹介します。更新するたびにCollisionを実行し、衝突を確認している円のパラメータを渡します。あなたは、私はそれが円の多くを使用して作成したプロジェクトのソースをチェックアウトすることができ、さらに

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

をし、衝突をチェックします：ここで

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

は円オブジェクトの例だし、それを呼び出す方法それらのすべてとプレイヤーとの間に 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]を除き、相互に重複している、それが正しいのですか？