Я немного изменил свой ответ, чтобы ответить на ваш дополнительный вопрос о том, можно ли его изменить, чтобы вместо этого генерировать случайные неконфликтующие квадраты , а не произвольные прямоугольники.Я сделал это самым простым способом, который мог бы сработать: постобработать прямоугольный вывод моего исходного ответа и превратить его содержимое в квадратные субрегионы.Я также обновил дополнительный код визуализации, чтобы показать оба вида вывода.Очевидно, что такого рода фильтрация может быть расширена, чтобы делать другие вещи, такие как небольшая вставка каждого прямоугольника или квадрата, чтобы они не соприкасались друг с другом.
Мой ответ избегает делать то, что делают многие из уже опубликованных ответов, а именно генерировать случайноПрямоугольники, отвергая любые, которые сталкиваются с уже созданными - потому что это звучит по своей сути несколько медленно и вычислительно расточительно.Вместо этого он концентрируется только на генерировании тех, которые не перекрываются с самого начала.
Это делает то, что должно быть сделано, относительно простым, превращая его в проблему деления на области, которая может быть решена очень быстро.Ниже приведена одна реализация того, как это можно сделать.Он начинается с прямоугольника, определяющего внешнюю границу, которую он разделяет на четыре меньших непересекающихся прямоугольника.Это достигается путем выбора полуслучайной внутренней точки и использования ее вместе с четырьмя существующими угловыми точками внешнего прямоугольника для формирования четырех подразделов.
Большая часть действия выполняется в функции quadsect().Выбор внутренней точки имеет решающее значение при определении того, как выглядит результат.Вы можете ограничить его любым удобным для вас способом, например, выбрать только тот, который приведет к тому, что под прямоугольники будут иметь минимальную ширину или высоту или не больше некоторой величины.В примере кода в моем ответе он определяется как центральная точка ± 1 / 3 от ширины и высоты внешнего прямоугольника, но в основном любая внутренняя точка будет работать до некоторой степени.
Поскольку этот алгоритм очень быстро генерирует под прямоугольники, можно потратить некоторое вычислительное время на определение внутренней точки деления.
Чтобы помочь визуализировать результаты этого подхода, есть некоторые несущественныекод в самом конце, который использует модуль PIL (Python Imaging Library) для создания файла изображения, отображающего прямоугольники, сгенерированные во время некоторых тестовых прогонов, которые я сделал.
В любом случае, вот последняя версия кода и выводобразцы:
import random
from random import randint
random.seed()
NUM_RECTS = 20
REGION = Rect(0, 0, 640, 480)
class Point(object):
def __init__(self, x, y):
self.x, self.y = x, y
@staticmethod
def from_point(other):
return Point(other.x, other.y)
class Rect(object):
def __init__(self, x1, y1, x2, y2):
minx, maxx = (x1,x2) if x1 < x2 else (x2,x1)
miny, maxy = (y1,y2) if y1 < y2 else (y2,y1)
self.min, self.max = Point(minx, miny), Point(maxx, maxy)
@staticmethod
def from_points(p1, p2):
return Rect(p1.x, p1.y, p2.x, p2.y)
width = property(lambda self: self.max.x - self.min.x)
height = property(lambda self: self.max.y - self.min.y)
plus_or_minus = lambda v: v * [-1, 1][(randint(0, 100) % 2)] # equal chance +/-1
def quadsect(rect, factor):
""" Subdivide given rectangle into four non-overlapping rectangles.
'factor' is an integer representing the proportion of the width or
height the deviatation from the center of the rectangle allowed.
"""
# pick a point in the interior of given rectangle
w, h = rect.width, rect.height # cache properties
center = Point(rect.min.x + (w // 2), rect.min.y + (h // 2))
delta_x = plus_or_minus(randint(0, w // factor))
delta_y = plus_or_minus(randint(0, h // factor))
interior = Point(center.x + delta_x, center.y + delta_y)
# create rectangles from the interior point and the corners of the outer one
return [Rect(interior.x, interior.y, rect.min.x, rect.min.y),
Rect(interior.x, interior.y, rect.max.x, rect.min.y),
Rect(interior.x, interior.y, rect.max.x, rect.max.y),
Rect(interior.x, interior.y, rect.min.x, rect.max.y)]
def square_subregion(rect):
""" Return a square rectangle centered within the given rectangle """
w, h = rect.width, rect.height # cache properties
if w < h:
offset = (h - w) // 2
return Rect(rect.min.x, rect.min.y+offset,
rect.max.x, rect.min.y+offset+w)
else:
offset = (w - h) // 2
return Rect(rect.min.x+offset, rect.min.y,
rect.min.x+offset+h, rect.max.y)
# call quadsect() until at least the number of rects wanted has been generated
rects = [REGION] # seed output list
while len(rects) <= NUM_RECTS:
rects = [subrect for rect in rects
for subrect in quadsect(rect, 3)]
random.shuffle(rects) # mix them up
sample = random.sample(rects, NUM_RECTS) # select the desired number
print '%d out of the %d rectangles selected' % (NUM_RECTS, len(rects))
#################################################
# extra credit - create an image file showing results
from PIL import Image, ImageDraw
def gray(v): return tuple(int(v*255) for _ in range(3))
BLACK, DARK_GRAY, GRAY = gray(0), gray(.25), gray(.5)
LIGHT_GRAY, WHITE = gray(.75), gray(1)
RED, GREEN, BLUE = (255, 0, 0), (0, 255, 0), (0, 0, 255)
CYAN, MAGENTA, YELLOW = (0, 255, 255), (255, 0, 255), (255, 255, 0)
BACKGR, SQUARE_COLOR, RECT_COLOR = (245, 245, 87), (255, 73, 73), (37, 182, 249)
imgx, imgy = REGION.max.x + 1, REGION.max.y + 1
image = Image.new("RGB", (imgx, imgy), BACKGR) # create color image
draw = ImageDraw.Draw(image)
def draw_rect(rect, fill=None, outline=WHITE):
draw.rectangle([(rect.min.x, rect.min.y), (rect.max.x, rect.max.y)],
fill=fill, outline=outline)
# first draw outlines of all the non-overlapping rectanges generated
for rect in rects:
draw_rect(rect, outline=LIGHT_GRAY)
# then draw the random sample of them selected
for rect in sample:
draw_rect(rect, fill=RECT_COLOR, outline=WHITE)
# and lastly convert those into squares and re-draw them in another color
for rect in sample:
draw_rect(square_subregion(rect), fill=SQUARE_COLOR, outline=WHITE)
filename = 'square_quadsections.png'
image.save(filename, "PNG")
print repr(filename), 'output image saved'
Выходной образец 1
Выходной образец 2
