[postgis-users] Fast bounding box intersection query against many edges

[Sandro Santilli]

On Tue, Jun 30, 2015 at 11:18:59PM -0400, Tom Kazimiers wrote:
> Hello everyone,
> 
> I use Postgres 9.4 and PostGIS 2.1 to represent about 13.000.000
> vertices in a 3D space (growing). Many points are connected in tree
> structures of varying size, often around 5000 nodes per tree. Therefore,
> we use single edges to represent them in our table. My aim is to have
> very fast queries to get all edges that intersect an arbitrary axis
> aligned bounding box.
> 
> From what I understand, one option (1) would be the &&& operator to get
> all all edges with (axis aligned, I assume) bounding boxes that
> intersect with my query bounding box. Or alternatively, (2) use
> ST_3DDWithin to get all edges that are within a distance of half my
> bounding box height to a polygon in Z that cuts my query bounding box in
> half.

[...]

> Option (1) is already pretty quick, but I get some false positives (due
> to intersecting bounding boxes of edges, not edges themself) that I
> would need to remove later (which is okay), but of course it would be
> nice to not have them in the first place. But there as well, better
> speed would be welcome.

The ST_3DDWithin function is currently _not_ using &&& operator.
It may actually be a good idea to make it do so.
In any case, you can manually mix the two. What speed do you get then ?

The query should then be:

SELECT te.id
FROM treenode_edge te
WHERE te.edge &&& 'LINESTRINGZ(41819.31354090536 81255.64336110713 102850, 59868.26425961124 88903.95239000155 102900)
  AND _st_3ddwithin(te.edge, ST_MakePolygon(ST_GeomFromText('LINESTRING(
    41819.31354090536 81255.64336110713 102825,
    59868.26425961124 81255.64336110713 102925,
    59868.26425961124 88903.95239000155 102925,
    41819.31354090536 88903.95239000155 102825,
    41819.31354090536 81255.64336110713 102825)')), 25);

--strk;