Если каждой точке разрешено перемещаться, обновления могут стать дорогими для kd-деревьев или аналогичных адаптивных структур. Думаю, я бы пошел на статический подход к разделению, например. разделите пространство на множество ячеек (квадратичных или прямоугольных) и для каждого хранилища ячеек ссылаются на содержащиеся точки вместе с максимальными и минимальными координатами набора содержащихся точек. Когда точки движутся, вы можете тривиально вычислить текущую ячейку, в которой они находятся. Когда дело доходит до расчета расстояния, вы просто определяете соответствующие ячейки, а затем вычисляете расстояния до их содержащихся точек с линейным временем.
Я вижу три основные преимущества этого подхода:
Глядя на текущий замкнутых системах мин и макс координаты для каждой ячейки вы можете легко определить, является ли его пустой и, если нет, то весь набор из содержащихся пунктов актуальна для текущей позиции вашего игрока.
Вы можете организовать статические ячейки в древовидной структуре (например, Quadtree) с идеальной балансировкой. Для каждого внутреннего узла дерева вы храните и обновляете объединенные минимальные и максимальные координаты своих дочерних узлов. Обратите внимание, что обновления довольно недороги, потому что структура дерева вообще не затрагивается.
Вам не нужно сортировать свои очки (как это было бы необходимо для других структур или конкретных реализаций). Это может сэкономить вам много времени, если объекты движутся быстро.
Создание и поддержание структуры данных прост. Вам не нужно разрушать свой мозг экзотическими тестовыми случаями и сложными обновлениями структуры.
Есть, конечно, некоторые недостатки в выборе неадаптивной структуры данных, так как она неадаптивна. Например, вы сильно зависите от размера ячеек сетки. Если вы выберете его слишком маленьким (наихудший случай: одна точка на ячейку), глубина дерева вздувается и проходит дорого. С другой стороны, если вы выберете слишком большой (худший случай: в какой-то момент все точки находятся в одной ячейке), вы будете выполнять множество ненужных и потенциально дорогостоящих вычислений расстояний.
В целом, это действительно зависит от типа данных, которые у вас есть. Предложение, которое я вам дал, должно дать достаточно хорошие результаты, но, вероятно, есть более эффективные способы сделать это. Если у вас достаточно времени, выполните оба подхода: адаптивный и статический подход к разбиению, придумайте некоторые репрезентативные тесты и сравните их друг с другом.
Надеется, что это помогает;)
Пространственного разделения является правильным ключевым слово здесь, но вы должны предоставить некоторую более подробную информацию. Например, я предполагаю, что «игрок» движется, но другие точки тоже? Вам действительно нужна 3D-информация для выбора? Кроме того, WGS84 - это система координат, основанная на прогнозах, не зависящая от длины, и ваш выбор разделения может зависеть от того, нужно ли вычислять метрические расстояния для игрока. –
Объекты тоже движутся. Нет. Мне не нужна 3d-информация для выбора. Я преобразую сферические координаты в декартову для метрических расстояний. –
@FelixLauer У вас есть идея? о том, как действовать?kd-дерево knn? –