Коротко: под «ортогональным многоугольником» обычно понимают многоугольник с поворотами, кратными $90^{\circ }$ (см. замечание о строго «все углы $90^{\circ }$» ниже). Основная координатная идея — проверять перпендикулярность соседних рёбер через скалярное произведение и/или проверять, что каждый вектор ребра получается из предыдущего поворотом на $\pm 90^{\circ }$ (дискретные повороты). Далее — алгоритмы, обоснование и рекомендации по погрешностям.
Определение/замечание
- Если требовать, чтобы все внутренние углы строго равнялись $90^{\circ }$, то из формулы суммы углов $180(n-2)=90n$ следует $n=4$ — т.е. единственные такие простые многоугольники — прямоугольники. В большинстве практических задач под «ортогональным» подразумевают, что каждый поворот между соседними рёбрами равен $\pm 90^{\circ }$ (т.е. рёбра имеют только две взаимно перпендикулярные направления); далее я использую это понятие.
Вход: упорядоченный замкнутый список вершин $p_1,\dots ,p_n$ (считаем $p_{n+1}=p_1$). Вектора рёбер $v_i=p_{i+1}-p_i$.
Алгоритм A — простая координатная проверка (скалярные произведения)
1. Предобработка: удалить повторяющиеся подряд вершины; если после этого какие‑то $v_i=(0,0)$ — либо удалить, либо считать некорректным вводом.
2. Для каждого i вычислить вектор $v_i$ и длины $\Vert v_i\Vert$.
3. Для каждого i проверить перпендикулярность соседних рёбер:
проверить условие
$$|v_i\cdot v_{i+1}|\le \epsilon \Vert v_i\Vert \Vert v_{i+1}\Vert$$ где $v_i\cdot v_{i+1}=x_i{x}_{i+1}+y_i{y}_{i+1}$.
4. Дополнительно можно проверить замкнутость
∥∑i=1nvi∥≤εpos \Big\|\sum_{i=1}^n v_i\Big\|\le\varepsilon_{\text{pos}}
i=1∑n vi ≤εpos (обычно натурально выполняется, если вход корректный).
5. Если все проверки пройдены — многоугольник ортогонален (в смысле поворотов $\pm 90^{\circ }$).
Обоснование: для двух векторов перпендикулярность эквивалентна $v_i\cdot v_{i+1}=0$. Т.к. последовательность перпендикулярностей гарантирует, что направления ребёр получаются поворотом на $\pm 90^{\circ }$ от предыдущего, все рёбра лежат в двух взаимно перпендикулярных направлениях.
Алгоритм B — проверка целых поворотов (дискретная проверка поворота на $\pm 90^{\circ }$)
1. Как выше найти $v_i$.
2. Для каждого i можно вычислить ориентированный «поворот‑коэффициент» через скаляр и псевдоскаляр (в 2D псевдоскаляр = детерминант):
$$a_i=v_i\cdot v_{i+1},b_i=v_i\times v_{i+1}=x_i{y}_{i+1}-y_i{x}_{i+1}.$$ 3. Нормализовать: положим
$$r_i=\frac{a_i+i{b}_i}{\Vert v_i\Vert \Vert v_{i+1}\Vert }.$$ В точном случае перпендикулярного поворота $r_i\in \{i,-i\}$. Проверяем дистанцию до этих значений:
$$\min (|\Re r_i|,||\Im r_i|-1|)\le \epsilon .$$ или проще: требуем $|a_i|\le \epsilon \Vert v_i\Vert \Vert v_{i+1}\Vert$ и $|b_i|$ не чрезмерно мал (чтобы исключить вырожденность).
4. Также можно фиксировать знак поворота по знаку $b_i$ (лeво/право).
Преимущество этого подхода — явная дискретизация поворота; удобно для последующей логики (счёт лево/право, связность).
Специальный случай при целых координатах
- Если вершины имеют целые координаты, то все выражения $v_i\cdot v_{i+1}$ и $v_i\times v_{i+1}$ целы; перпендикулярность проверяется точно условием
$$v_i\cdot v_{i+1}=0.$$ Это устраняет проблемы с округлением — используйте целочисленные 64‑/128‑бит операции или bigint при необходимости.
Обработка вырожденных/нежелательных случаев
- Последовательные коллинеарные рёбра дают внутренний угол $180^{\circ }$ — их надо либо считать некорректными, либо соединять в одно ребро.
- Если нужно, чтобы все внутренние углы были ровно $90^{\circ }$ (а не $270^{\circ }$), дополнительно проверяйте ориентацию внутреннего угла: для простого многоугольника вычислите ориентацию полигона (сумма поворотов) и используйте знак детерминанта, чтобы отличать выпуклые/вогнутые углы.
Погрешности численных реализаций — рекомендации
- Использовать относительную нормированную погрешность. Вместо $|v_i\cdot v_{i+1}|\le \delta$ применять
$$|v_i\cdot v_{i+1}|\le \epsilon \Vert v_i\Vert \Vert v_{i+1}\Vert .$$ Для double обычно берут $\epsilon$ в диапазоне от $10^{-12}$ до $10^{-8}$ в зависимости от расстояний/масштаба данных; можно выбрать
$$\epsilon =C\cdot {\text{eps}}_{\text{mach}}\cdot S^2,$$ где $S={\max }_i\Vert v_i\Vert$ и $C$ — небольшая константа (например $10^2$).
- Лучше нормализовать: проверять $|\cos \theta |\le \epsilon$ с $\cos \theta =\frac{v_i\cdot v_{i+1}}{\Vert v_i\Vert \Vert v_{i+1}\Vert }$.
- Если вход результат цифровой обработки (сканирование, округление), целесообразно сначала «привести к сетке»: поворачивать/сдвигать/округлять углы к ближайшим кратным $90^{\circ }$ при условии, что отклонение мало.
- Для точного результата при рациональных/целых координатах — использовать точную арифметику (целочисленные или рациональные, bigint), или использовать одностороннюю проверку через модульные/целочисленные операции.
- При работе с очень «плохими» данными (малые длины рёбер, близкие к 0) удалить или объединить мелкие ребра, т.к. относительная погрешность там растёт.
Сложность
- О(n) по времени и памяти: один проход по рёбрам вычисляет нужные скалярные и псевдоскалярные произведения.
Краткая сводка (практическая реализация)
- Удалить дубликаты и нулевые вектора.
- Для i=1..n вычислить $v_i$, проверить $\Vert v_i\Vert >0$.
- Проверить для всех i условие перпендикулярности
$$|v_i\cdot v_{i+1}|\le \epsilon \Vert v_i\Vert \Vert v_{i+1}\Vert .$$ - При целых входных координатах — проверка точная: $v_i\cdot v_{i+1}=0$.
- При обнаружении нарушения — не ортогонален; иначе — ортогонален (в смысле поворотов $\pm 90^{\circ }$).
Если нужно, могу прислать компактный пример кода (C++/Python) с указаниями выбора $\epsilon$.