Как построить симуляцию луча?

Question

[rusyska55011]

Решаю задачу №202 на Project Euler. Ищу способ реализации симуляции отражения луча. Нашел как зная координаты получить косинус угла. Если я захочу построить луч внутри треугольника, чтобы он отражался от его стен, как мне строить этот луч? Как задать направление движения?
Ниже вывел углы треугольника: {'a': 0.8944271909999159, 'b': 0.0, 'c': 0.4472135954999579}

from math import sqrt, fabs

def get_angle(a, b, c):
    ab = fabs(sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2))
    ac = fabs(sqrt((a[0] - c[0]) ** 2 + (a[1] - c[1]) ** 2))
    bc = fabs(sqrt((b[0] - c[0]) ** 2 + (b[1] - c[1]) ** 2))

    cos_a = (ab ** 2 + ac ** 2 - bc ** 2) / (2 * ab * ac)
    cos_b = (ab ** 2 + bc ** 2 - ac ** 2) / (2 * ab * bc)
    cos_c = (ac ** 2 + bc ** 2 - ab ** 2) / (2 * ac * bc)

    return {'a' : cos_a, 'b' : cos_b, 'c' : cos_c}

a = [0, 0]
b = [0, 25]
c = [12.5, 25]

print(get_angle(a, b, c))

Знаю что это можно перевести в арккосинус, а затем умножить на (180 / 3.14), тогда я получу угол в человеческих градусах. Но что с этим делать - я не знаю.

Comments

[o5a]

Учитывая, какой это сайт и постановку задачи, тут решение скорее должно быть не через синусы/косинусы, а через работу с углами, опираясь на то, что треугольник равносторонний, т.е. углы известны, и то, что при отражении угол сохраняется. А далее видимо расчет количества возможных комбинаций по комбинаторике, на что намекают приведенные примеры: 2 варианта (зеркальных) для 11 отскоков, и т.д.

[longclaps]

сынку, ну что за позор?

ab = fabs(sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2))

sqrt заведомо возвращает для неотрицательного аргумента неотрицательный результат, и fabs бессмысленнен.
почитай сюда
ab = math.hypot(a[0] - b[0], a[1] - b[1])

Answer 1

[Wataru]

Как это часто бывает в задачах на отражение света, не надо отражать луч. Представьте, что зеркало - это портал в Зазеркалье. Луч идет прямо и, проходя через зеркало, попадает в соседнюю треугольную комнату.

В этой задаче нужно представить, что вся плоскость замощена треугольниками, прямой луч выходит из одной точки до другой. Сколько сторон треугольников он пересечет - столько отрвжений и сделано.

Отражения, если вам так хочется, можно делать через вектора. Есть у вас вектор вдоль луча, и вектор вдоль зеркала и нормаль внутрь. Через скалярное произведение можно разложить вектор луча на перпендикуляр и паралледьный к зеркалу. Потом надо развернуть вектор перпендикуляр и сложить их.

Но в этой задаче это вам не поможет никак - ибо симулировать эти 100500 отражений и квантилионы возможных начальных углов никакого времени не хватит.

Comments

[rusyska55011]

Если я вас правильно понял - то нужно создать отзеркаленную копию луча. Тоже задумывался насчет такой реализиции. Однако есть проблема, что отзеркаленный луч может выйти за пределы треугольника. Возможно, тогда необходимо будет создать циклом не по-координатно "треугольную арену", а по точкам. И обрезать луч если он выйдет за ее пределы.
Действительно, это, возможно, ключ к решению задачи, однако интересно по каким формулам можно сделать трассировку.

[Wataru]

rusyska55011, Не понял ваш коммент.

Смотрите на картинку. Тут черными ограничены достижимые комнаты, а серым показана траетория луча из примера в задаче. Посчитайте сами - ровно 11 пересечений.

spoiler

Эта задача вообще не на геометрию - а на теорию чисел. Надо подсчитать сколько на этой треугольной решетке точек, обладающих определенными свойствами. Тут нужны делимость и взимопростота.

Если же вам интересно как смулировать луч с отражениями, то вам нужна базовая аналитическая геометрия и линейная алгебра. Нужно уметь задавать луч и отрезки параметрически, нужно знать вектора, смену системы координат, сколярное и векторное произведения.

Задайте ваш луч как p(t)=b+v*t, где b - начальная точка. v - вектор направления луча, t - параметр от 0 до бесконечности. Фактически, это 2 уравнения для X и Y: x(t)=..., y(t)=... Подставляете любое значение t, получаете точку на луче.

Изначально b - нижний угол комнаты. Потом вам надо найти, где этот луч пересечется с границей комнаты. Для этого пересеките его со всеми отрезками и найдите то пересечение, которое дает минимальное t. Задайте отрезки также параметрически (но там параметр q будет от 0 до 1). Приравняйте координаты x(t)=x(q), y(t)=y(q), решите систему 2 линейных уравнений относительно t и q. Проверьте, что значения параметров в нужных пределах.

Потом эта точка пересечения будет новым началом луча. Для отражения вектора v представьте, что мы поменяли систему координат на ту, где зеркало горизонально. Тогда отражение - просто поменять знак у координаты Y вектора v. Можно не вводить систему координат, а просто проецировать вектор v на сторону и ее нормаль через скалярное произведения и потом собрать вектор обратно сложив проекции.

Если s - вектор вдоль зеркала, n - нормаль к нему, то отраженный вектор v'=s*(v^s)/|s|-n*(v^n)/|n|. Тут "^" - это скалярное произведение. Еще вам надо будет понимать, если луч проходит через угол. Пусть этот угол - точка c. Тогда луч b+v*t проходит через нее, если (c-b)^v >=0, (c-b)*v = 0. Скалярное произведение вектора на угол и вектора луча - должно быть неотрицательно (значит вектора смотрят примерно в одну сторону). Векторное произведение должно быть 0 (значит вектора коллиниарны).