Блог

Учитывая небольшое количество точек и кругов (скажем, менее 100), как мне определить, какая точка лежит в каких кругах? Окружности могут пересекаться, поэтому одна точка может находиться в нескольких окружностях.

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

Немного подумав, кажется, что худший сценарий всегда будет квадратичным (когда каждая точка лежит во всех кругах)… но может быть какой-то способ ускорить это для среднего случая, когда пересечений не так много?

Я делаю это для моделирования искусственного интеллекта, и местоположения окружностей / точек постоянно меняются, поэтому я не могу ничего предварительно вычислить заранее. время.

Если количество точек и кругов настолько мало, вам, вероятно, сойдет с рук грубое принуждение. Пересечения с круговыми точками довольно дешевы, и 100 * 100 проверок кадра вообще не должны снижать производительность.

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

Вы можете попробовать использовать вариацию иерархий ограничивающих объемов.

Иерархия ограничивающих объемов — это дерево, в котором каждый узел охватывает весь объем обоих (или больше, если вы решите использовать дерево с более высокой степенью) его дочерних элементов. Тома / объекты, которые должны быть проверены на пересечение, всегда являются конечными узлами дерева.

Запросы вставки, удаления и пересечения имеют амортизированное среднее время выполнения O(log n) . Однако вам придется обновить дерево, поскольку ваши объекты являются динамическими, что делается путем удаления и повторной установки недопустимых узлов (узлов, которые больше не содержат свои конечные узлы полностью). Обновление полного дерева занимает в худшем случае время O(n log n) .

Следует позаботиться о том, чтобы при вставке в это поддерево был вставлен узел, который увеличивает объем поддерева на наименьшую величину.

Вот хороший пост в блоге Рэнди Галла, который хорошо объясняет динамические ограничивающие иерархии.

Вам придется использовать круги в качестве ограничивающих объемов, если вы не сможете найти способ использовать AABBs во всех узлах, кроме конечных узлов, и кругов в качестве конечных узлов. AABB более точны и должны дать вам немного лучше построенное дерево.

Вы можете построить kd-дерево точек. И затем для каждого центра окружности вы извлекаете все точки kd-дерева с расстоянием, ограниченным радиусом окружности. Учитывая M точки и N окружности, сложность должна быть M log M N log M = max(M,N) log M (если точки и окружности «хорошо распределены»).

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

Вместо перехода к полному 2D-дереву существует промежуточная возможность, основанная на сортировке.

Отсортируйте точки P по абсциссам. При хорошем алгоритме сортировки (скажем, Heapsort) стоимость может быть смоделирована как S.P.Lg (P) (S — стоимость сравнений / перемещений).

Затем для каждого круга (C из них) найдите его крайнюю левую точку (Xc-R) в отсортированном списке по дихотомии со стоимостью D.Lg (P) (D — стоимость шага дихотомии). Затем перейдите к самой правой точке (Xc R) и каждый раз выполняйте проверку точки / окружности.

Делая это, вы сэкономите сравнения с точками слева и справа от окружности. Пусть F обозначает среднюю долю точек, попадающих в диапазон [Xc-R, Xc R] для всех окружностей.

Обозначая K стоимость сравнения точки / окружности, общую сумму можно оценить как

S.P.Lg (P) D.Lg (P).C F.K.P.C

для сравнения с K.P.C.

Соотношение равно

S / K.Lg (P) / C D / K.Lg (P) / P F.

При неблагоприятной гипотезе о том, что S = D = K, для P = C = 100 мы получаем 6,6% 6,6% F. Эти три члена соответственно соответствуют времени предварительной обработки, накладным расходам на ускорение и уменьшенной рабочей нагрузке.

Предполагая, что круги достаточно малы, пусть F = 10%, и вы можете надеяться на ускорение x4.

Если вы используете тест ограничительной рамки перед точным сравнением точки / окружности (что не обязательно является улучшением), вы можете упростить тест ограничительной рамки до двух сравнений Y, поскольку перекрытие X неявно.