d3でのボロノイ図へのポイントの追加

Question

私は、d3を使って平面上の点をプロットする関数内で最も近いnabour検索を高速化しようとする図を作成しています。

ポイントを直接ダイアグラムに追加する方法があるので、voronoi全体を再描画するのではなく、whileループ内にポイントを追加できますか？

var svg = d3.select("svg") 
 

 
var distance = function(pa, pb) { 
 
    var x = pa[0] - pb[0], 
 
    y = pa[1] - pb[1] 
 
    return Math.sqrt((x * x) + (y * y)) 
 
} 
 
var scatterCircle = function(point, radius, quantity, proximity, margin) { 
 
    var x1 = point[0] - radius, 
 
    y1 = point[1] - radius, 
 
    inner = radius * margin, 
 
    array = [ 
 
     [500, 500] 
 
    ] 
 
    //should be declaring diagram here and addings points below// 
 
    while (array.length < quantity) { 
 
    //constructing new diagram each loop to test function, needs add to diagram function// 
 
    var newpoly = d3.voronoi()(array), 
 
     x = x1 + (radius * 2 * Math.random()), 
 
     y = y1 + (radius * 2 * Math.random()), 
 
     ii = newpoly.find(x, y).index 
 
    var d = distance(array[ii], [x, y]), 
 
     e = distance([x, y], point) 
 
    if (e < inner) { 
 
     if (d > proximity) { 
 
     array.push([x, y]) 
 
     } 
 
    } 
 
    } 
 
    return array 
 
} 
 
var test = scatterCircle([500, 500], 500, 1500, 10, 0.9) 
 
var o = 0 
 
while (o < test.length) { 
 
    svg.append("circle") 
 
    .attr("cx", test[o][0]) 
 
    .attr("cy", test[o][1]) 
 
    .attr("r", 1) 
 
    o++ 
 
}

<script src="https://d3js.org/d3.v4.js"></script> 
 
<svg width="1000" height="1000">

Answer 1

私はd3.jsには専門家でないが、私は私が見つけたものを共有することになります。ボロノイ図のアルゴリズムはFortune's algorithmです。これは、ボロノイ図を計算する古典的なアルゴリズムです。新しいポイントを挿入することは、このアルゴリズムの一部でもなく、機能セットの一部でもありません。しかし、あなたは正しいです、1つの新しいサイトを挿入することは、ダイアグラム全体を理論的に再描画する必要はありません。

---

NNS（最近傍検索）用のボロノイ図を使用します。また、2d-treeを使用してNNSを達成することもできます。挿入と取り外しが簡単です。クイック検索では、javascriptの2つの実装、すなわちkd-tree-javascriptとkd-tree-jsが明らかになりました。