How to write an algorithm for finding neighboring elements?

Question

JavaScript

There is an animation in which there are about 200 objects whose coordinates gradually (rather slowly) change in each frame. We need an algorithm that will perform the search for new connections very optimally. The connection should be established when the distance between objects is less than a certain number (it is not necessary to establish a connection directly in the same frame in which the distance becomes close enough, I will also be satisfied with the option when the connection is established a few frames after the distance has become enough small).
If it is trite to sort through the distances for each pair of points, then on each frame there will be a cycle of 40,000 pairs. Pretty big workload. It is necessary, while maintaining the uniformity of the load per frame, to reduce the number of calculations in one frame by at least 10-20 times (and preferably more). I have some ideas, but still wanted to hear the opinions of others.

Answer 1

If you store the coordinates in a sorted array (X and Y separately), then you only need to check the nearest neighbors, as long as the difference in coordinates does not exceed your minimum distance. This optimization is the more effective, the smaller the given distance relative to the size of the field. Plus, cache the results of comparisons so as not to check already checked pairs. Further, you can kill the cache not every frame, you can search up the array in even frames, and down in odd frames, etc. But this is already in fact, if necessary.

Answer 2

The idea of ​​having separate work on X and Y works well. On each frame, we check each of the 200 points (this is not much at all).
Sort the array of points by their X-coordinate. We move from left to right, choosing the next point.
We look to the left from it (in order not to check one connection twice, we select a half-plane from the point) and select only those points whose X differs by no more than radius.
Of these, we look only at those for which Y differs by no more than a radius (already in any direction: both up and down).
They already check the Euclidean distance - the root of the sum of the squared distances in X and Y - so that it is no more than radius. These have a “connection” - we draw an edge for them.
On a computer it gives about 60 fps, on a mobile phone from 40 to 55, i.e. perfectly acceptable speed at 200 points.
Интересна ситуация, наихудшая для оптимизации: когда за 1 кадр может поменяться максимальное число связей. Предположу, что это сетка из равносторонних треугольников, где длина ребра равна «триггерной» дистанции:

картинка треугольной сетки

Тут большинство точек, кроме крайних, взаимосвязаны. У каждой по 6 ближайших соседей. Примерно 200 * 6 / 2 = 600 связей (чуть меньше из-за краёв).
Если такую сетку пропорционально увеличить на любую малую величину, сразу все связи порвутся, их станет ноль. Пусть на месте останется, скажем, левый верхний угол сетки. Тогда наибольший путь проделает нижний правый угол. Тут вопросы к особенностям вашей задачи:
В идеальном мире всем достаточно проделать бесконечно малый шаг, и, вуаля!, было 600 связей, стало 0. Такой же шажок назад – не было связей, и вот их 600. Т.е. надо бы в каждый кадр проверять 600 ребер. Считать это за теоретический предел оптимизации?
Точки и рёбра. Ребро ссылается на две точки. Точка ссылается на рёбра. Ребро имеет длину и, в зависимости от длины, может быть «видимым».
Важнее всего следить за рёбрами, длина которых близка к пороговой – и с меньшей и с большей стороны. Такие стоит проверять почти каждый кадр, т.к. статус ребра может поменяться за один кадр. Прочие рёбра и кандидаты в рёбра проверять можно изредка.
Можно давать рёбрам веса, пропорциональные желаемой частоте их обновления. Скажем, от 0 до 1. Вес равный 1 значит, что нужно проверять каждый кадр. Например, вес W = Math.max(0, D - Math.abs( length - D))/D, где D – пороговая дистанция.
Остаётся сделать механизм, отбирающий рёбра в работу на очередном кадре, исходя из их весов. Запоминать время, когда ребро было обновлено. Приоритет его попадания в обработку равен W * (time - timeUpdated)

Answer 3

Cluster analysis?
If you studied at a university were supposed to pass, this is just the case when academic knowledge can come in handy.