Геопространственная индексация
Геопространственные индексы — это индексы по точкам. Кристина Ходоров написала отличное описание того, как это работает, в своем блоге «Монго во Флатландии». Geohashing метод , описанный здесь , позволяет искать точки вблизи данную точку. Поддерживая каталог достопримечательностей (например, кафе, ресторанов и т. Д.), Вы можете найти ближайший к вам, выполнив запрос о точках рядом с вами.
Тем не менее, возможность поиска других точек рядом с вами не позволяет напрямую задать вопрос «Где я?»
Предположим, у вас есть полигональная сетка, которая описывает границы штатов или стран, и вы хотите выяснить, какой полигон содержит ваше текущее местоположение. Другими словами, учитывая ваше местоположение, получите имя, где вы находитесь. Геопространственные индексы не могут сделать это напрямую, потому что этот запрос не о поиске других точек. Тем не менее, есть решение. Я собираюсь показать вам, как это сделать, используя геопространственный индекс. Я построил этот пример с использованием MongoDB , но этот метод должен работать так же хорошо с другими базами данных с геопространственными индексами, такими как Postgres с установленным расширением PostGIS .
Идеи реализации
У меня была пара идей о том, как это сделать:
- Используя граничные многоугольники, создайте инвертированный индекс, создав словарь, который сопоставляет каждую вершину многоугольника с ее исходным многоугольником. По заданной точке запроса ищите все близлежащие вершины; для каждого извлеките многоугольник и проверьте, находится ли в нем точка запроса.
- Для каждого граничного многоугольника вычислите его центроид (обратите внимание, что в этой записи Википедии есть форумы, которые нам понадобятся, чтобы найти центроид многоугольника). Создайте словарь, который отображает центроиды на их исходные полигоны. По заданной точке запроса ищите ближайшие центроиды; для каждого извлеките многоугольник и проверьте, находится ли в нем точка запроса.
Я не уверен, какое из этих решений будет работать лучше; Я могу вообразить, что первый генерирует много совпадений, потому что может быть много вершин для некоторых полигонов, если они представляют собой извилистые границы с высокой точностью. Множество попаданий означает необходимость проверки членства во многих полигонах, и это замедлит процесс. Но я действительно не буду знать, пока у меня не будет данных, чтобы опробовать их.
Нам нужны некоторые геопространственные данные
Первый ингредиент, который нам нужен в этом рецепте, — это некоторые данные для работы. Я догадывался, что у USGS будет кое-что, что можно будет загрузить; Поиск в Google по запросу «Государственные границы USGS» обнаружил меня на этой странице , на которой была ссылка для загрузки для state_bounds.zip , сжатого шейп- файла ESRI.
Какого черта «шейп-файл ESRI?» В Википедии есть запись , которая описывает шейпфайл формат файла. Большой! Я мог бы написать парсер для файла, который я скачал выше. Это начало казаться, что это может быть популярный формат данных; Интересно, смогу ли я избежать написания парсера для себя?
Конечно же, поиск в Google «esri shapefile parser java» поставил вопрос о stackoverflow, который отвечает на этот вопрос, и указывает на библиотеку GeoTools в качестве парсера для этих файлов.
Взглянув на данные
Я начал с того, что написал простое приложение для загрузки данных из шейп-файла и представления статистики по нему. Это дало бы мне некоторый опыт работы с ГИС-библиотеками GeoTools, и я мог бы использовать результаты, чтобы помочь выбрать одну из стратегий реализации, описанных выше.
Загрузка шейп-файла оказалась не такой простой. Библиотека GeoTools немного непрозрачна. В то время как есть много javadoc, не ясно, как использовать много библиотеки. Чтобы извлечь из этого что-либо, я обнаружил, что анализирую структуры данных в отладчике, чтобы увидеть, что они содержат.
Моя первоначальная попытка использовать описанный выше шейп-файл не привела к появлению каких-либо интересных функций в коде. Поэтому я попробовал еще несколько поисков, ища примеры использования шейп-файлов. В конце концов я нашел «Чтение данных» , которое предложило несколько примеров самоанализа схемы в шейп-файле. Кроме того, пример ссылается на org / geotools / sampleData / statepop.shp, который выглядит подозрительно как путь к файлу из примеров в загрузке GeoTools. Конечно же, этот файл там.
Этот пример был удачной находкой, поскольку оказалось, что исходный шейп-файл, с которым я работал, имеет некоторые недостатки. Мои вторичные поиски также обнаружили некоторые страницы, освещающие трудности использования state_bounds.shp (представление в формате gif) , потому что он не включает границы состояний с океанами; очевидно, вы должны наложить другую карту поверх этой, чтобы получить их.
Поэтому я переключился на использование данных выборки.
В моем первом проходе DataLoader.java я написал функцию printSchema (), чтобы проверить схему данных, доступных в шейп-файле. Затем я добавил итератор внизу, чтобы просмотреть функции и запросить идентифицированные мной полезные атрибуты, и распечатать их.
Все вызовы GeoTools были взяты из двух приведенных выше примеров и были дополнены использованием автозаполнения Eclipse и javadoc для поиска интересных вызовов, чтобы получить то, что мне нужно. Оказалось, что класс MultiPolygon имеет собственный метод getCentroid (), поэтому мне не пришлось прибегать к его реализации самостоятельно.
Загрузка данных
Распечатка количества точек на многоугольник показала, что у некоторых многоугольников было несколько сотен и более точек, поэтому я решил придерживаться стратегии реализации центроидов.
Чтобы выполнить запрос, который мне нужен, мне нужно было поместить данные в мою базу данных. Я не собираюсь здесь рассказывать об основах настройки экземпляра MongoDB, но если вы новичок в MongoDB, начните здесь .
Я собираюсь использовать геопространственную индексацию MongoDB . Я могу использовать команду geoNear, чтобы запросить все точки рядом с данной точкой, и они будут возвращены в порядке расстояния, ближайшего к первому. Я настроил свою схему и индекс (см. Комментарии в коде), чтобы я мог искать центроиды, ближайшие к моей точке запроса.
Для этого перехода через DataLoader я создал класс MongoGeo с методами createGeoIndex () и insertRegion (). Я добавил код в DataLoader, чтобы создавать объекты данных из элементов, найденных итератором объекта, и использовать MongoGeo.insertRegion () для добавления их в базу данных.
Как только у меня это заработало, я запустил его, чтобы заполнить базу данных.
Беглый взгляд на данные показал, что он включает только смежные состояния:
$ ./mongo
MongoDB shell version: 2.1.2-pre-
connecting to: test
> use geobox
switched to db geobox
> show collections
bounds
system.indexes
> db.bounds.count();
49
> db.bounds.find({}, {_id:0, stateAbbr:1}).sort({stateAbbr:1});
{ "stateAbbr" : "AL" }
{ "stateAbbr" : "AR" }
{ "stateAbbr" : "AZ" }
{ "stateAbbr" : "CA" }
{ "stateAbbr" : "CO" }
{ "stateAbbr" : "CT" }
{ "stateAbbr" : "DC" }
{ "stateAbbr" : "DE" }
{ "stateAbbr" : "FL" }
{ "stateAbbr" : "GA" }
{ "stateAbbr" : "IA" }
{ "stateAbbr" : "ID" }
{ "stateAbbr" : "IL" }
{ "stateAbbr" : "IN" }
{ "stateAbbr" : "KS" }
{ "stateAbbr" : "KY" }
{ "stateAbbr" : "LA" }
{ "stateAbbr" : "MA" }
{ "stateAbbr" : "MD" }
{ "stateAbbr" : "ME" }
Fetched 20 record(s) in 36ms
Type "it" for more
>
Счет 49 привел меня к подозрению, что для Аляски (АК) не было данных, поэтому я проверил это выше. Это не имеет значения для этого эксперимента.
Запрос данных
Теперь, когда у меня есть база данных о многоугольниках и их центроидах, мне нужно иметь возможность запросить ее. Я добавил методы findConisting () и pointInPoly () в класс MongoGeo. Затем я написал простое тестовое приложение для командной строки LocationFinder.java , чтобы проверить запросы.
LocationFinder использует служебный метод testLocation () для поиска одного объекта. Я добавил несколько случайных вызовов в testLocation из main (). Чтобы сгенерировать тестовые звонки, я поднял Google Maps . Чтобы создать каждую контрольную точку, я щелкнул правой кнопкой мыши в случайном месте на карте и выбрал «Что здесь?» Когда я это сделал, широта и долгота точки появились во всплывающем окне, и я скопировал их в тестовый вызов. Обратите внимание, что код реализован для принятия (долгота, широта), чтобы соответствовать классической
декартовой координате (x, y), поэтому координаты точек должны быть заменены из представления Google Maps.
Я пробовал несколько контрольных точек внутри штатов, а также за пределами, и они дали ожидаемые результаты:
(-114.433594, 43.707594) is in Idaho, USA (-83.583984, 40.713956) is in Ohio, USA (-92.548828, 31.353637) is in Louisiana, USA (-90.087891, 25.482951) not found
Смотрите комментарии в коде для ссылок на места, которые я тестировал.
Заключительный комментарий
Когда я впервые нашел ссылки на шейп-файлы и GeoTools, я подумал, что это будет хорошей возможностью для обучения. Но я не чувствую, что я многое узнал об этом. Основываясь на двух шейп-файлах, с которыми я пытался работать, кажется, что шейп-файлы могут быть просто форматом базы данных плоских файлов с некоторыми ассоциированными библиотеками для их чтения. Это действительно все, что нужно?
Количество точек в этих данных кажется достаточно маленьким, поэтому мы должны задаться вопросом, стоит ли вообще беспокоиться о базе данных. Можно было бы просто загрузить данные в память во время запуска приложения и использовать их напрямую. Похоже, что GeoTools может даже иметь средства для создания геопространственного индекса в памяти, чтобы поддержать это (но если нет, я мог бы сделать это сам).
Хотя это правда, что здесь есть только небольшой объем данных, я создал это с учетом чего-то большего. Даже добавление стран не может значительно увеличить размер набора данных, но представьте, если мы добавим границы города. (Нам может потребоваться увеличить число битов разрешения, чтобы геохешинг стал более точным; подробности об этом см. В документации.) Города могут сделать это довольно большим, и было бы более разумным, чем строить индекс путь. База данных также обеспечивает удобное общее место для упорядочения и хранения информации, которая может поступать из многих источников в разных форматах. Мы могли бы дополнить информацию для регионов с течением времени. Поиск и загрузка дополнительных данных геолокации может быть долгосрочным проектом.