This is a pre-production deployment of Warehouse. Changes made here affect the production instance of PyPI (pypi.python.org).
Help us improve Python packaging - Donate today!

Simple library for perform quick nearby search for geo spatial data.

Project Description

Simple library for perform quick nearby search for geo spatial data.

Requirements

  • python-geohash

It was written and tested on Python 2.7.

Installation

Get it from pypi:

pip install geoindex

or github:

pip install -e git://github.com/gusdan/geoindex.git#egg=geoindex

Simple use

If we have 100000 geo coordinates and we have to find some nearby location to given point and with given radius we can do something like this:

from geoindex import GeoGridIndex, GeoPoint

geo_index = GeoGridIndex()
for _ in range(10000):
    lat = random.random()*180 - 90
    lng = random.random()*360 - 180
    index.add_point(GeoPoint(lat, lng))

center_point = GeoPoint(37.7772448, -122.3955118)
for distance, point in index.get_nearest_points(center_point, 10, 'km'):
    print("We found {0} in {1} km".format(point, distance))

Search with associated data

When we fill index we can pass ref to GeoPoint as reference to some object and use it after:

from geoindex import GeoGridIndex, GeoPoint

index = GeoGridIndex()
for airport in get_all_airports():
    index.add_point(GeoPoint(lat, lng, ref=airport))

center_point = GeoPoint(37.7772448, -122.3955118)
for distance, point in index.get_nearest_points(center_point, 10, 'km'):
    print("We airport {0} in {1} km".format(point.ref, distance))

Performance

Creating index with 10000 random points and nearby search for each point took about 400ms. See tests/test_performance.py for more details.

How does it work

For perform quick search GeoGridIndex uses Geohash for each point and store it in internal dictionary. When we initialize GeoGridIndex we pass precision to constructor, based on it we divide all spaces with grid and store each point inside that grid. When we search nearest points we define cell with center point and 8 neighbors and check all points from these cells for distance to center.

Each cell has size dependent on precision, bellow you can find grid’s cell size and precision.

Precision Cell size
1 5000
2 1260
3 156
4 40
5 4.8
6 1.22
7 0.152
8 0.038

If you have created GeoGridIndex with precision = 4 it means what all points will be assign to grid with cell size = 40 km. And we can run search with radius less than 40/2km. If we’d like to make bigger radius we should create index with less precision 3.

But in other side if we create index with smallest precision (1) and will run search (get_nearest_points) with small radius (1km for example) it will works fine, but it will check all points inside 9 grid cells with size 5000km and it can be not so fast.

Release History

Release History

This version
History Node

0.0.1

Download Files

Download Files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

File Name & Checksum SHA256 Checksum Help Version File Type Upload Date
geoindex-0.0.1.tar.gz (4.7 kB) Copy SHA256 Checksum SHA256 Source Mar 1, 2014

Supported By

WebFaction WebFaction Technical Writing Elastic Elastic Search Pingdom Pingdom Monitoring Dyn Dyn DNS Sentry Sentry Error Logging CloudAMQP CloudAMQP RabbitMQ Heroku Heroku PaaS Kabu Creative Kabu Creative UX & Design Fastly Fastly CDN DigiCert DigiCert EV Certificate Rackspace Rackspace Cloud Servers DreamHost DreamHost Log Hosting