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

[Paul Ramsey]

Build your polygons.
Turn them into "prepared" geometries.
Build an STRTree on the polygons.

Now, each point can find a short-list of possible countries in about
log(n) time (thanks to STR tree) and (more importantly, thanks to the
prepared geometry feature) can determine whether they are inside said
countries in about log(v) time (where v = number of vertices).

Not sure if you can do your 100M points in an hour w/ this (0.036ms
per point reqd), but I think it's the best GEOS will do for you,
as-is.

P.

Algorithm guys on list can sort you out, but the "best" solution would
probably be a coverage topology of your border edges, with an index on
the edges so you can quickly determine what your leftwards and
rightwards edges are for a given point in the coverage.

On Fri, Nov 6, 2009 at 1:15 PM, Frederik Ramm <frederik at remote.org> wrote:
> 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"
> _______________________________________________
> geos-devel mailing list
> geos-devel at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/geos-devel
>