How do I randomly fill a given rectangular region with rectangles of random sizes without the rectangles overlapping each other using NumPy?
My idea is to create a two dimensional array with the same shape as the region, fill the array with zero, then for each rectangle required, randomly select two coordinates inside the array that are not set, make a rectangle from the two points, and fill the region inside the array corresponding to the rectangle with 1.
Somehow it isn't working:
Code:
import matplotlib.pyplot as plt
import numpy as np
from matplotlib.patches import Rectangle
from random import randbytes, randrange
def random_rectangles(width=1920, height=1080, number=24):
fig = plt.figure(figsize=(width/100, height/100), dpi=100, facecolor='black')
ax = fig.add_subplot(111)
ax.set_axis_off()
grid = np.zeros((height, width))
for i in range(number):
free = np.transpose(np.nonzero(grid == 0))
y1, x1 = free[randrange(free.shape[0])]
y2, x2 = free[randrange(free.shape[0])]
if x1 > x2: x1, x2 = x2, x1
if y1 > y2: y1, y2 = y2, y1
grid[y1:y2, x1:x2] = 1
w, h = x2-x1, y2-y1
x, y = x1, -y2
color = '#' randbytes(3).hex()
ax.add_patch(Rectangle((x, y), w, h, fill=True,facecolor=color,edgecolor='#808080',lw=1))
plt.xlim(0, width)
plt.ylim(-height, 0)
plt.axis('scaled')
fig.subplots_adjust(left=0, bottom=0, right=1, top=1, wspace=0, hspace=0)
plt.show()
I don't understand, I have tried this:
import matplotlib.pyplot as plt
import numpy as np
from matplotlib.patches import Rectangle
import random
class Grid:
def __init__(self, x1, x2, y1, y2):
assert x2 > x1 and y2 > y1
self.x1 = x1
self.x2 = x2
self.y1 = y1
self.y2 = y2
self.subgrids = []
self.divisions = dict()
self.last_subgrid = None
def random(self):
if not self.subgrids:
x = self.x1 random.random() * (self.x2 - self.x1)
y = self.y1 random.random() * (self.y2 - self.y1)
return x, y
else:
if not self.last_subgrid:
subgrid = random.choice(self.subgrids)
self.last_subgrid = subgrid
return subgrid.random()
else:
x, y = self.last_subgrid.random()
self.last_subgrid = None
return x, y
def set_subgrid(self, shape):
x1, x2, y1, y2 = shape
assert x2 > x1 and y2 > y1
assert self.x1 <= x2 <= self.x2 and self.y1 <= y2 <= self.y2
if not self.subgrids:
eight = [
(self.x1, x1, self.y1, y1),
(x1, x2, self.y1, y1),
(x2, self.x2, self.y1, y1),
(x1, x2, y1, y2),
(x2, self.x2, y1, y2),
(self.x1, x1, y2, self.y2),
(x1, x2, y2, self.y2),
(x2, self.x2, y2, self.y2)
]
for a, b, c, d in eight:
if a != b and c != d:
subgrid = Grid(a, b, c, d)
self.subgrids.append(subgrid)
self.divisions[(a, b, c, d)] = subgrid
else:
for a, b, c, d in self.divisions:
if a <= x1 < x2 <= b and c <= y1 < y2 <= d:
self.divisions[(a, b, c, d)].set_subgrid((x1, x2, y1, y2))
def random_rectangles(width=1920, height=1080, number=24):
fig = plt.figure(figsize=(width/100, height/100), dpi=100, facecolor='black')
ax = fig.add_subplot(111)
ax.set_axis_off()
grid = Grid(0, width, 0, height)
for i in range(number):
x1, y1 = grid.random()
x2, y2 = grid.random()
if x1 > x2: x1, x2 = x2, x1
if y1 > y2: y1, y2 = y2, y1
grid.set_subgrid((x1, x2, y1, y2))
w, h = x2-x1, y2-y1
color = '#' random.randbytes(3).hex()
ax.add_patch(Rectangle((x1, y1), w, h, fill=True,facecolor=color,edgecolor='#808080',lw=1))
plt.xlim(0, width)
plt.ylim(0, height)
plt.axis('scaled')
fig.subplots_adjust(left=0, bottom=0, right=1, top=1, wspace=0, hspace=0)
plt.show()
It doesn't work:
I did it
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle
import random
class Grid:
def __init__(self, x1, x2, y1, y2):
assert x2 > x1 and y2 > y1
self.x1 = x1
self.x2 = x2
self.y1 = y1
self.y2 = y2
self.subgrids = []
def random(self):
if not self.subgrids:
x = self.x1 random.random() * (self.x2 - self.x1)
y = self.y1 random.random() * (self.y2 - self.y1)
four = [
(self.x1, x, self.y1, y),
(x, self.x2, self.y1, y),
(self.x1, x, y, self.y2),
(x, self.x2, y, self.y2)
]
for a, b, c, d in four:
if a != b and c != d:
subgrid = Grid(a, b, c, d)
self.subgrids.append(subgrid)
else:
random.choice(self.subgrids).random()
def flatten(self):
if not self.subgrids:
return
result = []
for subgrid in self.subgrids:
if not subgrid.subgrids:
result.append((subgrid.x1, subgrid.x2, subgrid.y1, subgrid.y2))
else:
result.extend(subgrid.flatten())
return result
def random_rectangles(width=1920, height=1080, number=24):
fig = plt.figure(figsize=(width/100, height/100), dpi=100, facecolor='black')
ax = fig.add_subplot(111)
ax.set_axis_off()
grid = Grid(0, width, 0, height)
for i in range(number): grid.random()
rectangles = grid.flatten()
for x1, x2, y1, y2 in rectangles:
w, h = x2-x1, y2-y1
color = '#' random.randbytes(3).hex()
ax.add_patch(Rectangle((x1, y1), w, h, fill=True,facecolor=color,edgecolor='#808080',lw=1))
plt.xlim(0, width)
plt.ylim(0, height)
plt.axis('scaled')
fig.subplots_adjust(left=0, bottom=0, right=1, top=1, wspace=0, hspace=0)
plt.show()
I finally did it, but the result is not what I imagined, and I don't think my implementation is good enough. Can anyone help me?
CodePudding user response：
You can achieve a better result by tackling your problem in another direction.
What you have done is to split up the sample space into subspaces for each time you sample, then you sample within said subspaces again (or something similar to that).
If you split your sample space beforehand you can get a grid of even sampling spaces of which you can sample from instead:
import numpy as np
from matplotlib import pyplot as plt
from matplotlib.patches import Rectangle
from numpy.typing import ArrayLike
from numpy.random import default_rng
rng = default_rng(42069)
def get_rects(n: int) -> np.ndarray:
"""
Params
------
n: number of rectangles
"""
rects = []
ceilsqrtn = int(np.ceil(np.sqrt(n)))
n_grids = ceilsqrtn * ceilsqrtn
rects = rng.uniform(size = (n, 4))
# Create rectangles in the "full space", that is the [0, 1] space
rects[:,0], rects[:,1] = np.min(rects[:,:2], 1), np.max(rects[:,:2], 1)
rects[:,2], rects[:,3] = np.min(rects[:,2:], 1), np.max(rects[:,2:], 1)
# Create a ceilsqrtn x ceilsqrtn even grid space
flat_grid_indices = rng.choice(n_grids, n, False)
# Move each rectangle into their own randomly assigned grid
# This will result with triangles in a space that is ceilsqrtn times larger than the [0, 1] space
offsets = np.array(np.unravel_index(flat_grid_indices, (ceilsqrtn, ceilsqrtn)))
rects[:,:2] = offsets[1][..., None]
rects[:,2:] = offsets[0][..., None]
# Scale everything down to the [0, 1] space
rects /= ceilsqrtn
return rects
def plot_rects(rects: ArrayLike, width: int = 800, height: int = 800):
fig = plt.figure(figsize=(width/100, height/100), dpi=100, facecolor='black')
ax = fig.add_subplot(111)
ax.set_axis_off()
for x1, x2, y1, y2 in rects:
ax.add_patch(Rectangle((x1, y1), x2 - x1, y2 - y1, facecolor='red', edgecolor='#808080', fill=True))
fig.subplots_adjust(left=0, bottom=0, right=1, top=1, wspace=0, hspace=0)
plt.show()
rects = get_rects(138)
plot_rects(rects)
Result:
It is a good start at least. To obtain rectangles with other characteristics you could simply sample from another distribution, such as a Gaussian. With that, you would obtain more similar rectangles, but you would need to clip the ones that overflow into other subspaces or something like that. Another alternative are truncated distributions within the [0,1] domain.