[postgis-users] Deleting many points falling outside a large polygon (but within the bbox)

[Tim Keitt]

I have a very large table of points; basically I pushed a raster
extending over much of the western hemisphere at 1km resolution into
the db as xyz (actually 2d points + z in another column). Not a crazy
as it sounds as you can do a lot of interesting things intersecting
these grid points with other geometries, and I have a lot of RAM and
disk space available. The region of interest however is much smaller
than the original raster and is defined by a large polygon (certain
continent margins) composed of many vertices. Deleting the points
outside the bounding box of the roi is reasonably quick, however there
are many points that remain within the bbox, but outside the polygon.
These take forever to cull as it appears the entire polygon has to be
searched for each point. Its looking like this will at least take
days, perhaps much more on a fairly fast machine.

I'm curious if anyone has a reasonable solution. I was thinking of
dumping the roi polygon as points and then recursively subdividing the
bounding box, building quad-polygons on the way down. Those quads that
contain roi points are split into 4 while those that contain no points
remain. After a few recursion levels, you figure out which
quad-polygons are disjoint from the roi polygon and delete any
enclosed grid points. Points intersecting quads that are within the
roi polygon are not touched. Grid points within the remaining quads
would have to be searched one-by-one, but that should be a small
fraction of the total. Basically the idea is to emulate a kind of
quad-tree index in pure sql. Or alternatively I'll just come back in a
few weeks and see if the brute force query is done...

THK

-- 
Timothy H. Keitt
http://www.keittlab.org/