HTML5 Canvas draw line distance between points

Question

I'm trying to learn HTML5 and found a very simple particle system wich i modded a bit. I would like to create a line, between particles, if the distance between the particles is within the range 0-20.

What I currently have draws a line between every particle, no matter the distance.

This is where I try to check the distance, but I can't figure out how to do this. Would appreciate any help and explanations. Thanks in advance.

           // This particle
            var p = particles[t];

            // Check position distance to other particles
            for (var q = 0; q < particles.length; q++) {

                if (particles[q].x - p.x < line_distance || p.x - particles[q].x < line_distance) {
                    ctx.beginPath();
                    ctx.lineWidth = .1;
                    ctx.strokeStyle = '#fff';
                    ctx.moveTo(p.x, p.y);
                    ctx.lineTo(particles[q].x, particles[q].y);
                    ctx.stroke();
                }

            }

// Request animation frame
var requestAnimationFrame = window.requestAnimationFrame || 
    window.mozRequestAnimationFrame || 
    window.webkitRequestAnimationFrame || 
    window.msRequestAnimationFrame;

// Canvas
var canvas = document.getElementById('canvas');
var ctx = canvas.getContext('2d');

// Set fullscreen
canvas.width = document.documentElement.clientWidth;
canvas.height = document.documentElement.clientHeight;

// Options
var num =30;            // Number of particles to draw
var size = 3;           // Particle size
var color = '#fff';     // Particle color
var min_speed = 1;      // Particle min speed
var max_speed = 3;      // Particle max speed
var line_distance = 20; // This is the max distance between two particles
// if we want to draw a line between them

// Particles array
var particles = [];
for (var i = 0; i < num; i++) {
  particles.push(
    new create_particle()
  );
}

// Lets animate the particle
function draw() {

  // Background
  ctx.fillStyle = "#000";
  ctx.fillRect(0, 0, canvas.width, canvas.height);

  // Lets draw particles from the array now
  for (var t = 0; t < particles.length; t++) {

    // This particle
    var p = particles[t];

    for (var q = 0; q < particles.length; q++) {

      // Check position distance
      if (particles[q].x - p.x < line_distance || p.x - particles[q].x < line_distance) {
        ctx.beginPath();
        ctx.lineWidth = .1;
        ctx.strokeStyle = '#fff';
        ctx.moveTo(p.x, p.y);
        ctx.lineTo(particles[q].x, particles[q].y);
        ctx.stroke();
      }

    }

    // Color
    ctx.fillStyle = color;

    // Circle path
    ctx.beginPath();
    ctx.arc(p.x, p.y, p.radius, Math.PI * 2, false);
    ctx.fill();

    // Lets use the velocity now
    p.x += p.vx;
    p.y += p.vy;

    // If there is only 1 particle
    // show X, Y, and velocity
    if (num === 1) {
      ctx.fillText('Y:'+ p.y, 20, 20);
      ctx.fillText('X:'+ p.x, 20, 40);
      ctx.fillText('YV:'+ p.vy, 20, 60);
      ctx.fillText('XV:'+ p.vx, 20, 80);
    }

    // To prevent the balls from moving out of the canvas
    if (p.x < size) p.vx*= (p.vx / -p.vx);
    if (p.y < size) p.vy*= (p.vy / -p.vy);
    if (p.x > canvas.width - size) p.vx*= (-p.vx / p.vx);
    if (p.y > canvas.height - size) p.vy*= (-p.vy / p.vy);

  }

  // Loop
  requestAnimationFrame(draw);

}

// Function for particle creation
function create_particle() {

  // Random position
  this.x = Math.random() * canvas.width;
  this.y = Math.random() * canvas.height;

  // Velocity
  this.vx = random_int_between(min_speed, max_speed);
  this.vy = random_int_between(min_speed, max_speed);

  // Color & Size
  this.color = color;
  this.radius = size;

}

// Random number between (used for speed)
function random_int_between(min, max) {
  return Math.floor(Math.random() * max) + min;
}

draw();

<canvas id="canvas"></canvas>

Answer 1

N body Particle systems

As this is an N body case and no one said anything about CPU load.

CPU Load

Particle systems can quickly bog down a CPU in an overload of processing. This is particularly true when you are testing each particle against the other. As particle systems are almost always for realtime graphics ineffective coding can destroy the whole animation.

Do nothing not needed

First as you are only looking for a threshold distance you can optimise the calculations by not continuing to calculate as soon as you know that there is a fail in the test.

So set up the threshold distance

var dist = 20;
var distSq = dist * dist; // No need to square this inside loops

Then in the loop as you calculate test and continue. Assuming p1 and p2 are particles

x = p2.x-p1.x;  // do x first
if((x *= x) < distSq){ // does it pass?? if not you have saved calculating y
    y = p2.y-p1.y; // now do y as you know x is within distance
    if(x + (y * y) < distSq){ // now you know you are within 20
         // draw the line

Assuming only 1/6 will pass and 1/3 come close you save over half the CPU load. You will also notice that I don't use the CPU heavy sqrt of the distance. There is no need as there is a one to one match between a number and the square of a number. If the square root of a number is less than the distance so will the square of the number be less than the square of the distance.

N body Squared

Never do a N body sim with two for loops like this.

for(i = 0; i < particles.length; i ++){
    for(j = 0; j < particles.length; j ++){
       // you will test all i for j and all j for i but half of them are identical
       // and the square root of the number are self to self

This hurts me just to look at as the solution is so so simple.

Assuming you have 100 particles at 60 frames a second you are doing 60 * 100 * 100 comparisons a second (600,000) for 100 particles. Thats is a total waste of CPU time.

Never do something twice, or that you know the answer to.

To improve the for loops and avoid testing distances you already know and testing how far each particle is from itself

var len =  particles.length;  // move the length out as it can be expensive
                              // and pointless as the value does not change;
for(i = 0; i < len; i ++){
    for(j = i + 1; j < len; j ++){
       // Now you only test each particle against each other once rather than twice

Thus with just a few simple characters (for(j = 0 becomes for(j = i + 1) you more than half the CPU load, from 600,000 comparisons down to less than 300,000

The human eye is easy to fool

Fooling the eye is the best way to get extra performance from your animations.

This is a visual effect and the human eye does not see pixels nor does it it see individual frames at 1/60th a second, but it does see a drop in frame rate. Creating a complex particle system can an excellent FX but if it drops the frame rate the benefit is lost. Take advantage of the fact that pixels are to small and 1/20th of a second is way beyond the human ability to find error is the best way to optimise FXs and add more bang per CPU tick.

The demo below has two particle sims. 100 points each. Any points that come within 49 pixels have a line drawn between them. One does all the stuff I demonstrated above the other sacrifices a little memory and a lot off acuracy and only calculates the distances between 1/3rd of the points every frame. As the max speed can be close to half the line length a frame, skipping 2 frames can make a line twice as long or two points be too close without a line. There is a massive CPU saving in doing this, but you can not pick which is which.

Click on which sim you think is skipping points to find out which is which.

var canvas = document.createElement("canvas"); 
canvas.width= 540;
canvas.height = 270; 
var ctx = canvas.getContext("2d"); 
document.body.appendChild(canvas);
mouseX = 0;
mouseB = false;
function clickedFun(event){
  mouseX = event.clientX
  mouseB = true;
}
  

canvas.addEventListener("click",clickedFun);

var w = 250;
var h = 250;
var wh = w/2;
var hh = h/2;
var speedMax = 5;
var partSize = 2;
var count = 100
var grav = 1;
var pA1 = [];  // particle arrays
var pA2 = [];
var PI2 = Math.PI * 2;

// populate particle arrays
for(var i = 0; i < count; i += 1){
    // dumb list
    pA1.push({
       x : Math.random() * w,
       y : Math.random() * h,
       dx : (Math.random() -0.5)*speedMax,
       dy : (Math.random() -0.5)*speedMax,
       
    })      
    // smart list
    pA2.push({
       x : Math.random() * w,
       y : Math.random() * h,
       dx : (Math.random() -0.5)*speedMax,
       dy : (Math.random() -0.5)*speedMax,
       links : [], // add some memory
    })  
    for(var j = 0; j < count; j += 1){
        pA2[i].links[i] = false; // set memory to no links
    }
}


// move and draw the dots. Just a simple gravity sim
function drawAll(parts){
    var x,y,d;
    var i = 0;
    var len = parts.length;
    var p;
    ctx.beginPath();
    for(;i < len; i++){
        p = parts[i];
        x = wh-p.x;
        y = hh-p.y;
        d = x*x + y*y;
        x *= grav / d;
        y *= grav / d;
        p.dx += x;
        p.dy += y;
        p.x += p.dx;
        p.y += p.dy;
        if(p.x <= 0){
            p.dx -= p.dx/2;
            p.x = 1;
        }else
        if(p.x >= w){
            p.dx -= p.dx/2;
            p.x = w-1;
        }
        if(p.y <= 0){
            p.dy -= p.dy/2;
            p.y = 1;
        }else
        if(p.y >= h){
            p.dy -= p.dy/2;
            p.y = w-1;
        }
        ctx.moveTo(p.x+partSize,p.y)
        ctx.arc(p.x,p.y,partSize,0,PI2)
    }
    ctx.fill();
}
//Old style line test. If two particles are less than dist apart
// draw a line between them
function linesBetween(parts,dist){
    var distSq = dist*dist;
    var x,y,d,j;
    var i = 0;
    var len = parts.length;
    var p,p1;
    ctx.beginPath();
    for(; i < len; i ++){
        p = parts[i];
        for(j = i + 1; j < len; j ++){
            p1 = parts[j];
            x = p1.x-p.x;
            if((x *= x) < distSq){
                y = p1.y-p.y;
                if(x + (y*y) < distSq){
                    ctx.moveTo(p.x,p.y);
                    ctx.lineTo(p1.x,p1.y)
                }
            }
        }
        
    }
    ctx.stroke();
}

var counter = 0;// counter for multyplexing
// Fast version. As the eye can not posible see the differance of 
// of 4 pixels over 1/30th of a second only caculate evey third
// particls
function linesBetweenFast(parts,dist){
    var distSq = dist*dist;
    var x,y,d,j,l;
    var i = 0;
    counter += 1;
    var cc = counter % 3;
    var wr,re;
    var len = parts.length;
    var p,p1;
    var lineSet
    ctx.beginPath();
    for(; i < len; i ++){
        p = parts[i];
        l = p.links;
        for(j = i + 1; j < len; j += 1){
            p1 = parts[j];
            if((j + cc)%3 === 0){ // only every third particle
                lineSet = false;  // test for diferance default to fail
                x = p1.x-p.x;     
                if((x *= x) < distSq){
                    y = p1.y-p.y;
                    if(x + (y*y) < distSq){
                        lineSet = true;  // yes this needs a line
                    }
                }
                l[j] = lineSet; // flag it as needing a line
            }
            if(l[j]){ // draw the line if needed
                ctx.moveTo(p.x,p.y);
                ctx.lineTo(p1.x,p1.y);
            }
        }
    }
    ctx.stroke();
}


var drawLines; // to hold the function that draws lines
// set where the screens are drawn
var left = 10;
var right = 10 * 2 + w;
// Now to not cheat swap half the time
if(Math.random() < 0.5){
    right = 10;
    left = 10 * 2 + w;
}
  

// draws a screem
var doScreen = function(parts){
    ctx.fillStyle = "red"
    drawAll(parts);
    ctx.strokeStyle = "black";
    ctx.lineWidth = 1;
    drawLines(parts,49);
}
var guess = ""
var guessPos;
var gueesCol;
ctx.font = "40px Arial Black";
ctx.textAlign = "center";
ctx.textBasline = "middle"
var timer = 0;
function update(){
    ctx.setTransform(1,0,0,1,0,0);
    ctx.clearRect(0,0,canvas.width,canvas.height);
    ctx.setTransform(1,0,0,1,left,10);
    ctx.strokeStyle = "red";
    ctx.lineWidth = 4;
    ctx.strokeRect(0,0,w,h);
    drawLines = linesBetween;
    doScreen(pA1)
    ctx.setTransform(1,0,0,1,right,10);
    ctx.strokeStyle = "red";
    ctx.lineWidth = 4;
    ctx.strokeRect(0,0,w,h);
    drawLines = linesBetweenFast
    doScreen(pA2)  
  
  
  
  
    if(mouseB){
      if((mouseX > 270 && right >250) ||
          (mouseX < 250 && right < 250)){
        guess = "CORRECT!"
        guessPos = right;
        guessCol = "Green";
      }else{
        guess = "WRONG"
        guessPos = left
        guessCol = "Red";
      }
      timer = 120;
      mouseB = false;
    }else
    if(timer > 0){
      timer -= 1;
      if(timer > 30){
        ctx.setTransform(1,0,0,1,guessPos,10);
        ctx.font = "40px Arial Black";
        ctx.fillStyle = guessCol;
        ctx.fillText(guess,w/2,h/2);
      }else{
        if(Math.random() < 0.5){
          right = 10;
          left = 10 * 2 + w;
        }else{
          left = 10;
          right = 10 * 2 + w;
        }          
      }
      
    }else{
      ctx.setTransform(1,0,0,1,0,0);
      ctx.font = "16px Arial Black";
      var tw = ctx.measureText("Click which sim skips 2/3rd of").width +30;
      
      ctx.beginPath();
      ctx.fillStyle = "#DDD";
      ctx.strokeStyle = "Red";
      ctx.rect(270-tw/2,-5,tw,40);
      ctx.stroke();
      ctx.fill();

      ctx.fillStyle = "blue";
      ctx.fillText("Click which sim skips 2/3rd of",270,15) ;
      ctx.fillText("particle tests every frame",270,30) ;
    }

    requestAnimationFrame(update);
}
update();

Answer 2

You have a coordinate system - use the Pythagorean theorem.

Answer 3

To calculate the distance between two points you use the pythagorean theorem. http://www.purplemath.com/modules/distform.htm

// Request animation frame
		var requestAnimationFrame = window.requestAnimationFrame || 
		window.mozRequestAnimationFrame || 
		window.webkitRequestAnimationFrame || 
		window.msRequestAnimationFrame;
    
		// Canvas
		var canvas = document.getElementById('canvas');
		var ctx = canvas.getContext('2d');
		
		// Set fullscreen
		canvas.width = document.documentElement.clientWidth;
		canvas.height = document.documentElement.clientHeight;

		// Options
		var num =30;            // Number of particles to draw
		var size = 3;           // Particle size
		var color = '#fff';     // Particle color
		var min_speed = 1;      // Particle min speed
		var max_speed = 3;      // Particle max speed
		var line_distance = 20; // This is the max distance between two particles
		                        // if we want to draw a line between them

		// Particles array
		var particles = [];
		for (var i = 0; i < num; i++) {
			particles.push(
				new create_particle()
			);
		}

		// Lets animate the particle
		function draw() {

			// Background
			ctx.fillStyle = "#000";
			ctx.fillRect(0, 0, canvas.width, canvas.height);
			
			// Lets draw particles from the array now
			for (var t = 0; t < particles.length; t++) {
		  
				// This particle
				var p = particles[t];
				
				for (var q = 0; q < particles.length; q++) {

					// Check position distance
					if (distance(particles[q], p) < line_distance) {
						ctx.beginPath();
						ctx.lineWidth = 1;
						ctx.strokeStyle = '#fff';
						ctx.moveTo(p.x, p.y);
						ctx.lineTo(particles[q].x, particles[q].y);
						ctx.stroke();
					}
				
				}
				
				// Color
				ctx.fillStyle = color;

				// Circle path
				ctx.beginPath();
				ctx.arc(p.x, p.y, p.radius, Math.PI * 2, false);
				ctx.fill();
				
				// Lets use the velocity now
				p.x += p.vx;
				p.y += p.vy;

				// If there is only 1 particle
				// show X, Y, and velocity
				if (num === 1) {
					ctx.fillText('Y:'+ p.y, 20, 20);
					ctx.fillText('X:'+ p.x, 20, 40);
					ctx.fillText('YV:'+ p.vy, 20, 60);
					ctx.fillText('XV:'+ p.vx, 20, 80);
				}

				// To prevent the balls from moving out of the canvas
				if (p.x < size) p.vx*= (p.vx / -p.vx);
				if (p.y < size) p.vy*= (p.vy / -p.vy);
				if (p.x > canvas.width - size) p.vx*= (-p.vx / p.vx);
				if (p.y > canvas.height - size) p.vy*= (-p.vy / p.vy);

			}
		  
		  // Loop
		  requestAnimationFrame(draw);
		  
		}
		
		// Function for particle creation
		function create_particle() {

			// Random position
			this.x = Math.random() * canvas.width;
			this.y = Math.random() * canvas.height;
			
			// Velocity
			this.vx = random_int_between(min_speed, max_speed);
			this.vy = random_int_between(min_speed, max_speed);
			
			// Color & Size
			this.color = color;
			this.radius = size;
		  
		}

		// Random number between (used for speed)
		function random_int_between(min, max) {
			return Math.floor(Math.random() * max) + min;
		}

		draw();

function distance(pointA, pointB){
  var dx = pointB.x - pointA.x;
  var dy = pointB.y - pointA.y;
  return Math.sqrt(dx*dx + dy*dy);
}

<canvas id="canvas"></canvas>

Please note I increased the lineWidth to 1, so you could see better the result

Answer 4

To calculate the distance between two points, you should use pythagoras theorem:

length = sqrt(a² + b²)

Where a is the length of one side, and b is the length of the other side.

var a = (x2 - x1);
var b = (y2 - y1);
var sum = (a * a) + (b * b);
var length = Math.sqrt(sum);

This can be turned into a function, since you know you'll have particles that have an x and y.

function calcLength(particle1, particle2) {
  var xDiff = particle2.x - particle1.x;
  var yDiff = particle2.y - particle1.y;
  var sum = (xDiff * xDiff) + (yDiff * yDiff);
  return Math.sqrt(sum);
}

Then you can use that function in your code:

for (var t = 0; t < particles.length; t++) {
  var p = particles[t];
    for (var q = 0; q < particles.length; q++) {
      var p2 = particles[q];
      if (calcLength(p, p2) < 20) {
        // draw a line between the particles
      }
    }
 }

Answer 5

This is just your test which is wrong.

a-b < c || b-a < c is always true (except if a-b == c)

replace by abs(a-b) < c if you want to test "x" distance, or by using the above formula if you want an euclidian distance

// Request animation frame
		var requestAnimationFrame = window.requestAnimationFrame || 
		window.mozRequestAnimationFrame || 
		window.webkitRequestAnimationFrame || 
		window.msRequestAnimationFrame;
    
		// Canvas
		var canvas = document.getElementById('canvas');
		var ctx = canvas.getContext('2d');
		
		// Set fullscreen
		canvas.width = document.documentElement.clientWidth;
		canvas.height = document.documentElement.clientHeight;

		// Options
		var num =30;            // Number of particles to draw
		var size = 3;           // Particle size
		var color = '#fff';     // Particle color
		var min_speed = 1;      // Particle min speed
		var max_speed = 3;      // Particle max speed
		var line_distance = 20; // This is the max distance between two particles
		                        // if we want to draw a line between them

		// Particles array
		var particles = [];
		for (var i = 0; i < num; i++) {
			particles.push(
				new create_particle()
			);
		}

		// Lets animate the particle
		function draw() {

			// Background
			ctx.fillStyle = "#000";
			ctx.fillRect(0, 0, canvas.width, canvas.height);
			
			// Lets draw particles from the array now
			for (var t = 0; t < particles.length; t++) {
		  
				// This particle
				var p = particles[t];
				
				for (var q = 0; q < particles.length; q++) {

					// Check position distance
					if (Math.abs(particles[q].x - p.x) < line_distance) {
						ctx.beginPath();
						ctx.lineWidth = .1;
						ctx.strokeStyle = '#fff';
						ctx.moveTo(p.x, p.y);
						ctx.lineTo(particles[q].x, particles[q].y);
						ctx.stroke();
					}
				
				}
				
				// Color
				ctx.fillStyle = color;

				// Circle path
				ctx.beginPath();
				ctx.arc(p.x, p.y, p.radius, Math.PI * 2, false);
				ctx.fill();
				
				// Lets use the velocity now
				p.x += p.vx;
				p.y += p.vy;

				// If there is only 1 particle
				// show X, Y, and velocity
				if (num === 1) {
					ctx.fillText('Y:'+ p.y, 20, 20);
					ctx.fillText('X:'+ p.x, 20, 40);
					ctx.fillText('YV:'+ p.vy, 20, 60);
					ctx.fillText('XV:'+ p.vx, 20, 80);
				}

				// To prevent the balls from moving out of the canvas
				if (p.x < size) p.vx*= (p.vx / -p.vx);
				if (p.y < size) p.vy*= (p.vy / -p.vy);
				if (p.x > canvas.width - size) p.vx*= (-p.vx / p.vx);
				if (p.y > canvas.height - size) p.vy*= (-p.vy / p.vy);

			}
		  
		  // Loop
		  requestAnimationFrame(draw);
		  
		}
		
		// Function for particle creation
		function create_particle() {

			// Random position
			this.x = Math.random() * canvas.width;
			this.y = Math.random() * canvas.height;
			
			// Velocity
			this.vx = random_int_between(min_speed, max_speed);
			this.vy = random_int_between(min_speed, max_speed);
			
			// Color & Size
			this.color = color;
			this.radius = size;
		  
		}

		// Random number between (used for speed)
		function random_int_between(min, max) {
			return Math.floor(Math.random() * (max-min)) + min;
		}

		draw();

<canvas id="canvas" width="300" height="300"></canvas>

// Request animation frame
		var requestAnimationFrame = window.requestAnimationFrame || 
		window.mozRequestAnimationFrame || 
		window.webkitRequestAnimationFrame || 
		window.msRequestAnimationFrame;
    
		// Canvas
		var canvas = document.getElementById('canvas');
		var ctx = canvas.getContext('2d');
		
		// Set fullscreen
		canvas.width = document.documentElement.clientWidth;
		canvas.height = document.documentElement.clientHeight;

		// Options
		var num =30;            // Number of particles to draw
		var size = 3;           // Particle size
		var color = '#fff';     // Particle color
		var min_speed = 1;      // Particle min speed
		var max_speed = 3;      // Particle max speed
		var line_distance = 20; // This is the max distance between two particles
		                        // if we want to draw a line between them

		// Particles array
		var particles = [];
		for (var i = 0; i < num; i++) {
			particles.push(
				new create_particle()
			);
		}

		// Lets animate the particle
		function draw() {

			// Background
			ctx.fillStyle = "#000";
			ctx.fillRect(0, 0, canvas.width, canvas.height);
			
			// Lets draw particles from the array now
			for (var t = 0; t < particles.length; t++) {
		  
				// This particle
				var p = particles[t];
				
				for (var q = 0; q < particles.length; q++) {

					// Check position distance
					if (particles[q].x - p.x < line_distance || p.x - particles[q].x < line_distance) {
						ctx.beginPath();
						ctx.lineWidth = .1;
						ctx.strokeStyle = '#fff';
						ctx.moveTo(p.x, p.y);
						ctx.lineTo(particles[q].x, particles[q].y);
						ctx.stroke();
					}
				
				}
				
				// Color
				ctx.fillStyle = color;

				// Circle path
				ctx.beginPath();
				ctx.arc(p.x, p.y, p.radius, Math.PI * 2, false);
				ctx.fill();
				
				// Lets use the velocity now
				p.x += p.vx;
				p.y += p.vy;

				// If there is only 1 particle
				// show X, Y, and velocity
				if (num === 1) {
					ctx.fillText('Y:'+ p.y, 20, 20);
					ctx.fillText('X:'+ p.x, 20, 40);
					ctx.fillText('YV:'+ p.vy, 20, 60);
					ctx.fillText('XV:'+ p.vx, 20, 80);
				}

				// To prevent the balls from moving out of the canvas
				if (p.x < size) p.vx*= (p.vx / -p.vx);
				if (p.y < size) p.vy*= (p.vy / -p.vy);
				if (p.x > canvas.width - size) p.vx*= (-p.vx / p.vx);
				if (p.y > canvas.height - size) p.vy*= (-p.vy / p.vy);

			}
		  
		  // Loop
		  requestAnimationFrame(draw);
		  
		}
		
		// Function for particle creation
		function create_particle() {

			// Random position
			this.x = Math.random() * canvas.width;
			this.y = Math.random() * canvas.height;
			
			// Velocity
			this.vx = random_int_between(min_speed, max_speed);
			this.vy = random_int_between(min_speed, max_speed);
			
			// Color & Size
			this.color = color;
			this.radius = size;
		  
		}

		// Random number between (used for speed)
		function random_int_between(min, max) {
			return Math.floor(Math.random() * max) + min;
		}

		draw();

<canvas id="canvas"></canvas>