Nearest Neighbor Search

200 random points

by Sergei Sokolov

HTML

<script src="https://cdnjs.cloudflare.com/ajax/libs/require.js/2.3.5/require.min.js"></script>

CSS

body {
		  background-color: #333
		}
		
		canvas {
		  border: 1px solid #888
		}
		
		.centered {
		  width: 302px;
		  margin: 10px auto;
		  text-align: center;
		  color: #999;
		  font-family: Helvetica, Tahoma, Arial, sans-serif;
		}

JavaScript

/**
 * для вопроса https://toster.ru/q/455043
 * Как написать алгоритм поиска соседних элементов?
 *
 * non-minified source:
 * https://github.com/sergiks/nearest-neighbor
 */
define("src/point",[],function(){const t=function(t,e){this.L=[],this.x=t,this.y=e,this.v={x:0,y:0},this.speed=0,this.lastUpdate=(new Date).getTime()};return t.prototype.render=function(t){t.fillStyle="rgb(200, 0, 0)",t.fillRect(this.x-2,this.y-2,4,4)},t.prototype.setDirection=function(t,e){var n=t-this.x,i=e-this.y,s=Math.sqrt(n*n+i*i);this.v={x:n/s,y:i/s}},t.prototype.setSpeed=function(t){this.speed=t},t.prototype.update=function(){var t=(new Date).getTime(),e=(t-this.lastUpdate)/1e3,n=e*this.speed;this.x+=this.v.x*n,this.y+=this.v.y*n,this.lastUpdate=t},t}),define("src/link",[],function(){const t=function(t,e){this.a=t,this.b=e};return t.prototype.render=function(t){t.strokeStyle="rgba( 210, 210, 210, 0.5)",t.beginPath(),t.moveTo(this.a.x,this.a.y),t.lineTo(this.b.x,this.b.y),t.stroke()},t}),define("src/points",[],function(){const t=function(t){this.points=t||[],this.length=this.points.length};return t.prototype.add=function(t){return this.points.push(t),this.length=this.points.length},t.prototype.get=function(t){return this.points[t]},t.prototype.getX=function(){return this.points.slice().sort(function(t,e){return t.x-e.x})},t}),requirejs(["src/point","src/link","src/points"],function(t,e,n){function i(t){var n,s,o,h,l,u,f,y,m=c*c;for(d.clearRect(0,0,r.width,r.height),n=0;n<p.length;n++)o=p.get(n),o.update(),o.x<0&&(o.x*=-1,o.v.x*=-1),o.y<0&&(o.y*=-1,o.v.y*=-1),o.x>300&&(o.x=600-o.x,o.v.x*=-1),o.y>300&&(o.y=600-o.y,o.v.y*=-1),o.render(d);for(l=p.getX(),n=0;n<l.length;n++)for(o=l[n],[],s=n-1;s>=0;s--)h=l[s],u=o.x-h.x,f=o.y-h.y,y=f*f,u<=c&&y<=m&&u*u+y<=m&&new e(o,h).render(d);a.samples.push(t),a.samples.length===a.window+1&&(a.div.innerText=(1e3*a.window/(a.samples[a.window]-a.samples[0])).toFixed(2)+" fps",a.samples=a.samples.slice(-1)),window.requestAnimationFrame(i)}var...