任意の長方形ではなくランダムな非衝突の正方形を生成するように変更できるかどうかについてのフォローアップの質問に対処するために、回答を少し変更しました。これは、元の回答の長方形の出力を後処理し、その内容を正方形のサブ領域に変換するという、最も簡単な方法で行いました。また、オプションの視覚化コードを更新して、両方の種類の出力を表示しました。明らかに、この種のフィルタリングを拡張して、各長方形または正方形をわずかに挿入して、それらが互いに接触しないようにするなどの他のことを行うことができます。
私の答えは、すでに投稿されている回答の多くが行うことを避けています。これは、既に作成されたものと衝突するものを拒否しながら、ランダムに長方形を生成します。これは、本質的に遅く、計算が無駄に聞こえるからです。私のアプローチは、代わりに、そもそも重複しないものだけを生成することに集中しています。
それは、それを非常に迅速に実行できる単純な領域細分割問題に変えることによって、実行する必要があることを比較的単純にします。以下は、それを行う方法の1つの実装です。それは、4つの小さな重なり合わない長方形に分割する外側の境界を定義する長方形から始まります。これは、半ランダムな内部ポイントを選択し、それを外側の長方形の4つの既存のコーナーポイントと一緒に使用して、4つのサブセクションを形成することによって実現されます。
ほとんどのアクションは関数内で行われ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
