Как избежать O(n^2) C#

Question

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

            foreach (var joint in joints)
            {
                foreach (var jointNext in joints)
                {
                    if (joint == jointNext) continue;
                    if((jointNext.Position - joint.Position).magnitude <= _jointsConnectDistance)
                    {
                        TwoWayConnetion(joint, jointNext);
                    }
                }
            }

Answer 1

Предлагаю оптимизацию, которая хорошо работает для хороших наборов точек.

Разбейте всю плоскость или пространство где живут ваши точки квадратной или кубической решёткой. Шаг решётки _jointsConnectDistance. Каждая точка помещается в корзину соответствующую квадрату или кубу куда она попадает. Координаты квадрата или куба - это кортеж целых чисел. По ним удобно размещать точки в HashMap.

Когда HashMap готов, пробегаете по его корзинам. Точки из корзины надо сравнивать только с точками из той же корзины и её восемью или двадцатью шестью соседками.

Если расстояние заранее не известно или вы хотите использовать разные расстояние для разных точек, используйте K-d дерево.

Answer 2

Если под найти соседние вы имеете ввиду это:

То это называется триангуляция.

Есть разные фигуры: convex, concave с дырками. Алгоритмы триангуляции не просты.

Triangulation Delaunay

Поищите готовые фреймворки триангуляции для C#.

БЛОГ НА HUSL

Как избежать O(n^2) C#

Ответы (2 шт):