Find the area of the union of overlapping rectangles

Overview

a1.png

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/) img

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

b1.png

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/

Recommended Posts

Find the area of the union of overlapping rectangles
How to find the area of the Voronoi diagram
Find the definition of the value of errno
Find the ratio of the area of Lake Biwa by the Monte Carlo method
Migemo version of the: find command,: mfind
Find the coefficients of the least squares polynomial
Combinatorial optimization to find the hand of "Millijan"
Find the number of days in a month
Find the divisor of the value entered in python
Find the solution of the nth-order equation in python
Find out the day of the week with datetime
Find the geometric mean of n! Using Python
Projecet Euler 12 Find the number of divisors without division.
Find the sum of unique values with pandas crosstab
Find out the location of Python class definition files.
Find out the version of the language you are running
Find out the location of packages installed with pip
The beginning of cif2cell
Find the maximum Python
The meaning of self
Union Find on networkX
the zen of Python
The story of sys.path.append ()
Revenge of the Types: Revenge of types
I tried to find the entropy of the image with python
How to find the optimal number of clusters in k-means
Maya | Find out the number of polygons in the selected object
Find out the apparent width of a string in python
I tried to find the average of the sequence with TensorFlow
[Python] Heron's formula functionalization and calculation of the maximum area
Inherit the standard library to find the average value of Queue
Python --Find out number of groups in the regex expression
Find the index of the maximum value (minimum value) of a multidimensional array
How to find the scaling factor of a biorthogonal wavelet
Find the diameter of the graph by breadth-first search (Python memory)
Find the average / standard deviation of the brightness values in the image
Find the eigenvalues of a real symmetric matrix in Python