Конспект: повороты, пересечения и многоугольники

Понятия

Векторное произведение на плоскости - u × v = ux · vy − uy · vx: ориентированная площадь параллелограмма на u и v. Плюс - от u к v поворот против часовой стрелки, минус - по часовой.

Поворот трёх точек - (B − A) × (C − A): плюс - C слева от A → B, минус - справа, ноль - на прямой. Модуль - удвоенная площадь треугольника.

Предикат - операция с дискретным ответом, от которой зависит ветвление: сторона, пересечение, «внутри». Конструкция - новый объект: точка пересечения, расстояние, площадь.

Вырожденный случай - три точки на прямой, общий конец, вершина на уровне луча. Общее положение - допущение учебника, что их нет; реальные данные его не выполняют.

Формула Пика - для многоугольника с вершинами в целых точках S = I + B/2 − 1.

Что унести

ПОВОРОТ
povorot(a, b, c) = (b.x − a.x)(c.y − a.y) − (b.y − a.y)(c.x − a.x)
  > 0 налево      < 0 направо      = 0 на прямой
  |povorot| / 2       площадь треугольника
  |povorot| / |AB|    расстояние от C до прямой AB
  меняет знак при перестановке любых двух точек
  экран (ось y вниз): плюс выглядит как поворот по часовой

ПЕРЕСЕЧЕНИЕ ОТРЕЗКОВ AB и CD
d1 = povorot(C, D, A)   d2 = povorot(C, D, B)
d3 = povorot(A, B, C)   d4 = povorot(A, B, D)
крест:     d1, d2 разных знаков  И  d3, d4 разных знаков
касание:   какой-то d = 0  И  этот конец лежит на другом отрезке
           («лежит» = обе координаты между координатами концов)
наложение: все четыре = 0, и хоть один конец на другом отрезке
точка: A + t(B − A),  t = ((C − A) × (D − C)) / ((B − A) × (D − C))
       - дробь; решать по ней - только в целых (умножить на знаменатель)

МНОГОУГОЛЬНИК
2S = Σ Pᵢ × Pᵢ₊₁          плюс - обход против часовой
GeoJSON: внешний контур против часовой, Shapefile - по часовой
точка внутри: луч вправо, ребро засчитано, если
    (a.y > p.y) != (b.y > p.y)  и пересечение правее p
    нечётно - внутри; граница - отдельной проверкой
Пик: B по сторонам = Σ НОД(|dx|, |dy|)
буква Г: 2S = 36, I = 8, B = 22

ТОЧНОСТЬ
|x|, |y| <= M  →  |povorot| <= 8M²
float точен при M <= 2^25 ≈ 3,3 · 10^7,  int64 - при M < 2^30
сетка 16 × 16 у прямой y = x с шагом 2^-53: 114 неверных знаков из 256
eps не транзитивен: упрощение ломаной зависит от направления обхода
порядок: округлить к сетке один раз → дальше считать точно
CGAL: Exact_predicates_inexact_constructions_kernel; Шевчук (1996)

Ловушки джокера

Сравнил наклоны. Деление на ноль на вертикали и смена смысла при движении справа налево.

Проверил только крест. Т-образное касание, общий конец и наложение остались «без пересечения».

Проверил соседние рёбра общим тестом. Общая вершина законна - тест кричит на каждой паре соседей. А пропустить соседей нельзя: они могут сложиться по прямой назад.

Посчитал луч через вершину дважды. Нестрогие неравенства с обеих сторон.

Доверил решение float. Около прямой знак поворота - шум, и не точечный, а целыми блоками.

Заменил == 0 на abs < 1e-9. Порог не масштабируется и ломает транзитивность.

Округлил после вычислений. Вершина переехала через соседнее ребро - контур стал невалидным.

Решил, что целые - значит точные. Координаты OSM на всём земном шаре переполняют int64 в повороте: сначала вычесть опорную точку.

Проверь себя

Почему у векторного произведения именно такая формула и что значит её знак? Какие три края есть у пересечения отрезков и какой из них ловится только проверкой «конец на отрезке»? Откуда в формуле шнурка сумма по сторонам и почему от выбора начала координат ответ не зависит? Почему луч через вершину засчитывает одно ребро при правиле «вершина лежит ниже»? До какой величины координат поворот точен в float и как это посчитать? Чем предикат отличается от конструкции и почему точными должны быть именно предикаты?