Точки кластеризации или фильтрации в координатах WGS84
Поэтому я пытаюсь решить проблему. У меня есть точка, которая может быть игроком, и у меня есть несколько объектов, некоторые находятся дальше, некоторые ближе. Я хочу исключить все точки, которые находятся дальше, и включить ближе, используя расстояния, например. Как бы один кластер или фильтровать объекты. Я думаю о пространственном разделении. Объекты находятся в географических координатах. Количество объектов может быть 10.000
Решение
Если каждая точка может перемещаться, обновления могут дорого обойтись для kd-деревьев или аналогичных адаптивных структур. Я думаю, что я бы пошел на подход статического разделения, например разделите пространство на набор ячеек (квадратичных или прямоугольных) и для каждой ячейки сохраните ссылки на содержащиеся точки вместе с максимальными и минимальными координатами набора содержащихся точек. Когда точки движутся, вы можете легко вычислить текущую ячейку, в которой они находятся. Когда дело доходит до вычисления расстояния, вы просто определяете соответствующие ячейки, а затем вычисляете расстояния до их содержащихся точек с линейным временем.
Я вижу три основных преимущества этого подхода:
-
Просматривая текущие содержащиеся минимальные и максимальные координаты для каждой ячейки, вы можете легко определить, является ли ее пустая или нет, а весь набор содержащихся точек соответствует текущей позиции вашего игрока.
-
Вы можете организовать статические ячейки в древовидную структуру (например, Quadtree) с идеальной балансировкой. Для каждого внутреннего узла дерева вы сохраняете и обновляете объединенные минимальную и максимальную координаты их дочерних узлов. Обратите внимание, что обновления довольно недороги, потому что на структуру дерева это никак не влияет.
-
Вам не нужно сортировать ваши точки (как это было бы необходимо для других структур или конкретных реализаций). Это может сэкономить вам большую производительность, если объекты движутся быстро.
-
Построить и поддерживать структуру данных просто. Вам не нужно ломать свой мозг экзотическими тестами и сложными обновлениями структуры.
Есть, конечно, некоторые недостатки в выборе неадаптивной структуры данных, потому что она, ну, в общем, неадаптивная. Например, вы сильно зависите от размера ячеек сетки. Если вы выберете его слишком маленьким (наихудший случай: одна точка на ячейку), глубина дерева увеличивается, и обход становится дорогим. С другой стороны, если вы выберете его слишком большим (наихудший случай: в какой-то момент все точки находятся в одной и той же ячейке), вы будете выполнять много ненужных и потенциально дорогих вычислений расстояния.
В общем, это действительно зависит от того, какие данные у вас есть. Предложение, которое я вам дал, должно дать достаточно хорошие результаты, но, вероятно, есть более эффективные способы сделать это. Если у вас есть достаточно времени, примените оба подхода — адаптивный и статический, создайте несколько репрезентативных тестов и сравните их друг с другом.
Надеюсь это поможет 😉
Другие решения
Других решений пока нет …