Геометрия · объяснение и практика
Как триангулировать вогнутый многоугольник последовательным отсечением ушей
Как выбирать допустимый треугольник-ухо у вогнутого контура, почему одного выпуклого угла мало и какие проверки повторяются после удаления вершины.

В теме Площади плоских фигур · Учебная карта
В маршруте Выпуклость и геометрия решётки · 10 тем
Главная мысль
Для простого многоугольника можно последовательно отсекать уши: треугольники трёх соседних вершин с выпуклой вершиной, внутренней диагональю и без других вершин контура внутри или на границе треугольника.
Проверяем треугольник, а не только поворот
Возьмём простой контур без отверстий с обходом против часовой стрелки и без трёх коллинеарных вершин. Для соседей U, V, W положительный определитель векторов UV и VW означает выпуклый угол при V. Но угол проверяет только ближайшие рёбра: далёкая вогнутая вершина может попадать внутрь треугольника UVW. Тогда отсекать его нельзя.
Допустимое ухо имеет внутреннюю диагональ UW, не пересекающую остальные рёбра, а его треугольник не содержит других вершин. Для нашей невырожденной простой фигуры выпуклость и проверка остальных вершин дают критерий выбора. Проверку диагонали полезно сохранять явно на чертеже: она объясняет, почему оставшаяся область действительно отделяется от удаляемой части.
Разбираем контур с настоящей впадиной
Зададим А(0;0), Б(6;0), В(6;5), Г(3;2), Д(0;5) в порядке обхода. Угол при Б выпуклый, однако Г лежит внутри треугольника АБВ: её координаты положительны и 2 меньше (5/6)·3. Поэтому диагональ АВ пересекает отсечённую впадиной часть области, а Б не является ухом.
Треугольник БВГ подходит: поворот при В положителен, А и Д в нём не лежат, диагональ БГ остаётся внутри контура. Его площадь равна 5·3/2=7,5. После удаления В остаётся четырёхугольник АБГД. Теперь можно отсечь АБГ площадью 6; оставшийся АГД имеет площадь 7,5. Сумма 21 совпадает с площадью исходного контура по координатам.
Пример
Почему нельзя сразу отсечь треугольник ВГД?
При Г поворот отрицателен: это вогнутая вершина. Треугольник над впадиной заполняет участок вне исходной области, поэтому не является частью её триангуляции.
После отсечения соседи меняются
Удаляют именно вершину уха из текущего циклического списка, а её соседей соединяют диагональю. Затем проверяют новые соседние тройки заново. Выпуклая вершина могла раньше не быть ухом из-за находящейся внутри точки, которая теперь удалена. Поэтому список допустимых ушей нельзя один раз составить для исходного контура и использовать без обновления.
Для простого невырожденного многоугольника такое отсечение продолжается до последнего треугольника. Подсчёт частей здесь служит контролем, но не заменяет геометрических проверок. При самопересечениях, отверстиях и коллинеарных касаниях изложенный простой критерий требует дополнения. В вычислениях близкий к нулю определитель также нельзя бездумно считать надёжным признаком строгого поворота.
От чтения к действию
А теперь — вы
Частые вопросы
Выпуклый угол всегда является вершиной уха?
Нет. Треугольник соседних вершин может содержать другую вершину контура, как треугольник АБВ в примере.
Что требуется обновить после отсечения?
Циклическое соседство и проверки ближайших кандидатов. Удалённая вершина больше не участвует в проверке заполненности треугольника.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как знак ориентированной площади отличает внутренний поворот от вогнутого
Как знак определителя соседних рёбер показывает направление поворота контура, отличить вогнутый угол от смены обхода и почему самопересечения проверяются отдельно.
Открыть темуКак внутренние и граничные узлы решётки определяют площадь
Как находить площадь простого решётчатого многоугольника по внутренним и граничным узлам, учитывать промежуточные точки сторон и проверять масштаб клеток.
Открыть тему