algorithm - Finding if two polygons Intersect in Python?

I'm looking for an algorithm, a high level solution, or even a library which can help me determine if two polygons intersect, in Python.

I have the vertices of the two polygons (These are single part polygons without any holes) in two different arrays. The polygons are 2D (i.e. just X and Y coordinates)

I'll like to make an function which will return a boolean indicating whether these two polygons intersect.

Please note that I cannot use arcpy, or any arcgis components in this.

Can you suggest an algorithm or library for doing this?

Answer

You could try shapely.

They describe spatial relationships and it work on windows

The spatial data model is accompanied by a group of natural language relationships between geometric objects – contains, intersects, overlaps, touches, etc. – and a theoretical framework for understanding them using the 3x3 matrix of the mutual intersections of their component point sets

The following code shows how you can test for intersection:

from shapely.geometry import Polygon
p1 = Polygon([(0,0), (1,1), (1,0)])
p2 = Polygon([(0,1), (1,0), (1,1)])
print(p1.intersects(p2))