Существуют ли какие-либо алгоритмы, которые позволяют быстрый/эффективный поиск шестиугольников на основе местоположения ⇐ JAVA

[Anonymous]

Итак, у меня есть разделенная сфера икосаэдра (икосфера), и я просматриваю ее вершины и создаю логическую тайловую карту шестиугольников в месте каждой вершины массива. По сути, теперь мне нужно начать обнаруживать входные данные на тайловой карте, а перебирать 10 тысяч тайлов и выполнять проверку границ каждый раз, когда пользователь наводит указатель мыши на сферу или щелкает ее, слишком затратно в вычислительном отношении.
Мне нужен способ быстро и эффективно получить плитку, на которую пользователь нажимает или наводит курсор.
Моя текущая идея — создать 2D-массив плиток (широта/долгота). , конвертируйте положение плитки для значений широты и долготы и сохраните плитку по адресу tiles[lat][lon].
Проблема этого решения заключается в том, что широта и долгота сохраняются как значения с плавающей запятой - в этом В этом случае они (с точки зрения расстояния) находятся на «радиусе сферы» от центральной точки сферы. Если я это сделаю, мне придется резко увеличить сферу, и вполне вероятно, что в массиве будет много «неиспользуемых» слотов, содержащих нулевые значения. Это довольно грязно. Если бы мы сделали это, нам также пришлось бы найти какой-то способ гарантировать, что значение широты/долготы приблизительно сопоставляется непосредственно с координатой x/y тайла в массиве тайлов (т. е. мы могли бы просто сделать tiles[(int)lat] [(int)lon], чтобы получить плитку, но опять же, это создаст массив со многими пустыми слотами (что, насколько я понимаю, приводит к большому количеству потраченной впустую памяти, как дополнительный минус).
Я также мог бы хранить фрагменты в словаре словарей, при этом внешний словарь будет ArrayMap. Проблема в том, что я не совсем уверен, насколько производительно это действительно может быть - мы говорим о поиске массивов с сотнями или тысячами плиток на довольно регулярной основе.
Если я удостоверюсь, что плитки упорядочены, модифицированная реализация алгоритма двоичного поиска также может оказаться целесообразным.
Что вы думаете о разработке быстрой и эффективной системы координат?

Подробнее здесь: https://stackoverflow.com/questions/792 ... sed-on-loc