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

Question

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 calculations for me?

Are your aribitrary shapes really aribitrary shapes, or rather polygons? Is the "sequence of coordinate pairs" describing the vertices of these polygons? If not, what is it? — Sven Marnach
– Sven Marnach, Commented Feb 23, 2011 at 15:03

Glorfindel · Accepted Answer · 2022-10-09 18:11:13Z

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.

The "sides intersect" doesn't work, in the case where polygon A completely contains polygon B.
@Chris Check that the intersection point is between the endpoints of both sides you're checking (xA1 <= xInt <= xA2 and xB1 <= xInt <= xB2 and yA1 <= yInt <= yA2 and yB1 <= yInt <= yB2)
@Chris: If you want to include containment, you can use the crossing lines interior to the polygon. It adds computation time, but not complexity.

Collectives™ on Stack Overflow

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

1 Answer 1

3 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Related