Python: sorting two polygon lists for intersections

Question

I have two large 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 use shapely ).

So, for a polygon, I in list 1 may have several polygons in list 2 that will intersect with it.

The problem is that both lists are large, and if I just nest two loops and run the intersection command for each Possible pair of polygons, it takes a very long time. I am not sure if it would be much faster to do this before crossing the boolean test (for example, if crossing: return the intersection).

What would be a good way to sort or organize these two lists of polygons to make intersections more efficient? Is there a sorting algorithm that matches this situation and that I could do with python?

I am relatively new to programming and have no background in discrete mathematics, so if you know the existing algorithm that I should use (which, I believe, exists for such situations), please provide a link or explanation that could help me really actually implementing it in python.

Also, if there is a better StackExchange site for this question, let me know. I feel that these are the bridges of general python, gis and geometry programming, so I was not sure.

Answer 1

Squares are often used to narrow sets of polygons that need to be checked on each other - for two polygons you only need to be checked on each other if they both occupy at least one of the same areas in the quadrant. How deep you make your quadrant (in the case of polygons, as opposed to points) is up to you.

Answer 2

Even simply dividing the space into smaller areas with a constant size will speed up intersection detection (if your polygons are small and sparse). You create a grid and note that each polygon belongs to some grid cells. And then find the cells that have more than one polygon in them, and make intersection calculations only for these polygons. This optimization is easiest to code, but the most inefficient. The second simplest and most effective way is quadrants. Then there are BSP tres, KD trees, and BVH trees, which are probably the most efficient, but the most complex for the code.

Edit: Another optimization will be as follows: find the left and right vertices of each polygon and put them on the list. Sort the list, and then loop it somehow from left to right and easily find the polygons whose x-coordinates of the overlay overlap, and then do the intersection calculations for these polygons.