Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
(1) никакие два ребра не пересекаются (за исключением, возможно, в вершинах);
(2) каждая вершина (за исключением вершин с наибольшей «/-координатой) непосредственно соединена по крайней мере с одной вершиной, имеющей большую (/-координату;
(3) каждая вершина (за исключением вершин с наименьшей «/-координатой) неиосредственно соединена по крайней мере с одной вершиной, имеющей меньшую «/-координату.
Утверждается, что каждая область планарного графа, полученная в результате применения процедуры регуляризации, является монотонным многоугольником. Доказательство этого утверждения основывается на понятии внутреннего пика. Вершина v простого многоугольника называется внутренним пиком, если внутренний угол в вершине v превышает п и обе смежные с ней вершины имеют «/-координату, не превосходящую «/-координату вершины v. Из условий (2) и (3) следует, что ни одна вершина регуляризованного графа не может быть внутренним пиком. Ключ к доказательству сделанного утверждения дает следующая лемма:
Лемма 6.3. Если Р — простой многоугольник без внутренних пиков, то Р — монотонный относительно у-оси многоугольник.
Доказательство. Пусть v\, v2, vm — последовательность вершин многоугольника Р в порядке обхода по часовой стрелке, а о] и vs — вершины с наибольшей и наименьшей «/-координатами соответственно (рис. 6.8). Если многоугольник Р не монотонный, то по крайней мере одна из двух цепей из v\ в vs, образованных ребрами многоугольника Р, не является строго убывающей по «/-координате. Рассмотрим случай, когда это — цепь, проходящая через вершину v2 (другой случай полностью симметричен данному). Выберем в качестве первой вершины на этом пути vi, 1 < i <с s, такую, что «/-координата вершины vi+i превосходит у-координату вершины
292
Гл. 6. Близость: варианты и обобщения
Для начала заметим, что последовательность из трех вершин должна образовывать правый поворот, так как иначе о, была бы внутренним пиком многоугольника Р (рис. 6.8(a)). Рассмотрим теперь прямую, проходящую через вершины v\ и vs (рис. 6.8(b)). Пусть гфы — первая точка на границе многоугольника Р, встретившаяся при движении из v, в vs по прямой, проходящей через и, и vs {г может совпадать
(а) (Ь) (с)
Рис. 6.8. (a)—vi — первая вершина в последовательности vu v2..... для
которой y(vt+\)> y(vi); (b)—г — первая точка пересечения прямой, идущей из Vi в vs, с границей многоугольника Р; (с)—вершина и, имеющая в многоугольнике Р наибольшую (/-координату, является внутренним пиком многоугольника Р.
с Vs). Отрезок, соединяющий о, и г, делит область вне многоугольника Р на две части, одна из которых представляет ограниченный многоугольник Р' (рис. 6.8(c)). Все вершины многоугольника Р', за исключением г, являются вершинами многоугольника Р. Пусть и — вершина многоугольника Р', имеющая наибольшую у-координату. Тогда и является также и вершиной многоугольника Р, и, кроме того, является внутренним пиком Р (противоречие).
Лемма 6.3 и тот факт, что ни один из многоугольников, полученных в результате регуляризации, не имеет внутренних пиков, доказывают утверждение о монотонности каждого из многоугольников. Теперь можно обратиться к вопросу триангуляции монотонного многоугольника [Garey, Johnson, Preparata, Та-rjan (1978)].
6.2.2.1. Триангуляция монотонного многоугольника
Так как многоугольник Р монотонный относительно у-оси, то путем слияния двух монотонных цепей, образующих границу Р, можно за время O(N) упорядочить вершины Р в порядке уменьшения у-координаты. Пусть щ, и2, uN — последовательность вершин, полученная в результате упорядоче-
6.2. Планарные триангуляции
293
ния. Из монотонности следует, что для каждой вершины щ (1 ^ i ^ N—1) имеется вершина и,-, где i< /, такая, что щщ является ребром многоугольника Р.
Алгоритм триангуляции обрабатывает по одной вершине за раз в порядке уменьшения (/-координаты. В ходе этой обработки порождаются диагонали многоугольника Р. Каждая диаго-
(с)
Рис. 6.9. Три случая, возникающие на основном шаге. Штриховыми линиями обозначены добавленные диагонали.
наль ограничивает треугольник, оставляя для последующей триангуляции многоугольник, имеющий на одну сторону меньше. Алгоритм использует стек, содержащий пройденные вершины, но которые еще не отсечены диагоналями. Алгоритму доступны как самый верхний (верх), так и самый нижний (низ) элементы стека (нижний только для контроля).
Вершины v\ (нижний элемент стека), v2, vi, находящиеся в стеке СТЕК, образует цепь, являющуюся границей многоугольника Р, и при этом y(v\) > y(v2) > •¦• >y{vi). Если i>3, то угол (VjVj+ivj+2) ^ 180° для /=1, 1 — 2
(рис. 6.9).
Алгоритм работает следующим образом: Начальный шаг. В стек помещаются вершины и\ и и2. Основной шаг. Пусть и — текущая вершина.
294
Гл. 6. Близость: варианты и обобщения
(1) Если и смежна cjm.jho не смежна с vi (верх(СТЕК)), то добавить диагонали uv2, uv3, ¦ ¦¦, uvi. Заменить содержимое стека на viu (рис. 6.9(a)).
(2) Если и смежна с vi, но не смежна с v\, то, пока i > 1 и угол (aViVi-\)<. 180°, добавлять диагональ uvt-\ и выталкивать vi из стека. Если это условие, состоящее из двух частей, больше не выполняется (или если оно не выполнялось с самого начала), то добавить и в стек (рис. 6.9(b)).
