Метод (только скалярные произведения)
1. Пусть вершины идут в порядке обхода $p_1,\dots ,p_n$. Для каждой стороны вычислить вектор ребра
$$v_i=p_{i+1}-p_i,i=1,\dots ,n,p_{n+1}\equiv p_1.$$
2. На каждом верху проверить перпендикулярность соседних рёбер через скалярное произведение:
$$d_i=v_{i-1}\cdot v_i.$$ Если $d_i=0$ для всех $i$, то все углы прямые.
Практическая реализация с учётом масштаба (рекомендуемая):
проверять нормализованный косинус угла
$$c_i=\frac{d_i}{\Vert v_{i-1}\Vert \Vert v_i\Vert },$$ и требовать
$$|c_i|\le \text{tol}$$ или эквивалентно
$$|d_i|\le \text{tol}\Vert v_{i-1}\Vert \Vert v_i\Vert .$$
Выбор tol:
- Для целых координат можно проверить точно $d_i=0$ (без ошибок округления).
- Для вычислений в двойной точности рекомендую взять $\text{tol}=C\cdot u$ с машинным эпсилон $u\approx 2.22\cdot 10^{-16}$ и константой $C$ порядка $10$–$10^4$ в зависимости от надёжности данных. Практически часто используют $\text{tol}\in [10^{-12},10^{-10}]$.
Числовая устойчивость — оценка и замечания
- Скаларное произведение в двумерном случае вычисляется устойчиво (несколько операций), погрешность абсолютного значения $d_i$ ограничена по порядку величины $O(u)\Vert v_{i-1}\Vert \Vert v_i\Vert$. Поэтому нормализация на $\Vert v_{i-1}\Vert \Vert v_i\Vert$ даёт естественную шкалу ошибки.
- Главная проблема — вычитание/погрешности при очень маленьких длинах рёбер: если $\Vert v_i\Vert$ малы (вершины почти совпадают), проверка теряет смысл — следует заранее отбраковывать или нормировать такие случаи (требовать $\Vert v_i\Vert >$ порог).
- Если угол близок, но не равен $90^{\circ }$, то нельзя однозначно решить без априорной информации: погрешность порядка $\sim u$ в нормированном косинусе даёт погрешность в угле порядка $u$ радиан; для практических данных используйте более «мягкий» tol.
- Сложность алгоритма $O(n)$.
Краткая рекомендация: вычисляйте $c_i=\frac{v_{i-1}\cdot v_i}{\Vert v_{i-1}\Vert \Vert v_i\Vert }$ и требуйте $|c_i|\le 10^{-12}$ (или точное равенство для целых координат); перед этим проверьте ненулевые длины рёбер.