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

Как знак ориентированной площади отличает внутренний поворот от вогнутого

Как знак определителя соседних рёбер показывает направление поворота контура, отличить вогнутый угол от смены обхода и почему самопересечения проверяются отдельно.

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

В теме Выпуклость и геометрические оценки · Учебная карта

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

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

Для простого многоугольника одинаковые знаки ненулевых поворотов соответствуют выпуклому обходу. Определитель соседних рёбер даёт знак поворота, но без проверки простоты одного этого теста недостаточно.

Три последовательные точки задают локальный поворот

Для точек A,B,C вычислим векторы u=B−A, v=C−B и число D=uₓvᵧ−uᵧvₓ. В стандартной ориентации координат D>0 означает левый поворот, D<0 — правый. При D=0 точки коллинеарны, поэтому строгого поворота нет. Этот определитель равен удвоенной ориентированной площади тройки.

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

Вогнутая вершина меняет знак относительно соседей

Рассмотрим простой пятиугольник (0,0),(4,0),(4,3),(2,1),(0,3). У первых поворотов знак положителен. Но для тройки (4,3),(2,1),(0,3) векторы равны (−2,−2) и (−2,2), определитель составляет −8. Эта вершина входит внутрь общего контура и делает многоугольник невыпуклым.

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

Пример

Что означает нулевой определитель для точек (0,0),(2,2),(5,5)?

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

Локальный тест требует простого контура

У звёздчатого самопересекающегося обхода все повороты могут иметь одинаковый знак, хотя он не ограничивает выпуклую область обычным простым многоугольником. Поэтому перед применением критерия проверяют отсутствие пересечений несоседних сторон и повторных участков. Иначе локальная информация будет ошибочно выдана за глобальную.

Численные почти коллинеарные данные требуют аккуратного сравнения: округление может изменить знак малого определителя. С целыми ограниченными координатами его удобно вычислять точно. Сам тест определяет направление и выпуклость при нужных условиях, но не площадь всей фигуры: сумма или произведение локальных знаков не заменяет отдельный расчёт площади.

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

А теперь — вы

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

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

Почему отрицательные повороты не всегда означают вогнутость?

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

Что проверяют отдельно от знаков?

Отсутствие самопересечений и вырожденных повторов, а также принятую обработку коллинеарных вершин.

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

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

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