Menu
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?
510
Practical Data Science using PythonTwo rectangles overlap when the area of their intersection is positive. So, two rectangles that only touch at the corner or edges do not overlap. So, if the input is like R1 = [0,0,2,2], R2 = [1,1,3,3], then the output will be True.
Its top and bottom edges are perpendicular to the X-axis, while its left and right edges are perpendicular to the Y-axis. If the area of their intersection is positive, two rectangles overlap. Two rectangles that touch at the corners or edges do not overlap.
One option would be to enclose each shape in an imaginary circle. If those circles overlap, you can then imagine smaller tighter circles in the vicinity of the original intersection. Repeat the calculations with smaller and smaller circles as often as desired.
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.
69
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
