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?
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.
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.