Measure performance of d3-voronoi and d3-geo-voronoi.
It looks like d3-geo-voronoi is O(n^2), on my computer I have
time (in ms) ≈ 40 * 1e-6 * n^2
n = 100, 0.4s
n = 200, 1.6s
n = 300, 3.6s
n = 500, 10s
n = 700, 19s
n = 1000, 40s
n = 2000, 2.7min
n = 5000, 17min
…
n = 10000, +1h
xxxxxxxxxx
<head>
<meta charset="utf-8">
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="d3-geo-voronoi.min.js"></script>
<style>
body { margin:0;position:fixed;top:50;right:0;bottom:0;left:0; }
</style>
</head>
<body>
<script>
d3.select("body").append("button")
.text('Launch tests')
.on('click', test)
var svg = d3.select("body").append("svg")
.attr("width", 960)
.attr("height", 500)
function test() {
var res = [], line = d3.area();
bars = d3.select('svg').append('path');
for(var i=50; i<=60; i+=5){
var n = i*i;
var c = compare(n);
console.log(c.n, (c.geo/c.voro).toFixed(4));
res.push(c);
display(res);
}
function Y(y){
return 300*y;
}
function display(res){
res = res.map(function(e) {
e.r = +e.geo / (40* 1e-9*Math.pow(e.n, 2) );
return e;
})
var max = d3.max(res.map(function(e){ return e.r }));
console.log(d3.median(res.map(function(e){ return e.r })))
bars
.attr('d', line(res.map(function(e){
return [4*Math.sqrt(e.n), Y(e.r/max)];
})));
}
}
function compare(n){
var data = d3.range(n).map(function(){
return [360*Math.random(), 90*Math.random() - 90*Math.random()];
});
var t0 = performance.now();
d3.voronoi()(data);
var t1 = performance.now() - t0;
t0 = performance.now();
d3.geoVoronoi()(data);
var t2 = performance.now() - t0;
return { n: n, voro: t1, geo: t2, ratio: t2/t1 };
}
</script>
</body>
https://d3js.org/d3.v4.min.js