Stop re-iterating over duplicates in nested for loop

Question

I'm working with a JavaScript canvas, and I'd like to recreate quite a common effect I've seen where moving particles create lines between them when then get close to each other.

My issue is that I'm essentially performing two loops inside each other. Please see pseudo code:

var particles = [ /* array of particles with x and y values */ ]
for(var i = 0; i < particles.length; i ++){
 for(var j = 0; j < particles.length; j ++){
 // check if j is close to i
 // if so, draw a line between them
 } 
}

First of all I found that this would double check one particle against itself. So I can add:

 if(i == j) continue

But then actually, I need a further case. For instance, if I have already checked when i = 1 and j = 8, I don't need to check when j = 1 and i = 8

Is there a common method of simplifying this checking procedure? I'm losing a fair bit of performance with the multiple checks.

• Kilian Foth: Yes, for(var j = i+1 ...).

Answer 1

The usual way of saving effort here is

for(var j = i+1; j < particles.length; j++) {

This saves half of the comparisons in the naive double loop; and if you really do have to check every possible pair, you can't save any more than that.

• Pieter B: I would also do "i < particles.length - 1" that way you won't go over your length.
• underscore_d: @PieterB But if we loop with i < particles.length and start the iteration with i == particles.length - 1, then j = i + 1, so the test that j < particles.length will fail, so we'll stop both loops.