Search for numbers with the same value in an array

Question

I work in javascript. I have an array with points in 3d space and I want the points NOT to be very close to other points in the array. I want to say that the distance between the points is greater than x . Now what I am doing is a double loop comparing distances and moving the point further in the Z dimension, for example

 while(there_are_objects_that_are_close){ for(all_the_objects){ for (all_the_objects){ if (distance_between_them < 100){ object[i].z += 150; } } } } 

The problem is that I hate this algorithm, it looks very slow, and I'm looking for the best solution. If you have a solution that is also a “named algorithm” with literature, I would appreciate it, as it is part of our school project.

Answer 1

Comparing each point with each point is indeed the easiest, so your algorithm is a good start.

The disadvantage of this is that when the number of points becomes huge, the algorithm will start to behave rather badly, since it will have to compare each point with all points, while most points are not close. In such cases, you would like to separate the points so that you only check points that can be close enough.

For static points (those that do not move), it is trivial to make the tree such that you just need to go through several parent nodes and check its children (children close to each other are closer). It is also known as R-tree; other options also exist.

This also applies to 3D.

_{Both images are from Wikipedia.}

Visually, you can see that it is becoming much easier, you just check the boxes within your radius, and you end up doing a lot less work this way.

For dynamic points (moving), it may not be possible to save such a detailed tree R. Therefore, we will need to go to the level of detail and look for something between your approach and the R tree, simply by making several large boxes, for example, this is one of the approaches.

Another approach involves using ATVs (each time you divide a cube into 4 smaller cubes only if it contains a point) and a grid (you create many cubes of the same size). You can learn more about R trees and other structures here ; it also serves as an introduction to them.

A derivative of this is, for example, a geodesic grid that divides the globe into triangles, although this may not be applicable to 3D (unless you connect triangles with a vertex in the middle of the globe).

_{Image from Wikipedia.}

Answer 2

You need to find a way to divide the points into a smaller area for comparison.

Since you can only move points by changing the Z-dimension, I first think that sort points by Z-dimension value and only compare points that are close in Z-dimension. But I still don't know how to divide the area.