Great discussion!

@chris, very good point, computing the bounding box intersection is indeed much cheaper then shape intersection, thatās why typically the recursive tree-based methods I mentioned store the bounding box, and not the polygon - best of both worlds! For example, hereās an explaination[1] of the typical workflow for using R-treeās (spatial indexing via 2D tree subdivision) where the bounding boxes are used for a quick first pass for intersection checks. So you get the logarithmic search (O(logN)) to find neighboring polygons, plus the constant intersection complexity (O(2)) check for bounding box.

Tangent 2: This raises a third factor that Iāve been thinking about for a while: the orientation of the coordinate system can really contradict the efficiency of the bounding box calculation. For example, the image below shows a bounding box intersection in the typical coordinate system (standard basis):

ā¦But here you can see if you use a more natural, rotated coordinate system for this geometry, you get tighter bounding boxes and avoid the costly intersection calculation:

I suspect thereās a mathematically rigorous way to compute an efficient ārotationā to the coordinate system at the beginning of an intersection calculation. It relates to computing the eigenvectors of a statistical measure of your shapes called the covariance matrix. In english this means identifying the most prominent axis of a collection of datapoints. I think this is a superior way to store and compute spatial dataā¦ but I havenāt actually tested it yet so I could be totally wrong about it. Thereās definitely some assumptions that need to be met for this to work.

[1] python - Understanding use of spatial indexes with RTree? - Geographic Information Systems Stack Exchange