Reverse Geocoding Without Web Access [closed]

Question

I am working on an application where one of the requirements is that I be able to perform realtime reverse geocoding operations based on GPS data. In particular, I must be able to determine the state/province to which a latitude, longitude pair maps and detect when we have moved from one state/province to another.

I have a couple ideas so far but wondered if anyone had any ideas on either of the following:

• What is the best approach for tackling this problem in an efficient manner?
• Where is a good place to find and what is the appropriate format for North American state/province boundaries

As a starter, here are the two main ideas I have:

1. Break North America into a grid with each rectangle in the grid mapping to a particular state province. Do a lookup on this table (which grows quickly the more precise you would like to be) based on the latitude and then the longitude (or vice versa).
2. Define polygons for each of the states and do some sort of calculation to determine in which polygon a lat/lon pair lies. I am not sure exactly how to go about this. HTML image maps come to mind as one way of defining the bounds for a state/province.

I am working in python for the interested or those that might have a nice library they would like to suggest.

To be clear... I do not have web access available to me, so using an existing reverse geocoding service is not an option at runtime

Geisel

I'd love to hear more about how you solved this. Where did you end up getting the boundary data? – Leguminous

Answer 1

I suggest using a variant of your first idea: Use a spatial index. A spatial index is a data structure built from rectangles, mapping lat/long to the payload. In this case you will probably map rectangles to state-province pairs. An R-tree may be a good option. Here's an R-tree python package. You could detect roaming by comparing the results of consecutive searches.

Piane

Though I wasn't able to use the r-tree python project for my implementation I did use some of the ideas behind r-tree in that I built a simple spatial index using bounding rectangles for each of the states. After determining what bounding boxes the point lay in I used a point-in-polygon test to figure out the rest... works great! – Geisel

Glad to hear that. I misunderstood that you also needed this search for counties - for which a similar algorithm should also work, just need much more data.Anyway, have a happy roaming. – Piane

Answer 2

I created an offline reverse geocoding module for countries: https://github.com/richardpenman/reverse_geocode

>>> import reverse_geocode 
>>> coordinates = (-37.81, 144.96), (31.76, 35.21)
>>> reverse_geocode.search(coordinates)
[{'city': 'Melbourne', 'code': 'AU', 'country': 'Australia'},
 {'city': 'Jerusalem', 'code': 'IL', 'country': 'Israel'}]

I will see if I can add data for states.

Lederer

Thanks hoju, the tool is really amazing. And I have hunted it for years! – Croatian

Glad it was useful for other people - I needed this for my own projects – Lederer

Hi, this looks amazing. I am not Python dev myself but sometimes I include python scripts within my Node.js. Could you tell me which version of python does your script expect? – Materi

Answer 3

I would stay away from implementing your own solution from scratch. This is a pretty big undertaking and there are already tools out there to do this. If you're looking for an open source approach (read: free), take a look at this blog post: Using PostGIS to Reverse Geocode.

Linus

Excellent idea! This may very well be the way to go if you needed to solve this sort of problem on the desktop. Unforunately, and I should have mentioned this, I am running on an embedded platform which does not have support for Postgres (and it cannot be easily ported as it is not embedded linux, though it is posix based). A derivative of the Digi connectport is the platform: digi.com/products/wirelessdropinnetworking/idigi-kits/x4-zb.jsp – Geisel

Answer 4

If you can get hold of state boundaries as polygons (for example, via OpenStreetMap), determining the current state is just a point-in-polygon test.

If you need address data, an offline solution would be to use Microsoft Mappoint.

Kessinger

Answer 5

You can get data for the entire united states from open street map You could then extract the data you need such as city or state locations into what ever format works best for your application. Note although data quality is good it isn't guaranteed to be completely accurate so if you need complete accuracy you may have to look somewhere else.

Pallor

Answer 6

I have a database with all of this data and some access tools. I made mine from the census tiger data. I imagine it'd basically be an export of my database to sqlite and a bit of code translation.

Connate

@Mosche I've got one around here somewhere in sqlite format. Send me an email and I'll see what I can do. – Connate

Answer 7

The free reverse geocoding service I developed (www.feroeg.com) is based on spatialite, a sqlite library implementing SQL spatial capabilities (r-tree). The data are imported from OpenStreetMap (nation, cities, streets,street number) and OpenAddresses (street numbers) using proprietary tools. The entire world consumes about 250GB. There is a paper describing the architecture of the service: https://feroeg.com/Feroeg_files/Feroeg Presentation.pdf

At the moment the project (importer and server) is closed source.

Reverse Geocoding Library (C++) and converting tools are availabile on request.

Mississippian