数学背景
1. 代数
- 1st degree function (or [Wikipedia]: Linear function https://en.wikipedia.org/wiki/Linear_function) is a function ([Wikipedia]: function https://en.wikipedia.org/wiki/Function_(mathematics)) whose:
- 表达式可以写为：
f(x) = a * x + b (a and b常数，x多变的）
- 图形表示是一条直线xOy plane ([维基百科]：笛卡尔坐标系 https://en.wikipedia.org/wiki/Cartesian_coordinate_system)
2. 平面几何
-
平面由（无限）个点组成：让我们通过坐标来引用一个点，可以将其称为：
-
abscissa or 横坐标或（简单地）x
-
ordinate or 纵坐标或（简单地）y
-
平面上的点分布在二维空间中
-
平面上的每个点都可以通过其唯一标识x and y
-
平面上的一些点可能具有一些共同的特征：例如直线上的一堆点...直线上的点满足直线equation（这个表达式通常定义为${function（来自上一段）结果} = ${值})
-
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
-
！重要的提示 ！：这里讨论的一切都适用于各种函数（不想说all），但我仅限于线性函数，为了清楚起见
-
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 + b0 and f1(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)) < 0
-
更进一步：正方形由 2 组平行线（其边）组成；如果一个点位于每对线之间，则该点位于正方形内。
代码00.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:
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
关于方块一代的几句话
- 如输出中所示，对于 30 个显示的方块，1135已生成（在本次运行中）。那是因为它们重叠了
- 如果从main
allow_overlapping = True, 生成值输出中将匹配方块的数量（最大平方数)
- 如果增加最大平方数假设值高于50，生成值的数量将呈指数增长（生成它们所需的时间也会呈指数增长），并且程序将进入无限循环的机会（因为它将无法生成不与另一个正方形重叠的正方形）一）也会成长
