Что такое хорошая структура данных для хранения и поиска 2d пространственных координат в Java

В настоящее время я пишу плагин для игры, в котором одна функция включает в себя возможность устанавливать области, определенные двумя двумерными координатами (верхние левые и нижние правые области прямоугольника). Затем эти регионы должны быть сохранены и будут иметь различные другие данные, связанные с каждым регионом. Поскольку игрок движется по миру, мне нужно определить, когда он входит в один из этих регионов только из координат игрока, и метод его выполнения должен быть эффективным, так как это будет вызвано сотнями раз в секунду,

Существуют ли какие-либо структуры данных, которые могут эффективно поддерживать этот вид поиска, и если да, где я могу найти документацию на нем, чтобы либо найти реализацию java для использования, либо, если необходимо, реализовать ее самостоятельно?

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

Ответ 1

Хорошая структура данных для определения столкновения в части пространства представляет собой da -структуру quad-tree. Квадратное дерево рекурсивно делит пространство в соответствии с количеством элементов в данной области. Таким образом, он может выполнять поиск, если координаты находятся внутри области в логарифмическом времени.

EDIT: я нашел реализацию здесь, но информация о лицензии не указана.

Ответ 2

Для реализации координат вы можете использовать Point2D в классе, который реализует функциональность, которую вы ищете:

http://download.oracle.com/javase/6/docs/api/java/awt/geom/Point2D.html

Ответ 3

В одномерном случае подходящей структурой данных является дерево .

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

Предполагая, что игрок медленно перемещается (т.е. количество регистров вводится или покидает события невелики по сравнению с количеством регионов), следующий подход может быть более эффективным: сохранить дерево поиска координат x, где начинаются или заканчиваются прямоугольники, и аналогичное дерево для y-координат. Если игрок входит или покидает регион, он должен пересечь координату x или y граничной точки. То есть вы будете делать запрос диапазона в дереве поиска x для диапазона [old_x, new_x] и проверять каждый из этих прямоугольников. Сделайте то же самое для y-направления (не сообщая о дубликатах).