Find the area of the union of overlapping rectangles

Overview

There are times when you want to find the area of the union part of randomly overlapping rectangles like this.

You see, this kind of thing that is popular these days. (Image borrowed from here: https://note.nkmk.me/python-opencv-face-detection-haar-cascade/)

I can manage this by drawing an auxiliary line and calculating it manually, but it is quite difficult to calculate it properly. https://mathcommunication.hatenablog.com/entry/2016/10/11/003213#%E5%B9%B3%E9%9D%A2%E5%9B%B3%E5%BD%A2%E3%81%AB%E5%AF%BE%E3%81%99%E3%82%8B%E5%8F%AF%E6%B8%AC%E6%80%A7%E3%81%A8%E9%9D%A2%E7%A9%8D

NP-hard? It's impossible for ordinary people, so

policy

Draw directly and count the pixels.

The value is not as beautiful as when it is calculated by the formula, and there is an error in the resolution, but I think there aren't many cases where that becomes a problem.

In particular,

Binarize

Count black (fill color) pixels

Since opencv has a function called countNonZero, I use this. https://docs.opencv.org/2.4/modules/core/doc/operations_on_arrays.html#countnonzero

code

Let's go.

`requirements.txt`


cycler==0.10.0
kiwisolver==1.2.0
matplotlib==3.2.1
numpy==1.18.4
opencv-python==4.2.0.34
Pillow==7.1.2
pyparsing==2.4.7
python-dateutil==2.8.1
six==1.14.0

Since it is random, the position and size of the rectangle will change each time it is executed.

`a.py`


from PIL import Image, ImageDraw
import numpy as np
import cv2

import random
import matplotlib


rects = [
    (random.randrange(200),
        random.randrange(200),
        random.randrange(50, 120),
        random.randrange(50, 120)
    ) for x in range(20)
]

colors = random.sample(matplotlib.colors.cnames.keys(), len(rects))

#For line art
im1 = Image.new('RGB', (200, 200), (255, 255, 255))
d1 = ImageDraw.Draw(im1)
#For confirmation of binary conversion
im2 = Image.new('RGB', (200, 200), (255, 255, 255))
d2 = ImageDraw.Draw(im2)

#Rectangle drawing
for r, c in zip(rects, colors):
    print(c, r)
    d1.rectangle(r, outline=c)
    d2.rectangle(r, fill=(0, 0, 0))

im1.save("a1.png ")
im2.save("a2.png ")

#Binary conversion
nim = np.array(im2, dtype=np.uint8)
gim = cv2.cvtColor(nim, cv2.COLOR_RGB2GRAY)
ret, bwim = cv2.threshold(gim, 0, 255, cv2.THRESH_OTSU)

#Image after binary conversion
cv2.imwrite("b1.png ", bwim)

whitePixels = cv2.countNonZero(bwim)
blackPixels = bwim.size - whitePixels

print("-"*50)
print(whitePixels, blackPixels, bwim.size)
print("filled area rate:", blackPixels / bwim.size)

Run

`bash`


$ python a.py
gainsboro (188, 158, 61, 63)
palegreen (174, 182, 118, 53)
chartreuse (75, 34, 82, 81)
olive (170, 10, 93, 111)
mistyrose (183, 65, 78, 52)
indianred (25, 55, 51, 109)
mediumaquamarine (102, 155, 59, 89)
navy (169, 127, 85, 96)
darkviolet (103, 152, 76, 51)
yellowgreen (84, 6, 73, 118)
deeppink (42, 61, 95, 90)
bisque (47, 101, 107, 105)
dimgrey (95, 179, 91, 70)
maroon (146, 182, 88, 62)
whitesmoke (189, 118, 83, 112)
lavender (71, 149, 104, 117)
burlywood (36, 82, 105, 82)
darkslategrey (122, 128, 103, 52)
mediumslateblue (163, 121, 84, 92)
silver (144, 126, 61, 58)
--------------------------------------------------
18580 21420 40000
fill area rate: 0.5355

end.

reference

https://note.nkmk.me/python-pillow-imagedraw/ https://techtech-sorae.com/pythonopencv%E3%81%A7%E4%BA%8C%E5%80%A4%E7%94%BB%E5%83%8F%E3%81%8B%E3%82%89%E7%99%BD%E3%81%A8%E9%BB%92%E3%81%AE%E9%9D%A2%E7%A9%8D%E6%AF%94%E3%82%92%E7%AE%97%E5%87%BA/