Как написать алгоритм поиска соседних элементов?

Question

[Александр]

Есть анимация, в которой присутствует около 200 объектов, у которых в каждом кадре постепенно (довольно медленно) изменяются координаты. Нужен алгоритм, который будет очень оптимально выполнять поиск новых связей. Связь должна устанавливаться, когда расстояние между объектами меньше определённого числа ( при этом не обязательно устанавливать связь прямо в том же кадре, в котором расстояние становится достаточно близким, меня устроит и вариант, когда связь будет установлена через несколько кадров после того, как расстояние стало достаточно маленьким).

Если банально перебирать расстояния для каждой пары точек, то на каждом кадре будет цикл на 40000 пар. Довольно большая нагрузка вообще говоря. Необходимо сохранив равномерность нагрузки на кадр сократить кол-во вычислений в одном кадре минимум в 10-20 раз (а лучше больше). У меня есть определённые идеи, но всё же хотел послушать мнения других.

Comments

[Сергей Соколов]

это называется задача поиска ближайшего соседа. В англоязычной wiki статья гораздо подробнее и полезнее: Nearest Neighbor Search (NNS)

[devalone]

Первое, что приходит в голову - разбить область на подобласти(квадраты, кубы или какое у вас пространство) и искать уже в них, тогда проверок будет намного меньше

[Сергей Соколов]

LordGuard координаты целочисленные?

[Сергей Соколов]

кстати, вам может быть интересна реализация построения диаграммы Вороного на JS – там тоже выполняется задача поиска ближаших точек при добавлении новой - посмотрите, как они сделали: gorhill/Javascript-Voronoi

[Сергей Соколов]

Спасибо за интересный вопрос! Попробую написать реализацию. Для 200 точек у меня получилось почему-то всего 19900 рёбер:

[Александр]

Сергей Соколов: ну логично. 40к - это я имел ввиду, если брать перебор по 200 для каждой из 200 точек. Конечно действительное кол-во рёбер равно 1 + 2 + 3 + ... + (n-1). В вопросе я сильно утрировал. Спасибо за ваш вариант реализации))

Answer 1

[maxfox]

Если хранить координаты в отсортированном массиве (X и Y отдельно), то проверять нужно будет только ближайших соседей, до тех пор, пока разница координат не превысит вашего минимального расстояния. Такая оптимизация тем эффективнее, чем меньше данное расстояние относительно размеров поля. Плюс кэшировать результаты сравнений, чтобы не проверять уже проверенные пары. Далее можно убивать кэш не каждый кадр, можно в четных кадрах искать вверх по массиву, а в нечетных - вниз и т.п. Но это уже по факту, если потребуется.

Comments

[Сергей Соколов]

придётся все-таки проверять все точки и обе координаты каждой:

Для точки А по оси Y ближайшие – куча точек E, F, G. Истинная ближайшая точка H по каждой из осей «проигрывает» массе других кандидатов.

[maxfox]

Сергей Соколов: Речь о проверке точек в двух отдельных массивах (по X и по Y). На вашей иллюстрации точка H будет ближайшей в обоих.

[Сергей Соколов]

maxfox: я, видимо, не понял вашу идею. На иллюстрации, если взять только X-координаты точек, ближайшими к А будут B, C, D. И только потом H, и в хвосте E, F, G.

[maxfox]

Сергей Соколов: Прошу прощения за поспешность, вы правы. Проверять нужно только кандидатов, которые есть в обоих списках. Что, в общем, не увеличивает объём проверок. Вообще, достаточно одного прохода по каждому массиву, чтобы составить два множества пар точек, которые могут быть соседями. Их пересечение будет множеством кандидатов. При более-менее равномерном распределении по полю и достоточно большом поле, это будет сильно быстрее полного перебора.

[Сергей Соколов]

maxfox: и тут речь ведь идёт всего про одну из точек: поиск соседей для неё. А такую проверку вы предлагаете делать каждый раз для каждой из 200?

[maxfox]

Сергей Соколов: Я примерно накидал то, что я имею в виду:

function generatePoints(minX, maxX) {
    let letters = 'abcdefghijklmnopqrstuvwxyz';
    let points = letters.split('').map((c) => {
        return {id:c,
            x: minX + Math.random()*(maxX-minX)}
    });
    points.sort((a,b) => a.x - b.x);
    return points;
}

function findNeighbours(points, minDistance) {
    let frame = [];
    let neighbours = new Set();
    for (point of points) {
        while ((frame.length > 0) && ((point.x - frame[0].x) > minDistance)) {
            frame.shift();
        }
        for (framePoint of frame) {
            neighbours.add(framePoint.id + point.id);
       }
       frame.push(point);
    }
    return neighbours;
}

let points = generatePoints(0, 1000);
for (point of points) {
    console.log(point);
}
for (pair of findNeighbours(points, 10)) {
    console.log(pair);
}

Тут все точки на одной оси (одномерное пространство), проходим "кадром" по массиву отсортированных по координате точек. В каждом проходе кадр очищается от лишних элементов (тех, которые слишком далеко от текущей точки). Код написан "на коленке", но, надеюсь идея понятна.
Суть в том, что если "кадр" (т.е. минимальная дистанция) невелик по отношению к размеру поля, то в нем редко будет больше двух элементов. Так что почти линейная сложность. Если плотность элементов большая, и минимальная дистанция достаточно велика, то будет уже квадратичная сложность. Но у автора вроде 200 связей из 40000 возможных - значит, плотность небольшая.

[Сергей Соколов]

сделал вариант с сортировкой по X-координатам, отбором только в радиусе влево. И даёт, вроде бы, неплохую скорость - около 59–60 fps с 200 точек.
github

[maxfox]

Сергей Соколов: Отличный вариант! Держит 50 FPS с 1000 точек.
Я подумал сначала, что можно оптимизировать, прерывая внутренний цикл (82 строка), если dx>r2, т.к. дальше искать бессмысленно. Но на практике это не дало почти никакого прироста FPS.
Что еще раз доказывает, что не нужно заниматься преждевременной оптимизацией. :)
Спасибо за работу, у меня руки не дошли все написать..

Answer 2

[Сергей Соколов]

Идея с отдельной работой по X и по Y неплохо работает. На каждом кадре проверяем каждую из 200 точек (это совсем не много).

Сортируем массив точек по их X-координате. Двигаемся слева направо, выбирая очередную точку.

Смотрим от неё влево (чтобы не проверять одну связь дважды, выбираем полуплоскость от точки) и отбираем только те точки, чей X отличается не более, чем на radius.

Из них смотрим только на те, у которых Y не более, чем на radius отличается (уже в любую сторону: и вверх и вниз).

У них проверяем уже евклидово расстояние – корень из суммы квадратов расстояний по X и по Y – чтобы было не больше radius. У таких есть «связь» – рисуем им ребро.

Работающий fiddle (неминифицированный исходник на github)


На компе даёт около 60 fps, на мобильнике от 40 до 55, т.е. совершенно приемлемая скорость при 200 точках.

Первая версия ответа

Интересна ситуация, наихудшая для оптимизации: когда за 1 кадр может поменяться максимальное число связей. Предположу, что это сетка из равносторонних треугольников, где длина ребра равна «триггерной» дистанции:

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

Тут большинство точек, кроме крайних, взаимосвязаны. У каждой по 6 ближайших соседей. Примерно 200 * 6 / 2 = 600 связей (чуть меньше из-за краёв).

Если такую сетку пропорционально увеличить на любую малую величину, сразу все связи порвутся, их станет ноль. Пусть на месте останется, скажем, левый верхний угол сетки. Тогда наибольший путь проделает нижний правый угол. Тут вопросы к особенностям вашей задачи:

1. округляются ли координаты до целых или до какой-то точности?
   
2. какой наибольший путь может проделать за один кадр точка?
   

В идеальном мире всем достаточно проделать бесконечно малый шаг, и, вуаля!, было 600 связей, стало 0. Такой же шажок назад – не было связей, и вот их 600. Т.е. надо бы в каждый кадр проверять 600 ребер. Считать это за теоретический предел оптимизации?

Сущности
Точки и рёбра. Ребро ссылается на две точки. Точка ссылается на рёбра. Ребро имеет длину и, в зависимости от длины, может быть «видимым».

Важнее всего следить за рёбрами, длина которых близка к пороговой – и с меньшей и с большей стороны. Такие стоит проверять почти каждый кадр, т.к. статус ребра может поменяться за один кадр. Прочие рёбра и кандидаты в рёбра проверять можно изредка.

Можно давать рёбрам веса, пропорциональные желаемой частоте их обновления. Скажем, от 0 до 1. Вес равный 1 значит, что нужно проверять каждый кадр. Например, вес W = Math.max(0, D - Math.abs( length - D))/D, где D – пороговая дистанция.

Остаётся сделать механизм, отбирающий рёбра в работу на очередном кадре, исходя из их весов. Запоминать время, когда ребро было обновлено. Приоритет его попадания в обработку равен W * (time - timeUpdated)

Comments

[Александр]

Порядок точек к сожалению практически непредсказуемый, то есть любая может в определённый момент стать связанной с любой другой. То есть всё же рёбер будет 40к... хотя связей будет не больше 200 с вероятностью стремящейся к бесконечности... Идея хорошая, но не очень понятно как избежать цикла по всем 40к рёбрам на каждом кадре (даже для выборки по приоритетам).

[Сергей Соколов]

LordGuard: я правильно понял, что точки «инертны» – за один кадр ни одна из них не перепрыгнет внезапно из одного угла в другой?

[Александр]

Сергей Соколов: верно

Answer 3

[ThunderCat]

Кластерный анализ?
Если учились в вузе должны были проходить, это как раз тот случай когда академические знания могут пригодиться.

Comments

[Александр]

Учусь, на 2 курс перехожу) Хоть и на ВМК, но до серьёзных алгоритмов пока не дошли.