生成 "scattered" 个不重叠的项目
Generate "scattered" items, that do not overlap
这是一个我必须解决的问题，但在过去的 5 天里我一直在用头撞墙。一定有一些非常简单的东西我错过了，或者误解了，因为逻辑在我脑海中似乎 100% 正确，但它就是行不通。
我需要画 "scattered" 个不重叠的房子，共 100 个。
我必须使用 turtle 来绘制它们，所以我有 X 和 Y 坐标。
X 和 Y 列表用于验证目的，看看房子是否已经在那个地方。
我正在做的是在随机坐标上绘制一个 "house"（顶部有一个三角形的正方形），
我在房屋数量少于 100 时循环。
在每个循环中，我随机化 x 和 y 坐标，从那里我开始用乌龟绘制每个房子。
我检查该值是否已经在 X 和 Y 验证列表中，以及我的新 X 和 Y 是否为 +/- 房子的大小（将其视为正方形）
import turtle
import time
import random
t = turtle.Turtle()
turtle.screensize(1920,1000)
x_verif = []
y_verif = []
t.speed(0)
collision = None
def square():
for s in range(0, 4):
t.forward(90)
t.left(90)
def triangle():
for s in range(0, 2):
t.left(-60)
t.forward(52)
def house():
square()
t.left(90)
t.forward(90)
triangle()
def scatter():
print("a")
house()
x1 = random.randint(-850, 850)
y1 = random.randint(-380, 380)
count = 0
while count < 100:
print("a2")
i = 0
u = 0
collision = False
for tries in range (0, 2):
print("a3")
x_verif.append(x1)
y_verif.append(y1)
while u < 100:
print("a4")
print(x_verif, y_verif, x1, y1)
while i < len(x_verif):
x1 = random.randint(-850, 850)
y1 = random.randint(-380, 380)
print(x1, y1)
if x1 not in x_verif and (x1 > x_verif[i]+91 or x1 < x_verif[i]-91):
if y1 not in y_verif and (y1 > y_verif[i]+142 or y1 < y_verif[i]-142):
collision = False
else:
collision = True
if collision == False:
t.penup()
t.hideturtle()
t.setx(x1)
t.sety(y1)
t.pendown()
house()
x_verif.append(x1)
y_verif.append(y1)
count += 1
i+= 1
u += 1
scatter()
对于丑陋的代码及其背后的简单性，我们深表歉意。我很乐意为此使用列表理解，但我不知道我的逻辑目前在哪里失败。这就像我的第 100 次尝试，从这个版本开始，它只绘制了最初的房子，我认为它会在某个地方无限循环....
我的问题在于为每个新值遍历整个列表。我是否需要每次都循环遍历它们，还是可以使用一些 IF 条件？编辑：它不断循环遍历随机值，但其中 none 被我正在使用的两个 IF 语句接受。
附带说明：使用我当前的代码，它们每次都会更改绘图方向...不知道为什么会这样...
编辑：我非常感谢所有的解决方案！我在问题开头的笔记上苦苦挣扎。它说与第一行相比，最后一行只需要多几行......他们在开玩笑吗？
Defo 不是最好的方法，但是
import turtle
import time
import random
t = turtle.Turtle()
turtle.screensize(1920,1000)
x_verif = []
y_verif = []
t.speed(0)
collision = None
def square():
for s in range(0, 4):
t.forward(90)
t.left(90)
def triangle():
for s in range(0, 2):
t.left(-60)
t.forward(52)
def house():
square()
t.left(90)
t.forward(90)
triangle()
t.left(30) #returning to 90 degrres
def scatter():
beenAt = [] #this will hold every place that there is a house
for i in range(100):
t.penup()
loop = True
while loop == True:
area = random.randint(-850, 850)
for i in range(91): #looping for the size of the house
if area+i in beenAt: #if the number chosen plus i is in beenAt stop because we cant use that place
break
if i == 90: #if at the finial part of our loop then draw house
t.goto(area, 0)
t.pendown()
for i in range(area, area + 91):
beenAt.append(i) #add to been at list every place we have drawn
house()
loop = False
scatter()
事实证明这是一个比我从描述中假设的更棘手的问题。我的方法是将房子作为两个多边形、一个正方形和一个三角形来处理和存储。我随机测试绘制（画笔）一个房子并比较其多边形中的所有点以查看它们是否在现有房屋多边形内，反之亦然。如果没有重叠，就真的画房子。该解决方案 不 有效，但与简单的基于直径的方法相比，它允许紧密包装房屋。
point in triangle routine is based on one from GeeksForGeeks.org
我的代码中有一个小问题需要完善。但总的来说似乎达到了objective:
from turtle import Screen, Turtle
from random import randint
HOUSES = 100
HOUSE_SIZE = 90
WINDOW_WIDTH, WINDOW_HEIGHT = 1920, 1000
# assumes roof is an isosceles triangle
ROOF_SIDE = HOUSE_SIZE * 3**0.5 / 3
ROOF_HEIGHT = ROOF_SIDE // 2
FONT_SIZE = HOUSE_SIZE // 3
FONT = ('Arial', FONT_SIZE, 'normal')
def square(turtle, identity=None):
turtle.begin_poly()
for _ in range(3):
turtle.forward(HOUSE_SIZE)
turtle.right(90)
turtle.end_poly()
turtle.forward(HOUSE_SIZE/2 - FONT_SIZE/2) # visually finish square
if identity: # label each house with a number
turtle.penup()
turtle.right(90)
turtle.forward(HOUSE_SIZE/2)
turtle.write(identity, align='center', font=FONT)
turtle.backward(HOUSE_SIZE/2)
turtle.left(90)
turtle.pendown()
turtle.forward(HOUSE_SIZE/2 + FONT_SIZE/2) # visually finish square
turtle.right(90) # return to original orientation
return turtle.get_poly()
def triangle(turtle):
turtle.begin_poly()
turtle.forward(HOUSE_SIZE)
turtle.left(150)
turtle.forward(ROOF_SIDE)
turtle.end_poly()
turtle.left(60)
turtle.forward(ROOF_SIDE) # visually finish triangle
turtle.right(210) # return to original orientation
return turtle.get_poly()
def house(turtle, identity=None):
return (square(turtle, identity), triangle(turtle))
def area_of_triangle(p1, p2, p3):
x1, y1 = p1
x2, y2 = p2
x3, y3 = p3
return abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2))) // 2
def is_inside_triangle(point, triangle):
p1, p2, p3 = triangle
a = area_of_triangle(p1, p2, p3)
b = area_of_triangle(point, p2, p3)
c = area_of_triangle(p1, point, p3)
d = area_of_triangle(p1, p2, point)
return abs(a - (b + c + d)) < 5 # 5 == fudge factor, sigh
def is_inside_square(point, square):
x, y = point
p1, p2, p3, p4 = square
_, y1 = p1
x2, _ = p2
_, y3 = p3
x4, _ = p4
return x4 <= x <= x2 and y3 <= y <= y1
def scatter(turtle):
houses = []
count = 0
while count < HOUSES:
x = randint(-WINDOW_WIDTH/2, WINDOW_WIDTH/2 - HOUSE_SIZE)
y = randint(HOUSE_SIZE - WINDOW_HEIGHT/2, WINDOW_HEIGHT/2 - ROOF_HEIGHT)
turtle.penup()
turtle.goto(x, y)
proposed_square, proposed_triangle = house(turtle) # test draw invisible house
turtle.pendown()
collision = False
for point in proposed_square + proposed_triangle: # does proposed house collide with houses?
for square, triangle in houses:
if is_inside_square(point, square) or is_inside_triangle(point, triangle):
collision = True
break
if collision:
break
for square, triangle in houses: # do houses collide with proposed house?
for point in square + triangle:
if is_inside_square(point, proposed_square) or is_inside_triangle(point, proposed_triangle):
collision = True
break
if collision:
break
if not collision:
count += 1
houses.append(house(turtle, identity=count)) # actually draw new house
print(count)
screen = Screen()
screen.screensize(WINDOW_WIDTH, WINDOW_HEIGHT)
screen.tracer(False)
turtle = Turtle()
turtle.hideturtle()
scatter(turtle)
screen.tracer(True)
screen.exitonclick()
由于房屋朝向一致，这个问题在一定程度上得到了简化。如果房子是随机朝向的，罗盘方向，方形重叠计算会更复杂。
可以通过三角形与三角形重叠、方形与三角形重叠等测试而不是简单地 "point inside" 来提高解决方案的效率。我们还可以将碰撞逻辑下推到 square() 和 triangle() 例程中，以便在发生碰撞时立即抛出错误，而不是先完成房屋然后再进行测试。
鉴于屏幕区域的大小、房屋的大小、房屋的数量以及随机散布，我相信程序的个人 运行 可能会在尝试放置时停滞不前可能没有的房子 space:
这是一个我必须解决的问题，但在过去的 5 天里我一直在用头撞墙。一定有一些非常简单的东西我错过了，或者误解了，因为逻辑在我脑海中似乎 100% 正确，但它就是行不通。
我需要画 "scattered" 个不重叠的房子，共 100 个。 我必须使用 turtle 来绘制它们，所以我有 X 和 Y 坐标。 X 和 Y 列表用于验证目的，看看房子是否已经在那个地方。
我正在做的是在随机坐标上绘制一个 "house"（顶部有一个三角形的正方形）， 我在房屋数量少于 100 时循环。 在每个循环中，我随机化 x 和 y 坐标，从那里我开始用乌龟绘制每个房子。 我检查该值是否已经在 X 和 Y 验证列表中，以及我的新 X 和 Y 是否为 +/- 房子的大小（将其视为正方形）
import turtle
import time
import random
t = turtle.Turtle()
turtle.screensize(1920,1000)
x_verif = []
y_verif = []
t.speed(0)
collision = None
def square():
for s in range(0, 4):
t.forward(90)
t.left(90)
def triangle():
for s in range(0, 2):
t.left(-60)
t.forward(52)
def house():
square()
t.left(90)
t.forward(90)
triangle()
def scatter():
print("a")
house()
x1 = random.randint(-850, 850)
y1 = random.randint(-380, 380)
count = 0
while count < 100:
print("a2")
i = 0
u = 0
collision = False
for tries in range (0, 2):
print("a3")
x_verif.append(x1)
y_verif.append(y1)
while u < 100:
print("a4")
print(x_verif, y_verif, x1, y1)
while i < len(x_verif):
x1 = random.randint(-850, 850)
y1 = random.randint(-380, 380)
print(x1, y1)
if x1 not in x_verif and (x1 > x_verif[i]+91 or x1 < x_verif[i]-91):
if y1 not in y_verif and (y1 > y_verif[i]+142 or y1 < y_verif[i]-142):
collision = False
else:
collision = True
if collision == False:
t.penup()
t.hideturtle()
t.setx(x1)
t.sety(y1)
t.pendown()
house()
x_verif.append(x1)
y_verif.append(y1)
count += 1
i+= 1
u += 1
scatter()
对于丑陋的代码及其背后的简单性，我们深表歉意。我很乐意为此使用列表理解，但我不知道我的逻辑目前在哪里失败。这就像我的第 100 次尝试，从这个版本开始，它只绘制了最初的房子，我认为它会在某个地方无限循环....
我的问题在于为每个新值遍历整个列表。我是否需要每次都循环遍历它们，还是可以使用一些 IF 条件？编辑：它不断循环遍历随机值，但其中 none 被我正在使用的两个 IF 语句接受。
附带说明：使用我当前的代码，它们每次都会更改绘图方向...不知道为什么会这样...
编辑：我非常感谢所有的解决方案！我在问题开头的笔记上苦苦挣扎。它说与第一行相比，最后一行只需要多几行......他们在开玩笑吗？
Defo 不是最好的方法，但是
import turtle
import time
import random
t = turtle.Turtle()
turtle.screensize(1920,1000)
x_verif = []
y_verif = []
t.speed(0)
collision = None
def square():
for s in range(0, 4):
t.forward(90)
t.left(90)
def triangle():
for s in range(0, 2):
t.left(-60)
t.forward(52)
def house():
square()
t.left(90)
t.forward(90)
triangle()
t.left(30) #returning to 90 degrres
def scatter():
beenAt = [] #this will hold every place that there is a house
for i in range(100):
t.penup()
loop = True
while loop == True:
area = random.randint(-850, 850)
for i in range(91): #looping for the size of the house
if area+i in beenAt: #if the number chosen plus i is in beenAt stop because we cant use that place
break
if i == 90: #if at the finial part of our loop then draw house
t.goto(area, 0)
t.pendown()
for i in range(area, area + 91):
beenAt.append(i) #add to been at list every place we have drawn
house()
loop = False
scatter()
事实证明这是一个比我从描述中假设的更棘手的问题。我的方法是将房子作为两个多边形、一个正方形和一个三角形来处理和存储。我随机测试绘制（画笔）一个房子并比较其多边形中的所有点以查看它们是否在现有房屋多边形内，反之亦然。如果没有重叠，就真的画房子。该解决方案 不 有效，但与简单的基于直径的方法相比，它允许紧密包装房屋。
point in triangle routine is based on one from GeeksForGeeks.org
我的代码中有一个小问题需要完善。但总的来说似乎达到了objective:
from turtle import Screen, Turtle
from random import randint
HOUSES = 100
HOUSE_SIZE = 90
WINDOW_WIDTH, WINDOW_HEIGHT = 1920, 1000
# assumes roof is an isosceles triangle
ROOF_SIDE = HOUSE_SIZE * 3**0.5 / 3
ROOF_HEIGHT = ROOF_SIDE // 2
FONT_SIZE = HOUSE_SIZE // 3
FONT = ('Arial', FONT_SIZE, 'normal')
def square(turtle, identity=None):
turtle.begin_poly()
for _ in range(3):
turtle.forward(HOUSE_SIZE)
turtle.right(90)
turtle.end_poly()
turtle.forward(HOUSE_SIZE/2 - FONT_SIZE/2) # visually finish square
if identity: # label each house with a number
turtle.penup()
turtle.right(90)
turtle.forward(HOUSE_SIZE/2)
turtle.write(identity, align='center', font=FONT)
turtle.backward(HOUSE_SIZE/2)
turtle.left(90)
turtle.pendown()
turtle.forward(HOUSE_SIZE/2 + FONT_SIZE/2) # visually finish square
turtle.right(90) # return to original orientation
return turtle.get_poly()
def triangle(turtle):
turtle.begin_poly()
turtle.forward(HOUSE_SIZE)
turtle.left(150)
turtle.forward(ROOF_SIDE)
turtle.end_poly()
turtle.left(60)
turtle.forward(ROOF_SIDE) # visually finish triangle
turtle.right(210) # return to original orientation
return turtle.get_poly()
def house(turtle, identity=None):
return (square(turtle, identity), triangle(turtle))
def area_of_triangle(p1, p2, p3):
x1, y1 = p1
x2, y2 = p2
x3, y3 = p3
return abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2))) // 2
def is_inside_triangle(point, triangle):
p1, p2, p3 = triangle
a = area_of_triangle(p1, p2, p3)
b = area_of_triangle(point, p2, p3)
c = area_of_triangle(p1, point, p3)
d = area_of_triangle(p1, p2, point)
return abs(a - (b + c + d)) < 5 # 5 == fudge factor, sigh
def is_inside_square(point, square):
x, y = point
p1, p2, p3, p4 = square
_, y1 = p1
x2, _ = p2
_, y3 = p3
x4, _ = p4
return x4 <= x <= x2 and y3 <= y <= y1
def scatter(turtle):
houses = []
count = 0
while count < HOUSES:
x = randint(-WINDOW_WIDTH/2, WINDOW_WIDTH/2 - HOUSE_SIZE)
y = randint(HOUSE_SIZE - WINDOW_HEIGHT/2, WINDOW_HEIGHT/2 - ROOF_HEIGHT)
turtle.penup()
turtle.goto(x, y)
proposed_square, proposed_triangle = house(turtle) # test draw invisible house
turtle.pendown()
collision = False
for point in proposed_square + proposed_triangle: # does proposed house collide with houses?
for square, triangle in houses:
if is_inside_square(point, square) or is_inside_triangle(point, triangle):
collision = True
break
if collision:
break
for square, triangle in houses: # do houses collide with proposed house?
for point in square + triangle:
if is_inside_square(point, proposed_square) or is_inside_triangle(point, proposed_triangle):
collision = True
break
if collision:
break
if not collision:
count += 1
houses.append(house(turtle, identity=count)) # actually draw new house
print(count)
screen = Screen()
screen.screensize(WINDOW_WIDTH, WINDOW_HEIGHT)
screen.tracer(False)
turtle = Turtle()
turtle.hideturtle()
scatter(turtle)
screen.tracer(True)
screen.exitonclick()
由于房屋朝向一致，这个问题在一定程度上得到了简化。如果房子是随机朝向的，罗盘方向，方形重叠计算会更复杂。
可以通过三角形与三角形重叠、方形与三角形重叠等测试而不是简单地 "point inside" 来提高解决方案的效率。我们还可以将碰撞逻辑下推到 square() 和 triangle() 例程中，以便在发生碰撞时立即抛出错误，而不是先完成房屋然后再进行测试。
鉴于屏幕区域的大小、房屋的大小、房屋的数量以及随机散布，我相信程序的个人 运行 可能会在尝试放置时停滞不前可能没有的房子 space: