<!Doctype html>
|
<html>
|
<head>
|
<script src="http://s1.bdstatic.com/r/www/cache/ecom/esl/1-8-8/esl.js"></script>
|
|
<script src="http://ubilabs.github.io/kd-tree-javascript/kdTree.js"></script>
|
|
<meta charset="utf-8">
|
</head>
|
<style>
|
html, body {
|
height: 100%;
|
margin: 0px;
|
}
|
</style>
|
<body>
|
<canvas id="main"></canvas>
|
</body>
|
<script>
|
require.config({
|
packages: [{
|
name: 'echarts',
|
location: '../src',
|
main: 'echarts'
|
}, {
|
name: 'zrender',
|
location: '../../zrender/src',
|
main: 'zrender'
|
}]
|
});
|
|
require(['echarts/data/KDTree'], function (KDTree) {
|
var points = [];
|
var points2 = [];
|
var width = window.innerWidth;
|
var height = window.innerHeight;
|
var canvas = document.getElementById('main');
|
canvas.width = width;
|
canvas.height = height;
|
var ctx = canvas.getContext('2d');
|
for (var i = 0; i < 50000; i++) {
|
var point = [Math.round(width * Math.random()), Math.round(height * Math.random())];
|
points.push({
|
array: point
|
});
|
points2.push(point);
|
}
|
|
var time = performance.now();
|
var kdTree1 = new KDTree(points);
|
console.log(performance.now() - time);
|
|
var squaredDistance = function (a, b) {
|
a = a.array;
|
b = b.array;
|
return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]);
|
}
|
var squaredDistance2 = function (a, b) {
|
return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]);
|
}
|
var kdTree2 = new kdTree(points2, squaredDistance2, [0, 1]);
|
// Find nearest
|
var p2 = [Math.round(width * Math.random()), Math.round(height * Math.random())];
|
p = {
|
array: p2
|
};
|
var time = performance.now();
|
for (var i = 0; i < 50000; i++) {
|
var nearest = kdTree1.nearest(p, squaredDistance);
|
}
|
console.log(performance.now() - time);
|
console.log(p, nearest);
|
|
// Find nearst N
|
var nearestN = [];
|
var time = performance.now();
|
for (var i = 0; i < 50000; i++) {
|
var nearest = kdTree1.nearestN(p, 5, squaredDistance, nearestN);
|
}
|
console.log(performance.now() - time);
|
console.log(p.array, nearestN.map(function(a) {
|
return a.array;
|
}));
|
|
setTimeout(function () {
|
var time = performance.now();
|
for (var i = 0; i < 50000; i++) {
|
var nearest = kdTree2.nearest(p2, 5);
|
}
|
console.log(performance.now() - time);
|
console.log(p2, nearest.map(function(a) {
|
return a[0];
|
}));
|
}, 1000);
|
|
// var buildSplitLines = function (node, minx, miny, maxx, maxy) {
|
// switch (node.axis) {
|
// case 0:
|
// var x = node.data[0];
|
// ctx.moveTo(x + 0.5, miny);
|
// ctx.lineTo(x + 0.5, maxy);
|
// ctx.stroke();
|
// node.left && buildSplitLines(node.left, minx, miny, node.data[0], maxy);
|
// node.right && buildSplitLines(node.right, node.data[0], miny, maxx, maxy);
|
// break;
|
// case 1:
|
// var y = node.data[1];
|
// ctx.moveTo(minx, y + 0.5);
|
// ctx.lineTo(maxx, y + 0.5);
|
// ctx.stroke();
|
// node.left && buildSplitLines(node.left, minx, miny, maxx, node.data[1]);
|
// node.right && buildSplitLines(node.right, minx, node.data[1], maxx, maxy);
|
// break;
|
// }
|
|
// }
|
// ctx.fillStyle = 'black';
|
// buildSplitLines(kdTree1.root, 0, 0, width, height);
|
|
// ctx.fillStyle = 'red';
|
// for (var i = 0; i < points.length; i++) {
|
// var p = points[i];
|
// ctx.fillRect(p[0], p[1], 4, 4);
|
// }
|
})
|
</script>
|
</html>
|
