Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
370
Гл. 7. Пересечения
(2.1.2) обходим границу Ki против часовой стрелки от Li до тех пор, пока не достигнем или единственного ребра Ws-\ws, пересекающего луч у,•?,¦+! Л в точке w" (что наверняка произойдет, если Ki ограничен), или хвоста списка, не найдя подобного ребра (только в случае неограниченности Ki). Обозначая Ki = oLWt ¦. ¦ Ws-ф, в первом случае полагаем Ki+i := aw'ei+iw"$\ во втором случае (когда Ki неограничен) нужно проверить, будет Ki+\ ограниченным или нет. Если наклон луча viei+iA заключен в пределах между наклонами начального и конечного лучей Ki, то Ki+\ : = aw'et+\A также неограничен. В противном случае начнем обход границы Ki против часовой стрелки от головы списка до тех пор, пока не найдено ребро wr-\wr, которое пересекает луч viei+\A в точке до"; обозначая Ki ywr+i8wtr\, полагаем Ki+\: = := 8w'ei+\w", и список становится циклическим.
Выборы точек jFi+i и L,+i зависят от позиции ы+\ на луче viei+iA и от того, будет ли этот луч иметь одну или две точки пересечения с Ki. Рассмотрим эти два луча по отдельности:
(2.1.3) viei+iA пересекает Ki в точках до' и до". Если у<+1 е [vid+iw'], то выбираем Fi+\ так же, как в случае (1.2). Иначе положим F;+\\=w. Если vi+\ [viei+\w"}, то положим Li+\\=w". Иначе Li+i выбирается так же, как в случае (1.1), за исключением того, что Ki+\ обходится против часовой стрелки от до".
(2.1.4) v-,ei+\A пересекает Ki только в точке до'. Если y,-+i еЕ [у,е1+1до'], то выбираем Fi+\ так же, как в случае (1.2); иначе положим Fi+\:=w'. В качестве Li+\ выберем бесконечную точку на луче Viei+\A.
(2.2) Li лежит слева от луча vtet+iA (рис. 7.31). В этом случае Ki+r.= Ki. Fi+i определяется так же, как в случае (1.2). Если Ki ограничен, то L,+i определяется так же, как в случае (1.1); иначе Li+\ := Li.
Корректность данного алгоритма доказывается в следующей лемме, где через Н; обозначена полуплоскость, лежащая слева от прямой Ле,Л.
Лемма 7.1. Многоугольник Л',ц является пересечением полуплоскостей Но, #i.....Я,-+1 при i — 0, 1,____/V —2.
7.2. Плоские приложения
371
Доказательство. По индукции. Заметим, что К\ по определению есть пересечение Я0 и Н\ (начальный шаг данного алгоритма). Предположим индуктивно, что Ki = Я0ЛЯ1П ••• Поскольку во всех случаях, рассмотренных для общего шага, конструктивно строилось пересечение Ki и Я,+1, то доказательство завершено.
Хотя лемма 7.1 гарантирует, что изложенный алгоритм корректно строит К(Р), необходимо проделать небольшую, но важную модификацию общего шага для повышения его эффективности. Фактически существуют случаи (рис. 7.32) многоугольников с пустым ядром, для которых можно затратить
Рис. 7.32. Случай, когда немодифицированный алгоритм затрачивает 0(№) времени. Af-сторонний многоугольник Kn/2 заштрихован. Затем алгоритм делает вокруг Kn/2 A7/12 оборотов, прежде чем достигает вершины VNn+l, в которой выясняется, что К(Р)= 0.
0(N2) времени на всю работу алгоритма. Этого можно избежать путем проведения дополнительной проверки для определения ситуации, показанной на рис 7.32. Здесь для краткости опущены детали этой проверки, а читатель отсылается к работе [Lee, Preparata (1978)], которая содержит полное доказательство. Достаточно сказать, что после проведения обсуждаемой модификации алгоритм гарантированно остановится после того, как он обойдет границу Р, совершив поворот на угол Зя вокруг любой точки частичного ядра Ki.
Теперь оценим эффективность этого алгоритма. Удобно проанализировать порознь два основных типа действий, производимых алгоритмом построения ядра. Первое связано с корректировкой ядра путем пересечения Ki с лучом Aei+lA для получения /0+1; второе связано с корректировкой Ft и L, и состоит
372
Гл. 7. Пересечения
в обходах Ki против часовой стрелки (или прямых обходах) для получения новых опорных вершин (однако заметим, что в ряде случаев, таких как (1.1) и (2.1), корректировка Ki непосредственно приводит к корректировке той или иной опорной вершины).
Начнем с рассмотрения корректировок пересечений. В случае (1.1) (когда алгоритм не завершается) обходим Ki, начиная с Fi, как по часовой стрелке, так и против нее (при этом обходе ищется также Ft+i). Обозначим через v, общее число ребер, пройденных перед обнаружением двух точек пересечения w' и w". При этом фактически у,- — 2 ребер удаляются из Ki (те, которые заключены между ws и wt-\ на рис. 7.28), а поскольку все удаленные ребра коллинеарны. различным ребрам Р, то Л (v(- — 2) Итак, Yj vi — общее число вершин, пройден-
ных алгоритмом при обработке случая (1.1), —ограничено сверху числом 3N, т. е. равно O(N). Такое же рассуждение с небольшими видоизменениями применимо к случаю (2.1).
Теперь рассмотрим те корректировки опорных вершин F и L, которые явно выполняются в процессе построения пересечения. Такие корректировки проводятся для L во всех случаях — (1.1), (1.2), (2.3), (2.4), а для F в случаях (1.2) и (2.4). Заметим, что во всех этих случаях опорные вершины продвигаются вперед по границе Ki. Рассмотрим, например, корректировку L в случае (1.1); другие случаи можно трактовать аналогично. Рассмотрим множество тех ребер Ki+i, которые пройдены алгоритмом перед определением Ц+\; посещение ребра, следующего непосредственно за Li+U будет называться перелетом. Очевидно, что при обработке случая (1.1) общее число перелетов равно O(N), поскольку совершается не более одного перелета в расчете на вершину Р. Теперь докажем, что если игнорировать перелеты, то любое ребро будет пройдено не более чем дважды. Предположим обратное, что при обработке vi одно из ребер было пройдено в третий раз. Поскольку обход всегда ведется в положительном направлении, отсюда следует, что граница Р обернулась вокруг Ki по меньшей мере дважды, т. е. существует такая точка q е Ki, вокруг которой граница при обходе повернулась на угол ^4л, а это противоречит ранее высказанному утверждению.
