Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
procedure УДАЛИТЬ(й,е;у) begin if and (?[о]'<е) then C[v] := C[v] - I
else begin if (b <l(B[v] + E[v])/2}) then УДАЛИТЬ(6,е;ЛСЫН[и]); if ([(B[v] + E[v])/2]<e) then УДАЛИТЬ(&,е;ПСЫН[о])
end
end.
(Заметим, что удаление только ранее вставленных интервалов гарантирует корректность.)
Дерево отрезков — чрезвычайно гибкая структура данных, в чем мы еще сможем убедиться в связи с многочисленными приложениями (гл. 2 и 8). Отметим только, что если надо знать число интервалов, содержащих данную точку х, то простой двоичный поиск в Т (т. е. прохождение пути от корня к листу) полностью решает эту задачу.
1.2.3.2. Реберный список с двойными связями
Реберный список с двойными связями (РСДС) особенно удобен для представления планарного графа, уложенного на плоскости1) [Muller, Preparata (1978)]. Плоская укладка планарного графа G=(V, Е) — это отображение каждой вершины из У в точку на плоскости, а каждого ребра из Е
') Пленарный граф, уложенный на плоскости, принято называть плоским. — Прим. перев.
Гл. 1. Введение
в простую линию, соединяющую пару образов концевых вершин этого ребра так, чтобы образы ребер пересекались только в своих концевых точках. Хорошо известно, что любой пленарный граф можно уложить на плоскости так, чтобы все ребра отобразились в прямолинейные отрезки [Fary (1948)].
Пусть V — {v\, vN}, а Е = {еи ем). Главная компонента РСДС для планарного графа (V, Е) это реберный узел. Между ребрами и реберными узлами существует взаимно однозначное соответствие, т. е. каждое ребро представлено ровно один раз. Реберный узел содержит четыре информационных поля (VI,
VI V2 Fl FZ Р! PZ
Рис. 1.3. Пример РСДС.
V2, F\, F2) и два поля указателей (Р1 и Р2)\ следовательно, соответствующую структуру данных легко реализовать как шесть массивов с теми же именами, каждый из которых состоит из М ячеек. Значения этих полей таковы. Поле VI содержит начало ребра, а поле V2 содержит его конец; так ребро получает условленную ориентацию. Поля FI и F2 содержат имена1 граней, которые лежат соответственно слева и справа от ребра, ориентированного от VI к V2. Указатель Р1 (соответственно Р2) задает реберный узел, содержащий первое ребро, встречаемое вслед за ребром (VI, V2), при повороте от него против часовой стрелки вокруг VI (соответственно V2). Имена граней и вершин могут быть заданы целыми числами. В качестве иллюстрации фрагмент графа и соответствующий ему фрагмент РСДС показаны на рис. 1.3.
Теперь легко видеть, как с помощью РСДС можно вычислить ребра, инцидентные заданной вершине, или ребра, ограничивающие заданную грань. Если в графе N вершин и F граней, то мы можем ввести два массива (HV[\:N) и HF{ \ : F]) для заголовков списков этих вершин и граней. Эти массивы можно заполнить при просмотре массивов VI и F\ за время O(N).
1.3. Геометрические предпосылки
29
С помощью приведенной ниже процедуры ВЕРШИНА (/') можно построить последовательность ребер, инцидентных v,-, как последовательность адресов, занесенных в массив А:
procedure ВЕРШИНА(у') begin a:=HV[j];
а0:=а; А[1] :=а;
i := 2;
if <yi[a] = j) then a:=Pl[a] else a:=P2[a]; while (а ф a0) do begin A[i] := a;
if (Vl[a] = j) then a:=Pl[a) else a:=P2[a]; i:=l+l
end
end.
Ясно, что время работы процедуры ВЕРШИНА (/) пропорционально числу ребер, инцидентных о,. Аналогично мы можем создать процедуру ГРАНЬ (/), с помощью которой можно получить последовательность ребер, ограничивающих заменив соответственно HV и VI на HF и Л в процедуре ВЕРШИНА(/). Отметим, что процедура ВЕРШИНА перечисляет ребра в порядке обхода вокруг вершины против часовой стрелки, в то время как ГРАНЬ перечисляет их в порядке обхода по часовой стрелке вокруг грани.
Часто плоский граф G = (V, Е) представляется в форме реберного списка, где каждой вершине Vj е= У сопоставлен список инцидентных ей ребер, перечисленных в том порядке, в котором они следуют при обходе против часовой стрелки вокруг V,-. Легко показать, что представление G в виде реберного списка можно преобразовать в представление в форме РСДС за время 0(\V\).
1.3. Геометрические предпосылки 1.3.1. Общие определения и обозначения
Объекты, рассматриваемые в вычислительной геометрии, обычно задаются множествами точек в евклидовом пространстве1). Предполагается, что задана система координат, в которой каждая точка представима набором (вектором)
') Ограничение рамками евклидовой геометрии (частного, но весьма важного случая метрической геометрии) позволяет нам прибегнуть к своему непосредственному опыту, но оно обосновано еще и тем, что подавляющее большинство приложений формулируется в терминах евклидова пространства. Однако такое ограничение несущественно для множества тех приложений, которые будут рассмотрены в следующих главах. Позднее мы еще раз вернемся к этой важной теме (разд. 1.3.2).
Гл. 1. Введение
декартовых координат. Геометрические объекты не обязаны состоять из конечных множеств точек, но должны удовлетворять условию: быть описанными конечным образом (обычно конечными цепочками параметров). Следовательно, помимо изолированных точек будут рассматриваться также: прямая линия, содержащая две заданные точки; отрезок прямой линии, определенный парой своих концевых точек; плоскость, содержащая три заданные точки; многоугольник, определенный (упорядоченной) последовательностью точек, и т. п.
