python: sorting two lists of polygons for intersections

Question

I have two big lists of polygons.

Using python, I want to take each polygon in list 1, and find the results of its geometric intersection with the polygons in list 2 (I'm using shapely to do this).

So for polygon i in list 1, there may be several polygons in list 2 that would intersect with it.

The problem is that both lists are big, and if I simply nest two loops and run the intersection command for every possible pair of polygons, it takes a really long time. I'm not sure if preceding the intersection with a boolean test would speed this up significantly (e.g. if intersects: return intersection).

What would be a good way for me to sort or organize these two lists of polygons in order to make the intersections more efficient? Is there a sorting algorithm that would be appropriate to this situation, and which I could make with python?

I am relatively new to programming, and have no background in discrete mathematics, so if you know an existing algorithm that I should use, (which I assume exist for these kinds of situations), please link to or give some explanation that could assist me in actually implementing it in python.

Also, if there's a better StackExchange site for this question, let me know. I feel like it kind of bridges general python programming, gis, and geometry, so I wasn't really sure.

Answer 1

Quadtrees are often used for the purpose of narrowing down the sets of polygons that need to be checked against each other - two polygons only need to be checked against each other if they both occupy at least one of the same regions in the quadtree. How deep you make your quadtree (in the case of polygons, as opposed to points) is up to you.