| <!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> |
