[geos-devel] Which one of "n" polygons contains this point?

[Frederik Ramm]

Hi,

    I have a few hundred polygons representing country borders. And I 
have a few hundred million points, and for each, I want to record the 
country it lies in. I have about an hour of computing time to spend for 
this task.

A simple and working algorithm is of course to create the polygons for 
the countries, then for each point, do a "contains" test for all 
polygons until a match is found. Unfortunately many of these polygons 
are quite complex (the outline taking anything from 1.000 to 50.000 
nodes) which makes the "contains" test expensive, especially if you are 
planning to execute it for a large number of points.

Now I can think of a number of optimisations (divide earth into a grid 
of rectangles, record which polygons overlap any given grid square, thus 
reducing the number of "contains" tests you have to perform), but before 
I set about playing around with these I wanted to ask if you are aware 
of anything deep down it the GEOS guts that might help.

There is a class of algorithms that efficiently solves my problem, 
called "point location algorithms", however the only available 
implementation for this I could find comes from the CGAL library which 
has a license problem (my application must be GPL and the specific CGAL 
component I'm after is licensed in a GPL incompatible way).

Thank you
Frederik

-- 
Frederik Ramm  ##  eMail frederik at remote.org  ##  N49°00'09" E008°23'33"