Геометрия
Координатная геометрия
Ray casting в игровых движках, рейтрейсинг в графике, nearest-neighbor в k-d tree-всё это операции с прямыми и расстояниями в координатной геометрии.
- **Ray casting:** параметрическое уравнение луча + пересечение с примитивами сцены
- **LeetCode:** задачи на прямые, коллинеарность точек, пересечение отрезков
- **Computer Graphics:** кривые Безье = параболы, NURBS = рациональные кривые
- **GPS:** гиперболическая триангуляция-разность расстояний до станций
Предварительные знания
Расстояние и середина отрезка
Система координат позволяет выразить геометрические объекты через алгебраические уравнения. Расстояние между точками-основной примитив вычислительной геометрии.
**Расстояние:** d(P₁, P₂) = √((x₂−x₁)² + (y₂−y₁)²) **Середина отрезка:** M = ((x₁+x₂)/2, (y₁+y₂)/2) **Деление в отношении λ:μ:** P = (μx₁+λx₂)/(λ+μ), (μy₁+λy₂)/(λ+μ)
Расстояние между точками A(1, 2) и B(4, 6) равно:
Уравнения прямых
Прямая в 2D имеет несколько форм записи. Для вычислительных задач удобна общая форма, для визуализации-наклонно-точечная.
| Форма | Уравнение | Когда удобна |
|---|---|---|
| Наклонно-точечная | y − y₀ = k(x − x₀) | Известны точка и наклон |
| Наклонно-отрезочная | y = kx + b | График, пересечение с осями |
| Общая | ax + by + c = 0 | Расстояние от точки, intersection |
| Параметрическая | (x,y) = P + t·d | Ray casting, отрезки |
Прямая проходит через A(0, 3) и B(2, 7). Каково уравнение прямой в форме y = kx + b?
Расстояние от точки до прямой
Расстояние от точки до прямой-это длина перпендикуляра из точки на прямую. Формула напрямую использует общую форму уравнения прямой.
**Расстояние от точки (x₀, y₀) до прямой ax + by + c = 0:** d = |ax₀ + by₀ + c| / √(a² + b²) Знак (без модуля) определяет, с какой стороны прямой находится точка-ключевое для half-plane тестов.
Half-plane test (знак ax₀+by₀+c)-базовый примитив в Graham scan и проверке выпуклости полигона.
Расстояние от точки (3, 4) до прямой 3x + 4y − 10 = 0 равно:
Конические сечения
Конические сечения-параболы, эллипсы, гиперболы-получаются при пересечении конуса плоскостью. В компьютерной графике они используются как кривые второго порядка.
| Кривая | Каноническое уравнение | Применение |
|---|---|---|
| Парабола | y = ax² + bx + c | Траектория снаряда, кривая Безье 2-го порядка |
| Эллипс | x²/a² + y²/b² = 1 | Орбиты планет, LOD в 3D |
| Гипербола | x²/a² − y²/b² = 1 | GPS триангуляция, акустическая локализация |
| Окружность | x² + y² = r² | Частный случай эллипса при a = b = r |
Какое из уравнений описывает эллипс?
Ключевые идеи
- **Расстояние:** √((x₂−x₁)²+(y₂−y₁)²)-используй d² для сравнений без sqrt
- **Прямая ax+by+c=0:** расстояние от точки = |ax₀+by₀+c|/√(a²+b²)
- **Half-plane test:** знак (ax₀+by₀+c)-по какую сторону прямой точка
- **Конические сечения:** парабола/эллипс/гипербола-кривые второго порядка в CS
Связанные темы
Координатная геометрия-фундамент для преобразований и вычислительной геометрии:
- Геометрические преобразования — Матрицы преобразований действуют на координаты точек
- Векторная геометрия — Векторное произведение = half-plane test = ориентация
- Геометрия в CS — Все примитивы (CCW, intersection)-координатная геометрия
Вопросы для размышления
- Почему для LeetCode задач выгоднее хранить прямую в форме ax+by+c=0, а не y=kx+b?
- Как свести задачу "найти ближайшую точку на отрезке" к расстоянию от точки до прямой?
- Что общего у кривых Безье 2-го порядка и траектории мяча под действием гравитации?