Геометрия · объяснение и практика

Почему НОД приращений считает узлы на решётчатом отрезке

Как НОД координатных приращений определяет число узлов на наклонном отрезке и почему при суммировании по замкнутой границе нужно брать НОД без дополнительной единицы.

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

В теме Векторы и координаты · Учебная карта

В маршруте Выпуклость и геометрия решётки · 10 тем

Главная мысль

Для разных целочисленных концов отрезка число всех его узлов равно gcd(|Δx|,|Δy|)+1. На простом замкнутом решётчатом контуре число граничных узлов равно сумме НОД по сторонам.

Сокращаем направление до примитивного шага

Пусть от A до B координаты меняются на целые Δx,Δy, не равные нулю одновременно. Обозначим g=gcd(|Δx|,|Δy|). Тогда вектор (Δx/g,Δy/g) имеет взаимно простые компоненты и представляет кратчайший целочисленный шаг вдоль этой прямой. Полный отрезок содержит ровно g таких шагов.

Почему между соседними шагами нет ещё одного узла? Если доля примитивного вектора имела бы обе целые координаты, тождество Безу для его взаимно простых компонент заставило бы эту долю быть целой. Внутри одного шага это невозможно. Поэтому узлы перечисляются как A+k(B−A)/g при целых k от нуля до g.

Количество промежутков отличается от количества точек

При g промежутках получаем g+1 точку вместе с обоими концами и g−1 строго внутреннюю точку. Для A=(−2,1), B=(7,7) приращения равны 9 и 6, НОД равен трём. Шаг (3,2) даёт узлы (−2,1),(1,3),(4,5),(7,7). Всего их четыре, внутренних два.

Горизонтальные и вертикальные стороны формула тоже охватывает: gcd(m,0)=|m|. Но совпавшие концы следует обрабатывать отдельно, потому что это одна точка, а не обычная сторона многоугольника. Случай gcd(0,0) не даёт ненулевого направления и не поддерживает деление на g.

Пример

Сколько узлов у вертикального отрезка от (3,−2) до (3,5)?

Разность высот равна семи, поэтому g=7 и вместе с концами получаем восемь узлов. Формула не требует наклонной стороны.

На замкнутой границе вершины уже соединены

Если складывать gᵢ+1 по всем сторонам многоугольника, каждая вершина посчитается дважды: как конец одной и начало соседней стороны. Вычитая число сторон, получаем B=Σgᵢ. Другая проверка считает gᵢ−1 внутренних узлов каждой стороны и добавляет все вершины один раз — ответ получается тот же.

Такой подсчёт относится к простому контуру с различными соседними вершинами. При самопересечении разные стороны могут иметь дополнительные общие узлы, и одна поправка на углы уже не устранит все повторы. Также нужно брать НОД модулей приращений: направление обхода меняет знаки координат, но число физических узлов не меняется.

От чтения к действию

А теперь — вы

Приращения координат разных концов равны 12 и 8. Сколько узлов отрезка вместе с концами?

Частые вопросы

Почему к НОД добавляют единицу?

НОД считает примитивные промежутки между соседними узлами; у конечной цепочки точек на одну больше, чем промежутков.

Почему на многоугольнике эта единица исчезает?

Добавленные единицы дали бы повторный счёт каждой вершины; после его устранения остаётся сумма самих НОД.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться