Это оказалось более сложной проблемой, чем я предполагал из описания. Мой подход состоял в том, чтобы рассматривать и хранить дом как два многоугольника, квадрат и треугольник. Я случайным образом проверяю, как нарисовать (нарисовать) дом и сравнить все точки в его многоугольниках, чтобы увидеть, находятся ли они внутри существующих многоугольников дома, и наоборот. Если нет совпадений, нарисуйте дом по-настоящему. Решение является не эффективным, но оно позволяет более плотную упаковку домов, чем простой подход, основанный на диаметре.
Точка в процедуре треугольника основана на одном из GeeksForGeeks.org
У меня есть один небольшой фактор помадки в моем коде, который все еще нужно исправить. Но в целом кажется, что цель достигнута:
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()
Эта проблема несколько упрощена последовательной ориентацией домов. Если бы дома были ориентированы случайным образом по компасу, расчеты квадратного перекрытия были бы более сложными.
Решение можно было бы сделать более эффективным, если бы треугольник перекрывался с треугольником, квадрат перекрывался с треугольником и т. Д. c. тесты вместо просто "указать внутрь". Мы могли бы также записать sh логи столкновений c в подпрограммы square()
и triangle()
, чтобы выдать ошибку, как только возникнет коллизия, вместо того, чтобы завершить строительство дома и затем провести тестирование.
Учитывая размер области экрана, размер дома, количество домов и случайное рассеяние, я полагаю, что для отдельного прогона программы может быть остановлено попытка разместить дом там, где может не быть свободного места :