Bounded box on postgis

Question

I have a few MULTIPOLYGON geometries that are very complex to work with, and I need to find POINT geometries from a ~40M rows that are inside these MULTIPOLYGON geometries.
Right now I'm working with ST_Within but things are going on extremely slowly.

I don't need all of the POINT geometries, just a few of them, but they all have to be inside of the MULTIPOLYGON (I need a few points per geometry).

I thought that if there was something reverse to an envelope, that is to find the largest box that is within a geometry.

I couldn't find it in the docs or Google or here.

Is it possible to create such a box? If so, how?

I do not want to use simplify since it is:

1. Not accurate enough.
2. Still slow.

Answer 1

Try to dump the multipolygons to polygons. Build gist index and see what happens.

CREATE TABLE single_polygons AS
SELECT (ST_Dump(geom)).geom geom FROM multipolygon_table;

CREATE INDEX idx_sp_geom
ON single_polygons
USING GIST(geom);

ANALYZE single_polygons;

EDIT Of course you want an index. The index finds all points inside the bounding box of the multipolygon very fast. Then a function is rechecking which of those points inside the bounding box actually is inside the geometry.

The reason I suggest splitting the MultiPolygons to Polygons is that the bounding box will be unnessecary expanded and catch unnessecary many points to recheck if it is a MultiPolygon since the index is built on the bouning box around the whole MultiPolygon.

If you only wants a few points you can always limit the answer to the amount of points you want.

SELECT p.geom, p.id 
FROM point_table p, single_polygons sp 
WHERE ST_Intersects(p.geom, sp.geom) 
LIMIT 10;

Answer 2

A GiST index on the MULTIPOLYGON geometries will speed up the search. Sometimes use of the ST_DWithin function in a CTE will further cut down the search space, but in this case I don't think it will help you any more than the spatial index alone.

Answer 3

Create a grid of regular polygons small enough to ensure that every MULTIPOLYGON will contain at least one. Then query the MULTIPOLYGONS with ST_Within against the grid with a LIMIT 1. Finally, run your point ST_Within query against the selected grid polygon.

Perhaps any ST_Within query against your complex geometry is too expensive, but it might work.