Geo-region data for countries/states/oceans

views:

answers:

+1 Q:

Geo-region data for countries/states/oceans

I'm developing an application where entities are located at positions on Earth. I want to have a set of data from which I can determine what region(s) a point is contained within.

Regions may be of types:

Continent
Country
Lake
Sea
DMZ
Desert
Ice Shelf

...and so forth.

I'm envisioning representing each region as a polygon. For any given point, I would test to see if it is contained in each polygon. Alternative ideas are very welcome.

I am also hoping to find public domain data sets that contain some or all of these boundaries.

Some of these polygons are going to be enormously detailed (possibly more detailed than I need) and so I need tips on performing these calculations efficiently. Methods for simplifying 2D polygons would also be useful I expect. What are the best practices for these kinds of things?

Can anyone recommend any good resources of this data, any particular programming approaches or existing software libraries that do this kind of thing?

EDIT

I should point out that the data set of regions will be fairly static, so precomputation is a good option if it improves performance.

+1 A:

If you're on a plane, the common algorithm is to draw a random straight half line from your point and checking for the number of intersections points with the given polygon. If it is odd, you're inside, if it is even, you're outside. You have to beware of vertices and of numerical inaccuracies.

Now, you're on a sphere. You can project it on a plane (the actual projection you use can depend on the polygon) and do the above.

Alexandre C. 2010-09-03 14:30:03

Drew Noakes 2010-09-03 14:53:14

Do you have any thoughts on precomputing for query efficiency? I'm thinking along the lines of calculating bounding boxes, or perhaps dividing the earth into small sections and maintaining lists of regions that at least partially enclose each sub-section so as to narrow down the list that must be evaluated, both in terms of the number of polygons, and the number of line segments to check against.

Drew Noakes 2010-09-03 14:57:35

inner/outer approximation of your polygons (like inner and outer bounding boxes, but a perhaps more complicated) should get a lot of the complexity away. However, this can be difficult to do.

Alexandre C. 2010-09-03 15:58:58

Also optimizing the "ray tracing" part may involve partitioning the (projected) space with quadtrees for instance.

Alexandre C. 2010-09-03 15:59:43

+1 A:

A great resource is Natural Earth.

Natural Earth is a public domain map dataset available at 1:10m, 1:50m, and 1:110 million scales. Featuring tightly integrated vector and raster data, with Natural Earth you can make a variety of visually pleasing, well-crafted maps with cartography or GIS software.

The data is provided as ESRI Shapefiles. There are many Shapefile libraries in existence.

If you can't find support for Shapefiles in your programming languages, this PDF details the file format.

Drew Noakes 2010-09-04 12:28:37

ansaurus

tags:

views:

answers:

Geo-region data for countries/states/oceans

related questions