Given (lon,lat), how can I quickly retrieve the containing administrative region?

Question

Given a coordinate (lon,lat), I'd like to retrieve the containing administrative region (state/province level) for an offline mobile application. The method employed needs to be fast/efficient. NaturalEarthData is one source I found that has the required shape/attribute data (http://www.naturalearthdata.com/downloads/10m-cultural-vectors/10m-admin-1-states-provinces/).

I'm looking for suggestions on how to convert (lon,lat) into its corresponding administrative region. The obvious way is running point in polygon and maybe preempting it with a bounding box check. Are there better ways?

edit:

Spacedman: When I meant mobile I meant device side; right now I'm targeting embedded Linux, Android and QNX (BlackBerry). I think GEOS might be overkill -- I don't know if its worth adding all of GEOS for spatial indexing. In either case, right now I'm trying out this method and R.K.'s raster approach as well.

R.K.: This seems like a great idea, especially since the data is static... but I'm having a bunch of trouble trying to generate an image to do the lookup. I'm a novice with foss gis tools but I haven't been able to generate what I need with Mapnik or QGIS so far.

The NaturalEarthData shapefile separates each admin region into separate geometries with unique ids. I added an attribute column to this shapefile that converts the uid directly into a color, thinking it'd be possible to render a map where I could set the color of each polygon based on the attribute... that assumption didn't pan out too well. I'll keep at it though, and update this question with a properly selected answer soon.

edit2:

Alright, so with the preliminary testing I did, I think that the raster approach worked out a bit better for me. The size of the data ended up being much smaller compared to the vector data and the look up times were pretty quick (most of the time is spent loading a tile into memory). The overall complexity of the raster implementation is pretty low as well. The time taken for point in polygon tests for vector data varies a lot based on polygon shape, and you need to watch out for multipolygon definitions / erroneous geometry as well.

I created a really large map (36000x18000) so I got an acceptable level of accuracy (100px/degree latitude) with respect to the consideration of geopolitical borders. The raster data + meta data (admin region name) only took up 2.5mb.

Answer 1

You might want to try using GEOS, a C++ port of the Java Topology Suite:

http://trac.osgeo.org/geos/

You were on the right lines with a bounding-box check, but the even smarter way is build a spatial index which means you can do better than O(n) for that first pass. GEOS can build spatial indexes for you.

I'm wondering what mobile platform you're developing for - or is this the server side? In which case stick your data in a PostGIS database and do your spatial queries there (with spatial indexing as well).

Answer 2

What you are trying to do is to Reverse geocode information.

Since you'are going offline only you have imho two options:

1) Incorporate to your software a portable spatial db (eg. spatialite) loaded with the data you want. 2) You can use any reverse geocoding data dump (eg GeoNames data dump) as reference for your program (more info)

Either options I think are well suited for your needs. Then you'll have to parse the coordinates from the event and compare them with the data and display the result.

Hope it helps.

Answer 3

Just an idea, what about a raster approach? Your whole region would be a raster grid instead of polygons. Instead of a point in polygon operation, you would just:

1. Convert lon lat to pixel/cell coordinate
2. Retrieve pixel/cell value
3. Check for corresponding state/province on lookup table.

There would a a corresponding loss in precision though but I think it would be fast. If you do go with the point in polygon approach, you might find this thread on point in polygon analysis with big data useful.