Тригонометрия
Тригонометрия на собеседовании
На whiteboard-собеседовании в Google спрашивают: «Найдите, пересекаются ли два отрезка». Это 15 строк кода - если знаешь cross product. Без этого - час мучений. В игровой разработке та же задача встречается 10 000 раз за игровую сессию (collision detection). Тригонометрия в вычислительной геометрии - это не «теория», это ежедневный инструментарий senior-инженера.
- **LeetCode геометрия:** задачи Convex Hull, Point in Polygon, Segment Intersection - стандарт для FAANG и game dev интервью
- **Физический движок:** столкновение коллайдеров (Box2D, PhysX) - cross product и dot product тысячи раз за кадр
- **Навигационные алгоритмы:** A* на полигональных картах, видимость, обход препятствий - всё через геометрические предикаты
Предварительные знания
Угол между векторами, коллинеарность, пересечение
Угол θ между двумя векторами a и b находится через скалярное произведение: cos θ = (a·b)/(|a|·|b|). Это прямое следствие теоремы косинусов. Для определения знака (левый/правый поворот) нужно векторное произведение (cross product).
**Угол между векторами:** cos θ = (a·b) / (|a|·|b|) θ = arccos((a·b) / (|a|·|b|)) ∈ [0, π] **Знак поворота (2D cross product):** a × b = aₓ·bᵧ − aᵧ·bₓ a × b > 0: b левее a (против часовой) a × b < 0: b правее a (по часовой) a × b = 0: коллинеарны
Функция arccos имеет область определения [−1, 1]. При вычислении cos θ = (a·b)/(|a|·|b|) числовые ошибки могут дать значения чуть за пределами ±1. Всегда используйте np.clip(cos_theta, −1, 1) перед arccos, иначе получите NaN.
Как проверить, коллинеарны ли три точки A(0,0), B(1,2), C(3,6)?
Алгоритм намотки: точка внутри многоугольника
Классическая задача: дана точка P и многоугольник. Находится ли P внутри? Алгоритм намотки (winding number) - наиболее надёжный метод, работающий для любых (в том числе невыпуклых) многоугольников.
LeetCode задачи на геометрию (Convex Hull, Point in Polygon, Segment Intersection) - всё это комбинации трёх операций: cross product, dot product, atan2. Выучите их наизусть до собеседования.
Алгоритм ray casting даёт неверный ответ для само-пересекающегося многоугольника. Чем в таком случае лучше пользоваться?
Тождества наизусть и быстрый вывод забытых формул
На собеседовании нет времени выводить формулы с нуля. Нужно знать ключевые тождества наизусть и уметь быстро восстановить забытые из базовых принципов за 30 секунд.
| Тождество | Запомнить как | Применение |
|---|---|---|
| sin²x + cos²x = 1 | Теорема Пифагора на окружности | Нормализация, замены |
| sin(2x) = 2 sin x cos x | Двойной угол | Произведение → сумма |
| cos(2x) = cos²x − sin²x | Два варианта: 1−2sin²x или 2cos²x−1 | Упрощение степеней |
| cos²x = (1 + cos 2x)/2 | Понижение степени | Интегрирование |
| sin²x = (1 − cos 2x)/2 | Понижение степени | Интегрирование |
| sin(a±b) = sin a cos b ± cos a sin b | Перемешивание sin/cos | Разложение |
| cos(a±b) = cos a cos b ∓ sin a sin b | Перемешивание, знак меняется | Разложение |
На собеседовании нужно быстро вывести cos(a+b). Какой способ быстрее всего?
Ключевые идеи
- **Угол через dot product:** cos θ = (a·b)/(|a|·|b|); **знак поворота:** a×b = aₓbᵧ−aᵧbₓ > 0 → левый поворот
- **Коллинеарность:** AB × AC = 0; **пересечение отрезков:** точки по разные стороны прямой через знаки cross products
- **Winding number vs Ray casting:** winding number надёжен для само-пересекающихся многоугольников; ray casting проще
- **Вывод тождеств:** cos(a+b) за 30 сек через eⁱ⁽ᵃ⁺ᵇ⁾ = eⁱᵃ·eⁱᵇ; базовый набор наизусть: sin²+cos²=1, двойной угол, понижение степени
Связанные темы
Тригонометрия на собеседовании объединяет все темы курса:
- Теоремы синусов и косинусов — Формула cos θ = (a·b)/(|a|·|b|) - прямое следствие теоремы косинусов для треугольника с вершинами (0,0), A, B
- Тригонометрия в графике и сигналах — Матрицы вращения и atan2 - основа геометрических задач в игровом движке
- Формула Эйлера — Быстрый вывод тождеств через eⁱ⁽ᵃ⁺ᵇ⁾ = eⁱᵃ·eⁱᵇ - незаменимый трюк на whiteboard
Вопросы для размышления
- Объясните коллеге без формул, почему cross product ab_x*b_y − a_y*b_x определяет направление поворота. Что происходит геометрически?
- Алгоритм определения точки внутри многоугольника нужен в GPS-навигации (в каком регионе находится пользователь?). Какой алгоритм выбрать для 100 000 точек и 1 000 000 полигонов?
- Дана задача: «Проверить, выпуклый ли многоугольник». Как использовать cross product для её решения? Что геометрически означает знак cross product для каждого ребра?