python: sorting two lists of polygons for intersections

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.

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.

Even just dividing your space up to smaller constant-size areas would speed up the intersection detection (if your polygons are small and sparse enough). You make a grid and mark each polygon to belong to some cells in the grid. And then find cells that have more than one polygon in them and make the intersection calculations for those polygons only. This optimization is the easiest to code, but the most ineffective. The second easiest and more effective way would be quadtrees. Then there are BSP tres, KD trees, and BVH trees that are probably the most effective, but the hardest to code.

Edit: Another optimization would be the following: find out the left-most and the right-most vertices of each polygon and put them in a list. Sort the list and then loop it somehow from left to right and easily find polygons whose bounding boxes' x coordinates overlap, and then make the intersection calculations for those polygons.