Using Python, how do I tell if a rectangle and a shape overlap?

I'm writing a program in Python. I have a series of shapes (polygons, defined as a sequence of coordinate pairs) and I need to tell if they overlap a particular rectangle.

Is there an easy algorithm for handling this? Or, better, is there a pure Python library that can handle these calculat开发者_开发百科ions for me?

Presuming your "arbitrary shapes" are indeed polygons (given that they're described as coordinate pairs), determining if they overlap (in any language) is a relatively trivial calculation. You merely need to compute if any side of polygon A intersects any other side of polygon B.

If you need an example, there's a rather thorough walkthrough at the Drexel Math Forum.

There are a number of Python modules which can assist you in this pursuit, such as Sympy, Numpy, PyGame, etc., but all of them are rather heavy if this is the only geometric calculation you need to make.