Optimizing line-poly intersect queries

[David Fawcett]

I am attempting to optimize some queries examining the spatial
relationship between a line layer and a poly layer. Each line segment
may intersect one or more polygons.

The line data set contains 12000 features. The larges polygon data
set contains 10000 features. The features are quite high-resolution.

I have written the query to utilize an Rtree index, but I am concerned
that there could be cases where the line segment intersects more than
one polygon, but the line segment is not fully contained by the mbr of
all of the polygons that it intersects.

SELECT auids.auid AS auid, minors.minor5 AS minor
FROM stream_auids2010 auids, minorwshd_dnr minors
WHERE intersects(auids.geometry, minors.geometry)
AND auids.rowid IN
(
SELECT pkid FROM idx_stream_auids2010_Geometry
WHERE xmin > MbrMinX(minors.Geometry) AND
xmax < MbrMaxX(minors.Geometry) AND
ymin > MbrMinY(minors.Geometry) AND
ymax < MbrMaxY(minors.Geometry)
)
ORDER BY auid

I definitely get a performance boost from the spatial index, I am just
worried about missing intersections where the line feature is not
fully contained by the MBR of a polygon.

I also thought about an alternative strategy using MBR Cache, but
can't come up with a SQL statement that returns the IDs from both the
intersecting polygons and utilizes MBRintersects() or
FilterMBRintersects().

Any suggestions are greatly appreciated.

David.

[David Fawcett]

Based on this post:
http://groups.google.com/group/spatialite-users/browse_thread/thread/311331a57c0f34b1/4511e7a6f7b894cd?lnk=gst&q=mbrcache#4511e7a6f7b894cd

I have modified my query to use a mbrCache:

SELECT auids.auid as auid,
minors.minor5 as minor
FROM stream_auids2010 auids,
minorwshd_dnr_mbrtest minors
WHERE INTERSECTS(auids.Geometry, minors.Geometry)
AND auids.ROWID IN
(
SELECT rowid
FROM cache_stream_auids2010_mbrtest_Geometry
WHERE mbr = FilterMbrIntersects(
MbrMinX(minors.Geometry),
MbrMinY(minors.Geometry),
MbrMaxX(minors.Geometry),
MbrMaxY(minors.Geometry) )
)

This takes ~45 minutes on a Windows XP , Core2 Duo E8400 @ 3 GHz with
3.25GB RAM. and returns ~22,000 records.

[a.furieri]

Hi David,

I can simply add some remarks:

a) I don't think using MbrCache can grant
you a significant speed-up. I suppose
R*Tree is better suited for such tasks.

b) I don't understand your fears about
'missing intersections'.
An intersection can exist only if
entities MBRs overlaps: so checking
MBRs via R*Tree is enough.

c) Anyway I notice an error in your SQL,
because it has to be:
--------------
...
WHERE xmin < MbrMaxX(minors.Geometry) AND
xmax > MbrMinX(minors.Geometry) AND
ymin < MbrMaxY(minors.Geometry) AND
ymax > MbrMinY(minors.Geometry)
...
--------------
your original code will discard any MBR not
fully contained within the other one MBR :-)

d) optimizing complex spatial queries on
SpatiaLite is more an art than a science:
have you tried inverting the evaluation order ?
I mean, checking the 'auid' R*Tree instead of
checking the 'minors' R*Tree.
sometimes it makes a dramatic difference

bye
Sandro