5

I tried to using the algorithm shown here: https://discuss.leetcode.com/topic/15733/my-java-solution-sum-of-areas-overlapped-area

However, that algorithm only deals with finding the areas of only TWO overlapped rectangles.

How would I go on about finding the area of the intersection of say 3, or 4 or 5, etc number of overlapping rectangles, if I know the length, breadth of each rectangle?

benten
  • 1,995
  • 2
  • 23
  • 38
Lorren112
  • 93
  • 1
  • 2
  • 6
  • 2
    Are you looking for the union of _n_ rectangles, or the intersection? If intersection, do you want to count _any_ overlapping areas, or only where _all_ the rectangles overlap? – Kevin J. Chase Aug 20 '16 at 04:20
  • Intersection, where all the rectangles overlap – Lorren112 Aug 20 '16 at 04:27
  • 2
    Please [edit] your question to include important details like that, so people don't waste their time solving the wrong problem. (Note that the first answer you've received starts with, "I'm assuming you want to find the area of the **union**...".) – Kevin J. Chase Aug 20 '16 at 04:30
  • You can look at this code as well, https://stackoverflow.com/a/75378206/16733101 – Hamzah Feb 07 '23 at 19:39

1 Answers1

9

Shapely is a good library for stuff like this. 

from shapely.geometry import box

# make some rectangles (for demonstration purposes and intersect with each other)
rect1 = box(0,0,5,2)
rect2 = box(0.5,0.5,3,3)
rect3 = box(1.5,1.5,4,6)

rect_list = [rect1, rect2, rect3]

# find intersection of rectangles (probably a more elegant way to do this)
for rect in rect_list[1:]:
    rect1 = rect1.intersection(rect)
intersection = rect1

To visualize what's happening here. I plot the rectangles and their intersection:

from matplotlib import pyplot as plt
from matplotlib.collections import PatchCollection
from matplotlib.patches import Polygon

# plot the rectangles before and after merging 

patches  = PatchCollection([Polygon(a.exterior) for a in rect_list], facecolor='red', linewidth=.5, alpha=.5)
intersect_patch =  PatchCollection([Polygon(intersection.exterior)], facecolor='red', linewidth=.5, alpha=.5)

# make figure
fig, ax = plt.subplots(1,2, subplot_kw=dict(aspect='equal'))
ax[0].add_collection(patches, autolim=True)
ax[0].autoscale_view()
ax[0].set_title('separate polygons')
ax[1].add_collection(intersect_patch, autolim=True)
ax[1].set_title('intersection = single polygon')
ax[1].set_xlim(ax[0].get_xlim())
ax[1].set_ylim(ax[0].get_ylim())
plt.show()

enter image description here

Heng Zhang
  • 3
  • 3
benten
  • 1,995
  • 2
  • 23
  • 38
  • how do i install shapely.geometry on mac OS X? – Lorren112 Aug 20 '16 at 03:12
  • 2
    Behold the docs: https://pypi.python.org/pypi/Shapely. If you are using the Anaconda dist, you can use `conda install shapely` in the command line (recommended). – benten Aug 20 '16 at 03:23
  • Alright, I used conda to execute that installation line of code, now it says " usage: install [-bCcpSsv] [-B suffix] [-f flags] [-g group] [-m mode] [-o owner] file1 file2 install [-bCcpSsv] [-B suffix] [-f flags] [-g group] [-m mode] [-o owner] file1 ... fileN directory install -d [-v] [-g group] [-m mode] [-o owner] directory ... " What do I do now – Lorren112 Aug 20 '16 at 04:01
  • 2
    well, if we assume all the input rectangles are intersecting each other, then the proposed for-loop computation seems reasonable. But the general case is given a list of rectangles, how to efficiently find if there is any overlapped area by multiple rectangles (>2). – galactica Oct 09 '18 at 17:32