How to very efficiently assign lat/long to city boundary described by shape?

Question

I have a huge shapefile of 36.000 non-overlapping polygones (city boundaries). I want to easily determine the polygone into which a given lat/long falls. What would the best way given that it must be extremely computationaly efficient ?

I was thinking of creating a lookup table (tilex,tiley,polygone_id) where tilex and tiley are tile identifiers at zoom levels 21 or 22. Yes, the lack of precision of using tile numbers and a planar projection is acceptable in my application.

I would rather not use postgres's GIS extension and am fine with a program that will run for 2 days to generate all the INSERT statements.

Answer 1

Insert statements into what? Are you using a different spatial database or some other database? If you are willing to use python, C, or Java you could use shapely, GEOS, or JTS to write some custom code to do what you want rather simply.

In python use this lib to open the shapefile http://indiemaps.com/blog/2008/03/easy-shapefile-loading-in-python/

then shapely http://gispython.org/shapely/docs/1.0/manual.html#contains to test containment

For Java use Geotools which also includes JTS.

Answer 2

Sounds like you want a BSP tree. Basically you divide the area into smaller and smaller polygons in a tree like fashion.

The advantage is that you don't need to compare coordinates with every polygon later on. That makes it a very fast way to find the correct polygon.