Алгоритмы и структуры данных 9. Элементарная геометрия. Триангуляция

• Лекция посвящена элементарной геометрии.  

• В конце будет рассмотрена триангуляция.  

• Освежение знаний по скалярным и векторным произведениям, расстоянию от точки до прямой.  

• Живем в плоскости, точки и векторы задаются координатами x, y.  

• Вектор можно воспринимать как точку и наоборот.  

• Структура для хранения точек и векторов с двумя полями.  

• Операторы плюс, минус, умножение на константу.  

• Разность точек позволяет получать вектор из одной точки в другую.  

• Умножение на константу откладывает вектор в одном направлении.  

• Прямая задается уравнением x + y + c = 0.  

• Обобщенный вид уравнения позволяет хранить любые прямые.  

• Избегание тригонометрических преобразований для точности.  

• Прямая задается двумя точками p и q.  

• Уравнение прямой остается неизменным при умножении на константу.  

• Проверка, что точки p и q лежат на заданной прямой.  

• Все координаты остаются целочисленными для точности.  

• Возможность деления координат на константу для единичного направляющего вектора.  

• Прямая имеет два основных вектора: направляющий и нормальный.  

• Направляющий вектор коллинеарен прямой, а нормальный вектор перпендикулярен ей.  

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

• Для единичного вектора нормального или направляющего нужно нормировать его координаты.  

• Деление координат на корень из суммы квадратов делает вектор единичным.  

• Для прямых с единичными векторами нужно поддерживать, чтобы сумма квадратов коэффициентов уравнения была равна единице.  

• Для нахождения расстояния и проекции точки на прямую нужно опустить перпендикуляр.  

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

• Расстояние равно длине проекции, а проекция равна сумме координат точки и вектора нормали.  

• Проекция точки на прямую равна сумме координат точки и вектора нормали, умноженного на коэффициент.  

• Если вектор нормали единичный, то коэффициент равен единице.  

• Проекция точки на прямую позволяет найти точку, удовлетворяющую уравнению прямой.  

• Рассматривается пересечение двух прямых: a1x + b1y + c1 = 0 и a2x + b2y + c2 = 0.  

• Система линейных уравнений решается методом Крамера.  

• Вводится понятие определителя и его значение для нахождения точки пересечения.  

• Определяется определитель исходной матрицы 2x2.  

• Подставляются столбцы свободных членов вместо каждого столбца исходной матрицы.  

• Точка пересечения определяется как частное определителей.  

• Псевдовекторное произведение нормальных направляющих векторов.  

• Определяется как ориентированная площадь параллелограмма, натянутого на два вектора.  

• Если определитель равен нулю, векторы коллинеарны или противонаправлены.  

• Координаты могут быть рациональными, что требует точного хранения и сравнения.  

• Использование класса для хранения числителя и знаменателя для точных вычислений.  

• Проверка точности с погрешностью эпсилон.  

• Рассматриваются различные способы решения задачи.  

• Избежание использования тригонометрических функций для повышения точности.  

• Важность минимизации операций с корнями и тригонометрическими функциями.  

• Выражение икс из первого уравнения и решение квадратного уравнения для игрек.  

• Если а не ноль, то выражение икс и игрек.  

• Если а ноль, то выражение игрек и подстановка в уравнение.  

• Проекция центра на прямую и проверка расстояния от центра до прямой.  

• Если расстояние больше радиуса, решений нет.  

• Если расстояние равно радиусу, решение одно.  

• Если расстояние меньше радиуса, решений два.  

• Знание точки п и направляющего вектора прямой.  

• Расстояние от центра до прямой как катет в прямоугольном треугольнике.  

• Определение двух точек пересечения как п плюс-минус направляющий вектор.  

• Уравнения первой и второй окружностей.  

• Выражение икс из одного уравнения и подстановка в другое.  

• Вычитание уравнений для получения уравнения прямой.  

• Вычитание уравнений для упрощения.  

• Уравнение прямой как радикальная ось.  

• Пересечение окружности с прямой для нахождения точек пересечения.  

• Множество решений не меняется, задача остается той же.  

• Если коэффициенты при a и b равны нулю, система либо не имеет решений, либо любая точка подходит.  

• Если a и b равны нулю, это приводит к кривой прямой.  

• Если центры окружностей совпадают, это либо концентрические окружности с разными радиусами, либо одна и та же окружность.  

• Решение: все точки на одной окружности.  

• Скалярное произведение двух векторов можно вычислить через координаты или через длины и угол между векторами.  

• Знак скалярного произведения указывает на угол между векторами: острый, прямой или тупой.  

• Векторное произведение двух векторов a и b равно площади ориентированного параллелограмма.  

• Площадь параллелограмма зависит от угла между векторами и может быть положительной или отрицательной.  

• Векторное произведение помогает определить направление кратчайшего поворота между векторами.  

• Вращение против часовой стрелки: синус фи положителен, если синус фи равен нулю, векторы коллинеарны.  

• Вращение по часовой стрелке: синус фи меньше нуля.  

• Знак выражения позволяет определить направление кратчайшего поворота.  

• Триангуляция разбивает многоугольник на треугольники с помощью диагоналей.  

• Диагональ - это отрезок между не соседними вершинами, целиком лежащий внутри многоугольника.  

• Задача: найти триангуляцию многоугольника для его освещения или охраны.  

• Диагональ многоугольника соединяет две не соседние вершины и лежит внутри многоугольника.  

• Примеры плохих диагоналей: лежащие вне многоугольника или частично лежащие внутри.  

• Определение триангуляции: покрытие многоугольника непересекающимися треугольниками со сторонами, являющимися сторонами или диагоналями многоугольника.  

• Многоугольник задается перечислением своих вершин в порядке обхода.  

• Треугольник между двумя соседними вершинами называется ухом, если его можно безопасно отрезать.  

• Ухо - это треугольник, внутри и на границе которого нет других вершин.  

• Ухо можно безопасно отрезать для упрощения задачи.  

• Пример: три последовательные вершины образуют ухо, которое можно исключить из многоугольника.  

• В любом многоугольнике есть хотя бы одно ухо.  

• Алгоритм триангуляции: найти ухо, отрезать его, затем снова найти ухо и так далее.  

• Доказательство: индукция по числу вершин в многоугольнике.  

• В многоугольнике есть хотя бы одна вершина с углом меньше 180 градусов.  

• Сумма углов многоугольника равна пи на минус два.  

• Углы при вершинах измеряются между соседними сторонами.  

• Если треугольник не является ухом, внутри него могут быть другие вершины.  

• Ломаная периметра простого многоугольника не самопересекается.  

• Проблемы могут возникнуть только с диагоналями.  

• Среди всех вершин внутри треугольника выбирается самая далекая от прямой.  

• Отрезок между выбранной точкой и вершиной является диагональю.  

• Диагональ не пересекает стороны многоугольника и лежит внутри него.  

• По эту сторону от прямой нет других вершин многоугольника.  

• Если бы было пересечение со стороной, один из концов этой стороны лежал бы в полуплоскости.  

• Отрезок не может пересекаться с другой стороной, так как это приведет к противоречию.  

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

• Каждая часть является корректным многоугольником с меньшим числом вершин.  

• По предположению индукции, в каждой части есть ухо.  

• Утверждение переформулировано: всегда есть хотя бы два уха, не пересекающиеся по внутренностям.  

• База остается прежней: в треугольнике есть одно ухо.  

• Доказано существование диагоналей и ушей в каждой части.  

• Если обе части являются треугольниками, то они являются ушами.  

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

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

• Алгоритм работает за линейное время и находит выпуклую вершину.  

• Если треугольник не является ухом, то находится диагональ и запускается рекурсивно.  

• В следующий раз будет показано, как завершить алгоритм.