如何生成不相交的正方形(随机定位、大小相等、随机旋转)? [英] How to generate squares (randomly located, equally sized, randomly rotated) that don't intersect each other?
问题描述
我一直致力于在 1x1 网格上生成一层随机旋转并放置的正方形.我已经能够生成一个在网格上随机放置和旋转的正方形，但我不确定如何改进代码以生成更多不相交的随机正方形.当前代码如下所示:
<块引用>[cfati@CFATI-5510-0:e:\Work\Dev\StackOverflow\q046081491]>e:\Work\Dev\VEnvs\py_064_03.05.04_test0\Scripts\python.exe"代码00.py统计:平方数:30允许重叠:假生成的值:1135关于方块生成的几句话
- 如输出所示，对于 30 个显示的方块，生成了 1135(在本次运行中).那是因为它们重叠了
- 如果从 main
allow_overlapping = True更改，输出中的生成值 将匹配平方数 (MAX_SQUARES) - 如果将 MAX_SQUARES 增加到比 50 更高的值，生成的值的数量将呈指数级增加(生成它们所需的时间也会增加)，并且程序将进入无限循环(因为它将无法生成不与另一个正方形重叠的正方形)也会增长
I've been working on generating a layer of randomly rotated and placed squares on a 1x1 grid. I have been able to generate a single square that is randomly placed and rotated on the grid, but I'm not sure how to improve the code to generate more random squares that do not intersect with each other. Current code seen below:
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()
I do not have a CS background (I'm an environmental engineering major) and I am extremely inexperienced with coding. Please give me any recommendations that you may have for me to try and tackle this problem with!
Math background
1. Algebra
- 1st degree function (or [Wikipedia]: Linear function) is a function ([Wikipedia]: function) whose:
- Expression can be written as:
f(x) = a * x + b(a and b constants, x variable) - Graphical representation is a straight line in the xOy plane ([Wikipedia]: Cartesian coordinate system)
- Expression can be written as:
2. Plane Geometry
A plane consists of an (infinite) number of points: let's refer to a point by its coordinates which can be referred to as:
- abscissa or horizontal coordinate or (simply) x
- ordinate or vertical coordinate or (simply) y
The points in the plane spread across 2 dimensions
In the plane, every point can be uniquely identified by its x and y
Some of the points in the plane might have some common characteristics: e.g. a bunch of points that are on a straight line... a point that is on a straight line satisfies the line straight line equation (which is an expression generally defined as ${function (from previous paragraph) result} = ${value})
So, in short: for a point P0(x0, y0), if
y0 == f(x0), the point is located on that straight line (and more: depending on y0 being greater / lower than f(x0), P0 is located above / below the straight line in the xOy plane). Again, I want to state that for non linear functions,y = f(x)still applies (as it's the general equation formula), but other operators (e.g. <, >) don't- ! Important Note !: everything discussed here applies to a variety of functions (don't want to say all), but I'm limiting to linear functions, for clarity's sake
A straight line is determined by 2 distinct points (e.g. P0(x0, y0), P1(x1, y1)) - the equation for that straight line would be
y = a * x + b(in our example:y = ((y0 - y1) / (x0 - x1)) * x + (y0 - x0 * ((y0 - y1) / (x0 - x1)))); !! Of course it worth mentioning the "vertical" (parallel to Oy) line which is !! not a function !!Example: having 2 distinct parallel (non Bolyai :) ) lines:
f0(x) = a * x + b0andf1(x) = a * x + b1(a is the same for both lines - this is the condition for them to be parallel) and an external point P0(x0, y0) (that obviously doesn't belong to any of the lines). How to determine if P0 is between the 2 lines? Well, the point must be above (the lower) one and below the other (the higher one). Translated into math (considering f0 being the lower one):y0 > f0(x0)(y0 - f0(x0) > 0)y0 < f1(x0)(y0 - f1(x0) < 0)
From the above observations (and there may be more wisdom), this is the condition that the point coordinates should satisfy:
(y0 - f0(x0)) * (y0 - f1(x0)) < 0Going further: a square consists of 2 sets of parallel lines (its sides); if a point is between each lines pair, then the point is in the square.
code00.py:
#!/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()
Notes:
I didn't work with matplotlib before (actually, I
pip installed it for this task)General comments:
- A point is represented by a tuple representing its coordinates: (x, y)
- A square is a tuple consisting of 4 points (p0, p1, p2, p3)
get_func_deg1:
- Returns the function that describes the line that contains the 2 points given as arguments
- If the 2 points are on a line that is parallel to Oy (there's no "normal" function to describe it), simply return None
is_point_in_square:
- Determines if a point is inside a square
- Uses the logic explained above, except
- For the special case when the square edges are parallel to Ox and Oy when it uses some simple arithmetic operations
squares_overlap:
- Determines whether 2 squares overlap (I'm sure there are faster "algorithms")
- Checks if any of the 1st square corners are inside the 2nd one
- The other way around: checks if any of the 2nd square corners are inside the 1st one
- Since the above 2 checks are not enough (imagine a regular [Wikipedia]: Octagon and unifying its vertices every 2nd one: there will be 2 squares neither having its corners in the other one, but sharing their "central" areas), also check that one square's center is inside the other one
generate_random_point:
- Generates a point in the given bounding box
- safety_margin specifies the (minimum) distance that the generated point should be away from any of the bounding box sides, in order that any square that will have this point as a corner, would fit entirely in the bounding box
generate_random_angle:
- Generates a random angle between 0 and (π / 2)
generate_random_square:
- Generates a random point, a random angle, and constructs a square starting from there, using the specified side
- squares_to_avoid is a list of squares. After the square is generated, it is checked against every square from that list. If the 2 squares overlap, the square is regenerated
square_to_plot:
- Converts a square (from a tuple of points) to matplotlib format (2 tuples consisting of xs and ys with the 1st element duplicated as the last)
main:
- The main function
__generation_monitor (0):
- Internal function used for profiling
In order to change the number of squares, modify MAX_SQUARES
Output:
[cfati@CFATI-5510-0:e:\Work\Dev\StackOverflow\q046081491]> "e:\Work\Dev\VEnvs\py_064_03.05.04_test0\Scripts\python.exe" code00.py STATS: Squares: 30 Allow overlapping: False Generated values: 1135
Few words about the squares generation
- As seen in the output, for 30 displayed squares, 1135 were generated (at this run). That is because they were overlapping
- If changing from main
allow_overlapping = True, Generated values in the output will match the number of squares (MAX_SQUARES) - If increasing MAX_SQUARES to values let's say higher than 50, the number of generated values will increase exponentially (so will the time needed to generate them), and the chance that the program will enter an infinite loop (because it won't be able to generate a square that doesn't overlap to another one) will grow as well
这篇关于如何生成不相交的正方形(随机定位、大小相等、随机旋转)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
