如何生成彼此不相交的正方形（随机定位，大小相等，随机旋转）？

Question

我一直致力于在1x1网格上生成一层随机旋转和放置的正方形。我已经能够生成一个随机放置并在网格上旋转的单个方块，但我不确定如何改进代码以生成更多不相互交叉的随机方块。目前的代码如下：

Example of my One Randomized Square

from math import cos, pi, sin
from random import randint
from matplotlib.mlab import frange
from matplotlib.pyplot import plot, axis, show

def flake_position_layer1(): #Determines the initial position of one corner of the square
    x0 = randint(0, 100) / 100
    y0 = randint(0, 100) / 100
    theta = randint(0, 90) * pi / 180 #Angle of rotation for the square
    return x0, y0, theta


def flake_shape(): #generates the other 3 corners of the square
    x0, y0, z, theta = flake_position_layer1()
    x1 = x0 + (0.1 * cos(theta))
    x2 = x1 + (0.1 * cos((90 * pi/180) + theta))
    x3 = x2 + (0.1 * cos((180 * pi/180) + theta))
    y1 = y0 + (0.1 * sin(theta))
    y2 = y1 + (0.1 * sin((90 * pi/180) + theta))
    y3 = y2 + (0.1 * sin((180 * pi/180) + theta))
    return x0, x1, x2, x3, y0, y1, y2, y3


def display(): #connects the 4 corners on a plot
    x0, x1, x2, x3, y0, y1, y2, y3 = flake_shape()
    return plot([x0, x1, x2, x3, x0], [y0, y1, y2, y3, y0])


display()
axis([0,1,0,1]) #1x1 grid
show()

我没有CS背景（我是环境工程专业），我对编码非常缺乏经验。请给我任何建议，让我尝试解决这个问题！

Answer 1

数学背景

1. Algebra

• 1度函数（或[Wikipedia]: Linear function）是一个函数（[Wikipedia]: function），其函数为： 表达式可以写成：f(x) = a * x + b（a和b常量，x变量） 图形表示是xOy平面中的直线（[Wikipedia]: Cartesian coordinate system）

2. Plane Geometry

• 一个平面由（无限）个点组成：让我们通过坐标引用一个点，可以称为： 横坐标或水平坐标或（简称）x 纵坐标或纵坐标或（简称）y
• 飞机上的点分布在两个维度上
• 在平面中，每个点都可以通过其x和y唯一标识
• 飞机上的一些点可能具有一些共同特征：例如直线上的一串点......直线上的点满足直线方程（通常定义为$ {function（来自上一段）结果} = $ {value} ）
• 因此，简而言之：对于点P0（x0，y0），如果y0 == f(x0)，该点位于该直线上（并且更多：取决于y0大于/小于f（x0），P0位于上方/下方在xOy平面上的直线）。同样，我想说明，对于非线性函数，y = f(x)仍然适用（因为它是一般方程式），但其他运算符（例如<，>）不适用 ！重要提示！：这里讨论的所有内容都适用于各种功能（不想全部说明），但为了清晰起见，我限制了线性功能
• 直线由2个不同的点确定（例如P0（x0，y0），P1（x1，y1）） - 该直线的等式为y = a * x + b（在我们的例子中：y = ((y0 - y1) / (x0 - x1)) * x + (y0 - x0 * ((y0 - y1) / (x0 - x1)))）; ！当然值得一提的是“垂直”（与Oy平行）线!!不是功能!!
• 示例：具有2个不同的并行（非Bolyai :)）行：f0(x) = a * x + b0和f1(x) = a * x + b1（两个行的a是相同的 - 这是它们并行的条件）和外部点P0（x0，y0）（显然不是不属于任何一条线。如何确定P0是否介于2行之间？那么，要点必须高于（低）一个高于另一个高一低（高一个）。转换成数学（考虑f0是较低的一个）： y0 > f0(x0)（y0 - f0(x0) > 0） y0 < f1(x0)（y0 - f1(x0) < 0） 从上面的观察（可能有更多的智慧），这是点坐标应满足的条件：(y0 - f0(x0)) * (y0 - f1(x0)) < 0
• 更进一步：一个正方形由两组平行线（其两侧）组成;如果每个线对之间有一个点，则该点位于正方形中。

code.朋友:

#!/usr/bin/env python3

import sys
from random import random, seed
from math import pi, sin, cos, sqrt
import matplotlib.pyplot as plt

pi_2 = pi / 2

MINX = MINY = 0
MAXX = MAXY = 1
DEFAULT_SIDE = 0.1
DEFAULT_SAFETY_MARGIN = DEFAULT_SIDE * sqrt(2)
MAX_SQUARES = 30

__global_generation_counter = 0


def get_func_deg1(p0, p1):
    (x0, y0), (x1, y1) = p0, p1
    if x0 == x1:
        return None
    a = (y0 - y1)/(x0 - x1)
    b = y0 - x0 * a
    return lambda x: a * x + b


def is_point_in_square(p, sq):
    x, y = p
    p0, p1, p2, p3 = sq
    side_func0 = get_func_deg1(p0, p1)
    side_func1 = get_func_deg1(p1, p2)
    side_func2 = get_func_deg1(p2, p3)
    side_func3 = get_func_deg1(p3, p0)
    if not side_func0 or not side_func1 or not side_func2 or not side_func3:
        xmin = min(p0[0], p2[0])
        xmax = max(p0[0], p2[0])
        ymin = min(p0[1], p2[1])
        ymax = max(p0[1], p2[1])
        return xmin <= x <= xmax and ymin <= y <= ymax
    return ((y - side_func0(x)) * (y - side_func2(x))) <= 0 and \
           ((y - side_func1(x)) * (y - side_func3(x))) <= 0


def squares_overlap(square0, square1):
    for p0 in square0:
        if is_point_in_square(p0, square1):
            return True
    for p1 in square1:
        if is_point_in_square(p1, square0):
            return True
    xc0 = (square0[0][0] + square0[2][0]) / 2
    yc0 = (square0[0][1] + square0[2][1]) / 2
    if is_point_in_square((xc0, yc0), square1):
        return True
    # The "reverse center check" not needed, since squares are congruent
    """
    xc1 = (square1[0][0] + square1[2][0]) / 2
    yc1 = (square1[0][1] + square1[2][1]) / 2
    if is_point_in_square((xc1, yc1), square0):
        return True
    """
    return False


def __generation_monitor():
    global __global_generation_counter
    __global_generation_counter += 1


def generate_random_point(minx=MINX, miny=MINY, maxx=MAXX, maxy=MAXY, safety_margin=DEFAULT_SAFETY_MARGIN):
    if maxx - minx < 2 * safety_margin or maxy - miny < 2 * safety_margin:
        print("MUEEE")
        safety_margin = 0
    x = safety_margin + random() * (maxx - minx - 2 * safety_margin)
    y = safety_margin + random() * (maxy - miny - 2 * safety_margin)
    __generation_monitor()
    return x, y


def generate_random_angle(max_val=pi_2):
    return random() * max_val


def generate_random_square(side=DEFAULT_SIDE, squares_to_avoid=()):
    while 1:
        restart = False
        x0, y0 = generate_random_point()

        angle = generate_random_angle()
        x1 = x0 + side * cos(angle)
        y1 = y0 + side * sin(angle)

        angle += pi_2
        x2 = x1 + side * cos(angle)
        y2 = y1 + side * sin(angle)

        angle += pi_2
        x3 = x2 + side * cos(angle)
        y3 = y2 + side * sin(angle)

        ret = (x0, y0), (x1, y1), (x2, y2), (x3, y3)
        for square in squares_to_avoid:
            if squares_overlap(ret, square):
                restart = True
        if restart:
            continue
        return ret


def square_to_plot(square):
    xs, ys = zip(square[0], square[1], square[2], square[3])
    return xs + (xs[0],), ys + (ys[0],)


def main():
    seed()
    squares = list()
    allow_overlapping = False # CHANGE to True to allow square to overlap
    for _ in range(MAX_SQUARES):
        #print("Generating:", _)
        if allow_overlapping:
            square = generate_random_square()
        else:
            square = generate_random_square(squares_to_avoid=squares)
        squares.append(square)
    plot_squares = tuple()
    for sq in squares:
        plot_squares += square_to_plot(sq)
    print("STATS:\n    Squares: {}\n    Allow  overlapping: {}\n    Generated values: {}".format(MAX_SQUARES, allow_overlapping, __global_generation_counter))
    plt.plot(*plot_squares)
    plt.axis([MINX, MAXX, MINY, MAXY])
    plt.show()


if __name__ == "__main__":
    print("Python {:s} on {:s}\n".format(sys.version, sys.platform))
    main()

笔记：

• 之前我没有使用matplotlib（实际上，我为此任务进行了pip installed）
• 普通的留言： 一个点由表示其坐标的元组表示：（x，y） 正方形是由4个点组成的元组（p0，p1，p2，p3）
• get_func_deg1： 返回描述包含作为参数给出的2个点的行的函数 如果2个点位于与Oy平行的线上（没有“正常”函数来描述它），则只返回None
• is_point_in_square： 确定点是否在正方形内 使用上面解释的逻辑，除了 对于特殊情况，当方形边缘与Ox和Oy平行时，它使用一些简单的算术运算
• squares_overlap： 确定2个方格是否重叠（我确定有更快的“算法”） 检查第一个方角是否在第二个方角内 反过来说：检查第一个角落是否在第一个角落内 由于上面的两个检查是不够的（想象一个常规的[Wikipedia]: Octagon并且每隔一个统一它的顶点：将有2个正方形在另一个中没有角，但是共享它们的“中心”区域），也检查一个正方形的中心在另一个里面
• generate_random_point： 在给定的边界框中生成一个点 safety_margin指定生成的点应该远离任何边界框边的（最小）距离，以便将此点作为角点的任何方格完全适合边界框
• generate_random_angle： 生成0到（π/ 2）之间的随机角度
• generate_random_square： 生成随机点，随机角度，并使用指定的边构造从那里开始的正方形 squares_to_avoid是一个正方形列表。生成正方形后，将对照该列表中的每个正方形进行检查。如果2个正方形重叠，则重新生成正方形
• square_to_plot： 将一个正方形（从一个点的元组）转换为matplotlib格式（由xs和ys组成的2个元组，其中第一个元素重复为最后一个）
• 主要： 主要功能
• __generation_monitor *： 用于分析的内部函数
• 要更改方块数，请修改MAX_SQUARES

输出：

[cfati@CFATI-5510-0:e:\Work\Dev\StackOverflow\q046081491]> "e:\Work\Dev\VEnvs\py_064_03.05.04_test0\Scripts\python.exe" code.py
STATS:
    Squares: 30
    Allow  overlapping: False
    Generated values: 1135

---

* - 关于方块生成的几句话

• 如输出中所示，对于30个显示的正方形，生成了1135个（在此运行中）。那是因为它们重叠了
• 如果从主allow_overlapping = True更改，输出中的生成值将与平方数匹配（MAX_SQUARES）
• 如果将MAX_SQUARES增加到值，例如高于50，则生成值的数量将呈指数增长（生成它们所需的时间也将增加），以及程序进入无限循环的可能性（因为它无法进行生成一个不与另一个重叠的正方形）也会增长

Answer 2

好的，这是我在shapely包的帮助下得到的。安装帮助在这里的底部。最终结果：

Code walkthrough

• distance是一个辅助函数，使用Point类从形状上找到两个坐标之间的距离。只是一个帮手功能以后。
• Square实例化一个新的多边形。它有4个角，每个角为（x，y）对，其中心为一个坐标，标量值等于对角线距离的一半。
• test_overlap通过标题非常自我解释。但从逻辑上讲，它的作用是：找到两个形状之间从中心到中心的距离。然后找到每个形状的半对角线的总和。如果中心距离大于总和，则方块不能重叠。
• Squares以一个空容器（空列表）开始，并尝试向其添加方块。但是对于每个可能的新增加，它首先测试与现有方块没有重叠。

Code

import math
import random

from shapely.geometry import Polygon, Point


def distance(a, b):
    return Point(a).distance(Point(b))


class Square(object):
    def __init__(self):
        self.x0, self.y0 = random.random(), random.random()
        theta = random.randint(0, 90) * math.pi / 180  # Angle of rotation
        self.x1 = self.x0 + (0.1 * math.cos(theta))
        self.x2 = self.x1 + (0.1 * math.cos((90 * math.pi/180) + theta))
        self.x3 = self.x2 + (0.1 * math.cos((180 * math.pi/180) + theta))
        self.y1 = self.y0 + (0.1 * math.sin(theta))
        self.y2 = self.y1 + (0.1 * math.sin((90 * math.pi/180) + theta))
        self.y3 = self.y2 + (0.1 * math.sin((180 * math.pi/180) + theta))
        self.corners = ((self.x0, self.y0), (self.x1, self.y1), 
                        (self.x2, self.y2), (self.x3, self.y3))

    @property
    def center(self):
        """(x, y) of the center of the polygon."""
        return Polygon(self.corners).centroid.coords[0]

    @property
    def half_diag(self):
        """The distance of 1/2 the shape's diagonal (center-to-corner)."""
        p0, p1, p2, p3 = self.corners
        return 0.5 * distance(p0, p1) * math.sqrt(2)


def test_overlap(square1, square2):
    """Do two shapes overlap?  

    Note this is a 'conservative' test.  May return True if they do not
    (false positive), but will never return False if they do (false negative).
    """

    # Distance between two centers
    ctc = distance(square1.center, square2.center)
    # Sum of half-diagonals
    halfdiags = square1.half_diag + square2.half_diag
    res = ctc < halfdiags
    return res


class Squares(object):
    def __init__(self):
        self.squares = []

    def add_square(self):
        new_square = Square()
        if not self.squares:
            # Initial empty list/container - just add without any tests
            self.squares.append(new_square)
        else:
            while True:
            # Test that new_square overlaps with existing
                res = [test_overlap(square, new_square) for square in self.squares]
                if any(res):
                    # We have at least 1 case of overlap (1 True)
                    new_square = Square()
                else:
                    # Safe to add
                    self.squares.append(new_square)
                    break

    def plot_squares(self):
        for square in self.squares:
            (x0, y0), (x1, y1), (x2, y2), (x3, y3) = square.corners
            plt.plot([x0, x1, x2, x3, x0], [y0, y1, y2, y3, y0])  

Example

import itertools
%matplotlib inline
for _ in itertools.repeat(None, 10):
    # Add 10 squares; you could also just build this into the class
    sqs.add_square()
sqs.plot_squares()

Installing shapely

如果您还没有安装Anaconda发行版。然后只需使用conda-forge进行整形安装。从cmd运行：

conda config --add channels conda-forge
conda install shapely

Glaring deficiency

在某个时刻，你的方块容器被填满，剩下的空间很小，无法添加新的形状。即使有可用空间，该功能基本上是反复试验，因此在高形状计数时需要很长时间。目前发生在大约20-25个方格（1.0x1.0方框）。

Answer 3

您需要一个函数来确定两个立方体是否相交。

from math import cos, pi, sin
from random import random
from matplotlib.mlab import frange
from matplotlib.pyplot import plot, axis, show,axes

LEN = 0.1


def rotate(point, theta):
    x = point[0]
    y = point[1]
    x_ = x * cos(theta) + y * sin(theta)
    y_ = - x * sin(theta) + y * cos(theta)
    return x_, y_


class CUBE(object):
    def __init__(self, x, y, theta):
        self.corner = [(LEN / 2, LEN / 2),
                       (-LEN / 2, LEN / 2),
                       (-LEN / 2, -LEN / 2),
                       (LEN / 2, -LEN / 2)
                       ]
        self.theta = theta
        self.x = x
        self.y = y
        for i in range(4):
            self.corner[i] = rotate(self.corner[i], theta)
            self.corner[i] = (self.corner[i][0] + x,
                              self.corner[i][1] + y)


def is_include(cube, point):
    point = [point[0] - cube.x, point[1] - cube.y]
    point = rotate(point, -cube.theta)
    if (point[0] < -LEN / 2
            or point[0] > LEN / 2
            or point[1] < -LEN / 2
            or point[1] > LEN / 2
            ):
        return False
    else:
        return True


def is_intersect(cube1, cube2):
    if (any([is_include(cube1, point) for point in cube2.corner])
            or any([is_include(cube2, point) for point in cube1.corner])
            or is_include(cube1, (cube2.x, cube2.y))):
        return True
    else:
        return False


def plot_cube(cube,n):
    plot(
        [cube.corner[i][0] for i in [0, 1, 2, 3, 0]],
        [cube.corner[i][1] for i in [0, 1, 2, 3, 0]])
    ax = axes()
    ax.text(cube.x,cube.y,str(n))


def display(cubelist):  # connects the 4 corners on a plot
    for i,cube in enumerate(cubelist):
        plot_cube(cube,i)
    axis([0, 1, 0, 1])  # 1x1 grid
    show()


cubelist = []

for i in range(100):
    x0 = random()
    y0 = random()
    theta = random() * pi
    cube = CUBE(x0, y0, theta)
    if any(is_intersect(cube,cb) for cb in cubelist):
        continue
    else:

        cubelist.append(cube)

display(cubelist)