在d3中添加點到Voronoi圖中

Question

我正在使用d3創建一個圖表，嘗試加快在平面上繪製點的函數內最近的nabour搜索。

有沒有辦法直接給圖添加點，所以我可以在while循環中添加點而不是重新繪製整個voronoi？

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專家，但我會分享我發現了什麼。所實現的Voronoi圖的算法是Fortune's algorithm。這是計算Voronoi圖的經典算法。插入一個新點既不是該算法的一部分，也不是功能集的一部分。但是你是正確的，插入一個新的站點並不需要在理論上重新繪製整個圖。

---

您使用NON（最近鄰居搜索）的Voronoi圖。您也可以使用2d-tree來完成NNS。插入和刪除更容易。快速搜索顯示了javascript中的兩個實現：kd-tree-javascript和kd-tree-js。