Условие
Студент Алёша вернулся в университет после академического отпуска. За время своего отсутствия он подтянул математику и алгоритмы, так что теперь готов идти дальше. По крайней мере, так казалось до того, когда он получил билет на экзамене.
.
Из билета: есть окружность с центром O, а также N, множество вершин многоугольника, вписанного в фигуру. Каждая вершина может быть расположена на длине окружности случайным образом. Нужно определить вероятность, что при случайном наборе N центр O будет внутри этого образованного многоугольника.
С какой стороны подойти к задаче? Стоит ли перебирать все варианты или есть более элегантное решение? Кажется, если Алёша разберется с этой задачей, злополучный семестр будет позади.
Задача
Напишите модель симуляции, например, на Python, которая будет вычислять вероятность того, что случайно сгенерированный многоугольник, вписанный в окружность, будет заключать в своей площади центр O.
Решение
Первое, что нужно принять: внутри окружности может быть бесконечно много вариаций вписанных многоугольников. И для решения задачи нам понадобится задать ограниченное, но достаточное количество симуляций для определения вероятности. Из этого следует второе, что самый эффективный подход — решить задачу экспериментальным методом, не пытаясь выводить ряды и формулы.
Общая формула вычисления вероятности наступления события A нам известна. Получается, нужно как-то идентифицировать искомое событие среди основного множества. Но как получить само множество N на длине окружности? На самом деле, это не так сложно — нужно лишь вспомнить тригонометрию.
Итак, принимаем, что в конечном счете мы работаем именно с вершинами, которые образуют многоугольники. А у каждой точки в декартовой системе координат есть свои x и y. Следовательно, нам нужно понять, как случайно генерировать координаты вершин так, чтобы они находились на длине окружности. Ответ кроется в последних двух словах.
Длина окружности — это просто отрезок, длину которого можно выразить как 2pi радиан, если радиус — единичный. Тогда если взять, например, 2pi/3, что на самом деле является углом (angle), и подставить значение в качестве аргумента для формул синуса и косинуса, мы получим координаты точки на окружности с единичным радиусом. А чтобы получить остальные вершины, нужно просто случайным образом менять значение angle.
Вот, как такое множество точек можно описать в Python:
import numpy as np
def points_on_circle(N, R=1):
angles = np.random.uniform(0, 2*np.pi, N)
x = R * np.cos(angles)
y = R * np.sin(angles)
return np.column_stack((x, y))
Отлично — теперь мы можем генерировать случайный набор вершин. Но обратите внимание, что таким образом мы генерируем вершины как простых, так и сложных многоугольников, когда его стороны могут пересекаться между собой. Ошибки здесь нет, так как в задаче явно не прописано, что многоугольник может быть только простым. Но это усложняет задачу — и сейчас вы это поймете.
Следующим шагом нужно научиться определять, собирается ли из набора вершин многоугольник, который будет содержать в своей площади центр окружности O. Если бы многоугольники были правильными, то можно было бы применить приближенное решение. Для всех правильных многоугольников при N > 3 оно сформулировано так: если есть по крайней мере четыре точки, расположенные в разных четвертях координат, то центр окружности заключен в площади образуемого многоугольника.
С этим поможет алгоритм лучей. Он сформулирован довольно просто: из заданной точки посылается воображаемый длинный луч в произвольном направлении (например, pi/4). Далее считается, сколько раз этот луч пересекает стороны многоугольника. Если число пересечений нечетное, значит точка находится внутри многоугольника, поскольку луч «проходит» через внутреннюю область и выходит наружу ровно нечетное число раз. Если же число пересечений четное, значит точка снаружи, так как луч либо не пересекает границы вообще, либо делает это парное число раз — заходя и выходя из многоугольника.
На Python этот алгоритм можно описать следующим образом:
def is_point_inside_polygon(point, polygon):
x, y = point
inside = False
n = len(polygon)
px, py = polygon[:,0], polygon[:,1]
for i in range(n):
j = (i + 1) % n
xi, yi = px[i], py[i]
xj, yj = px[j], py[j]
intersect = ((yi > y) != (yj > y)) and \
(x < (xj - xi) * (y - yi) / (yj - yi + 1e-12) + xi)
if intersect:
inside = not inside
return inside
Полный код тогда будет выглядеть так:
import numpy as np
def points_on_circle(N, R=1):
angles = np.random.uniform(0, 2*np.pi, N)
x = R * np.cos(angles)
y = R * np.sin(angles)
return np.column_stack((x, y))
def is_point_inside_polygon(point, polygon):
x, y = point
inside = False
n = len(polygon)
px, py = polygon[:,0], polygon[:,1]
for i in range(n):
j = (i + 1) % n
xi, yi = px[i], py[i]
xj, yj = px[j], py[j]
intersect = ((yi > y) != (yj > y)) and \
(x < (xj - xi) * (y - yi) / (yj - yi + 1e-12) + xi)
if intersect:
inside = not inside
return inside
def simulate_probability(N, M=10000):
success = 0
for _ in range(M):
polygon = points_on_circle(N)
if is_point_inside_polygon((0, 0), polygon):
success += 1
return success / M
N = 3 # Количество вершин
M = 10000 # Количество симуляций
probability = simulate_probability(N, M)
print(f"Вероятность, что центр внутри {N}-угольника: {probability}")
Заключение
Наш герой справился с этой интересной задачей и теперь готов покорять новые вершины. Но ничего бы не вышло, если бы он не подписался на рассылку Академии Selectel, в которой собраны актуальные материалы про IT-технологии и не только. Посмотрим, с какими еще задачами столкнется Алёша на своем пути.
