Структура данных Java для хранения точек широты и долготы и их извлечения по площади

Я хочу запомнить географические точки для быстрого поиска:

  1. Я храню несколько {широта, долгота, объект Java}
  2. Я запрашиваю все объекты, содержащиеся в пределах n километров от определенной широты, долготы

Требования:

  • Бесплатный, с открытым исходным кодом
  • Чистая Java
  • Запрос внутри «прямоугольника» (определяемого lat1,long1-lat2,long2) также допустим, но круг предпочтительнее
  • Приближения в порядке, в частности, приложение не будет использоваться вблизи полюсов.
  • Настойчивость не нужна
  • Легкий. JAR не должен быть больше мегабайта, надеюсь, намного меньше.

Нерешения:

Ответы (2)

Прошло несколько месяцев с тех пор, как вы разместили свой запрос, но если у вас все еще есть потребность, рассмотрите FeSimpleGeoProx

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

  • Бесплатный, с открытым исходным кодом (лицензия Apache версии 2.0)
  • Чистая Java
  • Поддерживает запрос внутри круга (начальная точка и радиус)
  • Поддерживает запрос внутри «прямоугольника» (определяется lat1,long1-lat2,long2)
  • Несколько объектов могут храниться на одной и той же широте/долготе без обходного пути.
  • Легкий. Банки (как FeProxiMap, так и LatLng, от которых он зависит) вместе составляют менее 100 КБ.

В спектре производительности/веса он находится между линейным поиском (легким, но медленным: для разумного поиска это от 100 до 1000 раз быстрее) и GeoRedis (молниеносно быстрым, но более тяжелым). Кроме того, в документации GeoRedis говорится, что его ответы приблизительны, в то время как они точно такие же, как даст LatLng.

Отказ от ответственности: я являюсь автором FeSimpleGeoProx . Кроме того, он опирается на отличный (и также FOSS) SimpleLatLng , который необходимо загрузить отдельно.

Выглядит отлично! А вблизи полюсов случайно не ведет себя корректно?
Спасибо, и я думаю, что ответ "да". Я полагаюсь на SimpleLatLng, который, как я полагаю, хорошо обрабатывает точки вблизи полюсов — мой поиск практически такой же правильный, как и SimpleLatLng. Мои модульные тесты (которые включают набор данных рядом с полюсами) показывают результаты, идентичные грубой проверке каждой точки в наборе данных, только намного быстрее для «разумных» поисков.
Прохладный! Пробовали ли вы проверить, сколько точек FeSimpleGeoProx становится более производительным, чем грубая сила?
Действительно есть. Если вы запустите прилагаемые тесты производительности, вы увидите, что это намного быстрее (в 100–1000 раз) быстрее на нетривиальном наборе точек, если ваш поиск относительно мал: то есть, если возвращаемый набор точек является небольшим часть общего количества баллов в полном наборе данных. По мере роста размера возвращаемого набора данных производительность снижается, и, в конечном счете, если поиск возвращает все или почти все (~ 80%) точек в мире, производительность на самом деле хуже, чем при линейном поиске.
@NicolasRaoul Если вы в конечном итоге используете его, сообщите мне о своем опыте. Я построил его, чтобы быть полезным.
Не могли бы вы оставить комментарий на github.com/nicolas-raoul/apps-android-commons/issues/141 ? Спасибо!
@NicolasRaoul Да, но я не знаю, что ты хочешь сказать. ;]

Quadtree можно использовать:

... но у него есть некоторые недостатки:

  • Поиск не по радиусу, а по прямоугольнику.
  • Плоская карта, не работает вблизи полюсов.
  • Два разных объекта не могут храниться на одной и той же широте/долготе. Это можно обойти, сделав каждый объект списком объектов.
Структура данных Java для хранения точек широты и долготы и их извлечения по площади
СпросиСетьПолитика конфиденциальности1y, 2v