Научная литература
booksshare.net -> Добавить материал -> Математика -> Препарата Ф. -> "Вычислительная геометрия: Введение" -> 152

Вычислительная геометрия: Введение - Препарата Ф.

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 146 147 148 149 150 151 < 152 > 153 154 155 156 157 158 .. 180 >> Следующая


a[v]: = удвоенное число компонент связности & П \В М , E[v])l

ЛКР [с] := 1 или 0 в зависимости от того, будет или нет В [v] нижним концом интервала из & П [В [о], Е [v];

ПКР [v] := 1 или 0 в зависимости от того, будет или нет Е [v] верхним концом интервала из & П [В [v], Е [v]].

Эти три специальных параметра вначале равны нулю, а их вычисление выполняет нижеследующая конкретизация подпро-

') Заметим, что возможно равенство X[i — 1] и X[i], т. е. две вертикальные стороны имеют одинаковые абсциссы. В этом случае введем для них удобное лексикографическое упорядочение (например, по ординатам их нижних концов) и представим себе, что две такие стороны фиктивно раздвинуты на величину е в направлении оси х.

2) ЛКР и ПКР — аббревиатуры выражений «левый край» и «правый кран». — Прим. перев.

8.4. Мера и периметр объединения прямоугольников 413

граммы КОРРЕКТИРОВАТЬ, вызываемой в строке 4 процедуры ВСТАВИТЬ (см. разд. 8.2):

procedure КОРРЕКТИРОВАТЬ(о);

1. begin if (C[v] > 0) then

2. begin a[y]:=2;

3. ЛКРМ:=1;

4. ПКР[г>] := 1 end

5. else begin a[v] := а[ЛСЫН[а]] + а[ПСЫН[у]] -

-2 • ПКР[ЛСЫН[и]] ЛКР[ПСЫН[и]];

6. ЛКРМ:=ЛКР[ЛСЫН[у]];

7. ПКР[и]:=ПКР[ПСЫН[и]] end

end.

Корректность процедуры КОРРЕКТИРОВАТЬ доказывается легко. Если С[о]^1, т. е. интервал [B[v],E[v]] полностью накрыт, то в составе &f\[B[v], E.[v]] будет ровно один элемент, причем оф] = 2, ЛКРМ = ПКРМ = 1, как указано в

Текущая адсиисса

Рис. 8.11. Вклад в величину периметра на текущем шаге состоит из длин горизонтальных и вертикальных ребер.

строках 2—4. Если же С [v] = 0, то число элементов в & [") Г![ЯМ, E[v]] равно сумме чисел таких элементов для двух потомков узла и, за исключением того случая, когда сечение 3 содержит один интервал, соединяющий точку ?[ЛСЫН[у]] = = 5[ПСЫН[у]]; в последнем случае ПКР1ЛСЫН [о] ] = = ЛКР [ПСЫН [v] ] = 1. Этим доказывается корректность строк 5—7 алгоритма. Кроме того, не составит большого труда показать, что дополнительные параметры а, ЛКР и ПКР вы-

414

Гл. 8. Геометрия прямоугольников

числяются за константное время в расчете на один пройденный узел.

Теперь очевидно, что а,= а[корень (Т)\. Следовательно, алгоритм вычисления периметра F получается путем простой модификации соответствующего алгоритма вычисления меры этого объединения. Заметим, однако, что в то время, как в алгоритме вычисления меры объединения к площади F добавляется площадь только что заметенной вертикальной полосы (так что корректировка дерева отрезков следует за суммированием этой площади), в обсуждаемом алгоритме ситуация несколько иная. Обратимся к рис. 8.11; вклад текущего шага в периметр состоит из двух частей: от горизонтальных ребер в полосе [X[i— 1], X[i] ] он равен а,-X — X[i— 1]) и от вертикальных ребер на абсциссе X[i] он равен |m,+i — m,|. Поэтому величину ос,- необходимо извлечь из дерева отрезков до его корректировки, а величину m,>i — после. Итак, получаем:

procedure ПЕРИМЕТР-ОБЪЕДИНЕНИЯ-ПРЯМОУГОЛЬНИКОВ begin X[l : 2N] := упорядоченная последовательность абсцисс вертикальных сторон; *[0]:=*[1]; т0:=0; р:=0;

построить и инициализировать дерево Т, состоящее

из ординат сторон прямоугольников;

for i := 1 until 2N do

begin a*:=a [корень(Г)];

if (X[i] — абсцисса левого конца) then ВСТАВИТЬ^,,*,, корень(Г)) else УДАЛИТЬ^,*?,-; корень(Г)); m* := т[корень(Г)];

p:=p + amX(X[i\-X\i-l]) + \m--m0\; m0 := m*

end

end.

В заключение получаем:

Теорема 8.3. Периметр объединения N изотетичных прямоугольников можно вычислить за время О (N log N).

8.5. Контур объединения прямоугольников

Тот же самый общий подход (плоское заметание, основанное на дереве отрезков) можно с успехом применить для решения другой интересной задачи: определения контура

8.5. Контур объединения прямоугольников

415

объединения F, состоящего из N изотетичных прямоугольников Ru RN. Вновь F = Ri U ... [}RN может состоять из одной или более не пересекающихся компонент связности, а каждая компонента может содержать или не содержать внутренние дыры (заметим, что дыра может содержать внутри себя некоторые из компонент связности F). Контур (граница) F состоит из набора непересекающихся циклов, образованных (чередующимися) вертикальными и горизонтальными ребрами. Условимся, что любое ребро ориентировано так, что фигура расположена слева от него; другими словами, цикл ориентирован по часовой стрелке, если он ограничивает дыру, и против часовой стрелки, если он является внешней границей компоненты связности. Мы имеем:

Задача 0.4 (КОНТУР ОБЪЕДИНЕНИЯ ПРЯМОУГОЛЬНИКОВ). Дан набор из N изотетичных прямоугольников. Требуется определить контур их объединения.

Во-первых, заметим, что периметр (для вычисления которого в предыдущем разделе был описан довольно простой алгоритм) является не чем иным, как длиной искомого контура. Однако мы увидим, что

вычислить периметр зна- е3| 1е6 е _ ~ у87

чительно проще, чем сам г-----, .-у6?

контур, как набор непе- eif
Предыдущая << 1 .. 146 147 148 149 150 151 < 152 > 153 154 155 156 157 158 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed