    US.  ДВУМЕРНОЕ   ХЕШИРОВАНИЕ   ПО  РАВНОМЕРНОЙ  СЕТКЕ     235 

    15. Двумерное хеширование по равномерной сетке. Оптимизация алгоритма  
построения изображения полиэдра 

    Тг      Вспомним      проект.     «Построение     изображения      полиэдра» 
 -''(разд.  11)- В этом проекте при построении изображения видимой .части 
полиэдра для каждого ребра перебирались все грани, чтобы дочесть возможное 
загораживание гранью части ребра. Введенный ® конце разд. 11 фильтр лишь 
ускорил обработку пары (ребро, грань) в случае, когда грань заведомо не 
затеняет ребро, однако не изменил качественной картины — перебор всех пар 
(ребро, грань) при построении изображения полиэдра сохранился. 
    Легко проследить аналогию между перебором вс^х граней для определения 
видимой части ребра в разд. 11 и перебором всех влементов множества для 
определения принадлежности этому множеству некоторого элемента. Естественно, 
возникает вопрос: нельзя 'ли воспользоваться идеями хеширования и не искать 
грани, «имеющие отношение» к ребру, а вычислять их? Другими словами, нельзя 
'ли реализовать построение изображения полиэдра так, чтобы пары '(ребро, 
грань) для далеких друг от друга ребра и грани в процессе построения 
изображения вообще не рассматривались'? В этом разделе мы покажем, что это 
возможно, и соответствующим образом изменим проект «Построение изображения полиэдра». 
    Ситуация, когда нам приходится дорабатывать, улучшать уже готовую 
программу, типична для программирования. Данный раздел призван также на 
конкретном примере продемонстрировать, что для проектов, реализованных по 
технологии «сверху вниз», модификация проводится достаточно легко и просто: 
хотя новые идеи и требуют добавления в проект новых исполнителей, реализация 
старых исполнителей меняется незначительно или не меняется вовсе. 
    Идея двумерного хеширования. Рассмотрим плоскость проекции с координатами 
u, v. Опишем вокруг проекции полиэдра на эту плоскость стандартный 
прямоугольник (т. е. прямоугольник со сторонами, параллельными координатным 
осям). Разделим его средними линиями на четыре части (рис, 15.1) и назовем эти 
части tHL'3()uMU.	'" "     '     '' 
    '.•      "Для каждого из четырех гнезд запомним множество граней, Проекции 
которых вадевают гнездо. Допуская вольность речи, такой-,;, множество граней 
мы также будем называть -гнездом и гоорить, wo грань «попала» в гнездо. 
Предварительное размещение граней по гнездам назовем гнездованием граней (рис. 15.2). 
    После гнездования граней для построения изображения любого ребра 
достаточно учесть грани только из тех гнезд, которые задеваю проекция »того 
ребра. Разумеется, грань может попасть не 

    236	ГЛ. 3. СТРУКТУРЫ   ДАННЫХ  И   ИХ  РЕАЛИЗАЦИИ 

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

    Рис.   15.1 

    Это и есть выигрыш, который дает хеширование, — ведь если ребро 
проецируется целиком в одно гнездо, то грани из трех других гнезд вообще не 
рассматриваются при построении изображения видимой части ребра. 
    Естественно пытаться развить этот подход, увеличивая число делений 
прямоугольника, описанного вокруг полиэдра, вплоть до теоретически идеального 
случая, когда размер гнезд примерно равен размеру граней. Еще более, 
изощренную оптимизацию можно было бы провести, рассматривая на плоскости сетку 
гнезд пере-мешшго размера, согласованного с размерами проекций граней. Мы, 
однако, не будем обсуждать этот подход, а ограничимся только случаем 
равномерной сетки. Более того, для простоты мы даже не будем подстраивать 
размер гнезда под размер грани, а реализуем двумерное хеширование по 
фиксированной сетке, например 30 * 30, 

    JB.  ДВУМЕРНОЕ   ХЕШИРОВАНИЕ  ПО   РАВНОМЕРНОЙ   СЕТКЕ     237 

    /j Таким образом, сетка — это матрица из к*к гнезд, где гнездо*-* •то 
множество элементов типа «грань». Хеш-функция сопоставляет некоторому 
прямоугольнику множество задеваемых им гнезд, т. е. 

    1	2	3	4	С 
    ь	7	в	9	10 
    11	12	13	14	15 
    16	17	18	19	20 
    21	22	23	24	25 
    а 23 гранями 
    1.	2,	3.	3,	4,	3, 
    6.	7,	8,	8.	9,	10, 
    11.	12.	13	13,	14,	13 
    и,	12,	13,	13,	14,	15, 
    16,	17,	1в,	18,	19,	20 
    21.	22,	23	22,23,24		,25 
    проекция полиэдра и сетка 2X2 

    Рие. 15.2 


    Результат гнездования 

    какое-то множество индексов матрицы, В соответствии о этой функцией каждую 
грань надо поместить в те гнезда, Которые э«-девает прямоугольник грани, а при 
построении изображения ребра перебирать грани только из тех гнезд, которые 
задевает прямо-1 угольник ребра. 
    Чтобы еще раз пояснить аналогию о обычным хешированием, вспомним, что 
важнейшая операция при работе с множествами*-4 это поиск. Но искать можно не 
только конкретный элемент, Sa-дачу поиска в множестве М заданного элемента в 
можно обобщить так: найти в М подмножество MQ всех элементов m «Е М, 
обладающих свойством Q(m). В задаче поиска элемента свойство Q есть совпадение 
с е, т. е. Q(m)-»(m •= е), В случае рассматриваемого нами двумерного 
хеширования М -* это множество граней 

    238	ГЛ. 1 СТРУКТУРЫ ДАННЫХ И  ИХ РЕАЛИЗАЦИИ 

    полиэдра, в — ребро, а ищется подмножество граней MQ, обладаю-щих свойством 
Q (m) = (проекции m и в на  плоскость uv пересекаются), 
    И в обычном, и в двумерном хешировании множество MQ явно РЙЧИСЛИТЬ трудно. 
 Поэтому  свойство Q  заменяется  более слабым свойством Q' (т. е. таким, это 
из Q'(m) следует Q(m)), вычислить которое более или менее просто, В обычном 
хешировании свойство m «« е заменяется на h(m) »=,h(e), В двумерном 
хешировании свойство  пересечения проекций m  и е заменяется на свойство 
«суще-с^ует   гнездо,  которое   пересекают  н   прямоугольник  ребра   е,   и 
прямоугольник  грани  т».  В  том  и  другом  случае  выигрыш  достигается за 
счет того, что поиск влементов,  удовлетворяющих Q в множестве М, заменяется 
поиском в подмножестве MQ'. k       Простота   вычисления   MQ'   в   обоих   
случаях   обеспечивается :тем, что множество М разбивается некоторым не 
зависящим от е способом на подмножества Mi   (M«=«UMi). В обычном, хешировании 
подмножества Mi не пересекаются, a MQ' совпадает с одним ;и$ них, т. в. задача 
нахождения MQ' сводится к выбору одного из фгЖв существующих MI.  В  двумерно^ 
 хеширов ании  множества Mi ;могут пересекаться, MQ' есть объединение 
некоторого числа Mi и ^ахождеЙЙ» М$' состоит в выборе нескольких из MI. 
    Возвращай» к исходной задаче, заметим, что для двумерного хеширования аадЪ 
знать размеры проекции всего полиэдра. Поэтому будем «читать, что В систему 
предписаний базового исполнителя «Йолиэдр» входит еще одно предписание 4. 
размеры <вых i центр i точка R3, радиус: число), которое возвращает   в   
выходных   параметрах  центр   и   радиус  какой-нибудь Сферы, содержащей 
полиэдр и примерно равной ему по размеру. Реализация. В соответствии с 
технологией «сверху вниз» введем   для  всех действий  о  гнездами   
(гнездование  граней,  перебор ^граней, имеющих отношение к ребру, и т. п.)  
специальный испол-(Натель «Гнездователь».  Кроме того, будем,  если это 
понадобится, •Использовать исполнителей  «Изобразитель  ребра»,  «UV» и др. из 
разд.   И, Тогда в соответствии  с идеей двумерного хеширования построение 
изображения полиэдра можно записать так; программа построение изображения полиэдра 
    , дано       1 j полиэдр в R3 (исполнитель "Полиэдр") 
    ,	| направление проектирования (исполнитель "Проектор") 
    . получить: | плоское изображение ребер  полиэдра (параллельная 
    .	| проекция) с "удалением невидимых линий" 
    ,начать работу 


    15, ДВУМЕРНОЕ ХЕШИРОВАНИЕ ПО РАВНОМЕРНОЙ СЕТКЕ      239 


    .   цикл V грань е Полиэдр.множество граней выполнять 
    .   ,  Гнездователь.добавить объект (вх: грань, 
    .    .	вх :UV.прямоугольник грани (вх: грань)) 
    . конец цикла 
    . цикл V ребро е Полиэдр.множество ребер выполнять 
    , .   Изобразитель ребра.начать работу (вх :ребро) 
    . .  ГнезДователь.для каждого объекта имеющего отношение 
    . .	к (вх : UV.прямоугольник ребра (вх ; ребро)) выполнить 
    . .	(вх:Изобразитель ребра,учесть  тень  от  грани) 
    . .  Изобразитель ребра.кончить работу 
    . конец цикла 
    . Гнездователь.кончить работу	. 
    конец программы 

    Предписание «прямоугольник полиэдра>, которое мы здесь до« бавили 
исполнителю «UV», должно вырабатывать в качестве зна« чения прямоугольник на 
плоскости проекции в uv-координатах, ко* торый содержит проекцию всего 
полиэдра и примерно равен ей по размеру. Реализацию этого предписания 
проведите самостоятельно, 
    Здесь нам впервые встречается ситуация, когда имя программы передается в 
качестве фактического параметра другой программе, а именно имя программы 
«Изобразитель ребра.учесть тень от гра» ни» передается одной из программ 
Гнездователя. Такая передача, в сущности, ничем не отличается от передачи 
чисел — при реализации программы 
    для каждого объекта имеющего отношение к (вх: П) 
    выполнить (вх: дейс ТВ и«> 
    формальный параметр «действие» обозначает некоторую программу^ Встретив 
при выполнении строку 
    действие (вх I е), 
    Универсальный Выполнитель заменит формальный параметр ,«дей< ствие» на 
фактический, указанный в вызове, и выполнит 
    Изобразитель ребра.учесть тень от грани (вх:е). 
    С чисто синтаксической, языковой точки зрения параметр «дей« ствие» здесь 
имеет тип «имя программы» (точнее, сконструирован способом «имя программы» — 
см. приложение 1). 
    Теперь перед нами стоит задача реализовать исполнителя «Гнездователь»: 
    исполнитель Гнездователь . СП: 
    ,      1. начать работу (вх: П: прямоугольник)	% ,     2, добавить объект 
(вх; е; Е, П: прямоугольник) 


    240 ГЛ. 3. СТРУКТУРЫ   ДАННЫХ  И   ИХ  РЕАЛИЗАЦИИ 


    3. для каждого объекта имеющего отношение к 
    (вх:П!прямоугольник) выполнить (вх! действие) 
    4. кончить работу 

    В предписании «начать работу» задается максимальный пря* моугольник, тот 
самый, который дальше разбивается равномерной веткой на гнезда. В соответствии 
с идеями двумерного хеширова* ния по предписанию «добавить объект» надо 
перейти от прямоугольника объекта к множеству задеваемых этим прямоугольником 
гнезд и далее добавить объект в каждое отдельное гнездо из этого множества. 
Аналогично к операциям над отдельными гнездами сводится и выполнение 
предписания «для каждого...». Поэтому в соответствии с технологией «сверху 
вниз» примем решение, что все операции над отдельными гнездами будет выполнять 
специальный исполнитель «Гнезда» и реализуем Гнездователя на базе этого вновь 
придуманного исполнителя. 

    . константы: 
    .   k =" 30 | число делений сетки гнезд 
    типы: 
    индекс гнезда   • прямоугольник = 
    = 0 .. k —1 
    = запись (urain, vtnin, umax, vmax:R) 
    . объекты! 
    .   uO, vO: число | координаты левого нижнего угла сетки гнезд 
    .   du, dv : число | размеры гнезда по горизонтали и вертикали 

    Эти объекты, вместе с константой к полностью задают сетку гнезд и должны 
быть установлены по предписанию «начать работу». . используемые исполнители: . 

  Гнезда 
    конец описаний | -——--——.____ — ___________—____ 

    программа начать работу (вх:П: прямоугольник) 
    . дано       : П: прямоугольник | всей сетки гнезд целиком 
    . получить: 1 установлены глобальные объекты Гнездователя 
    .   uO := n.umin 
    .   vO := П.vtnin 
    .   du := (П.umax — uO)/k 
    •   dv := (n.vmax —vO)/k 
    .   Гнезда.начать работу 
    конец программы 


    15.  ДВУМЕРНОЕ  ХЕШИРОВАНИЕ  ПО   РАВНОМЕРНОЙ  СЕТКЕ     241 


    программа добавить объект (вх ! е : Е, П : прямоугольник) 
    . дано         : | объект е и его прямоугольник П 
    . получить: | объект добавлен во все гнезда, которые задевает П 
    .	imin := минимум (k— 1, целое ( (n.umin — uO)/du) ) н'\ ,Ку 
    .	jmin := минимум (k — 1, целое ( (n.vmin — vO)/dv) ) 
    .	imax := минимум (k — 1, целое ( (П. umax — uO)/du) ) 
    .	jmax := минимум (k — 1, целое ( (n.vmax — vO)/dv) ) 
    • 
    .   цикл V i e imin . . imax выполнять 
    .   .    цикл V jejmin .. jmax выполнять 
    .   .    .    Гнезда добавить объект (вх : е) в гнездо (вх:Ц]') 
    .    .     конец цикла 
    .   конец цикла 
    конец программы 

    Первые четыре строки этой программы, вычисляющие imin, Imax, jmin, jmax, — 
• это и есть хеш-функция, которая по прямоугольнику объекта вычисляет 
«прямоугольное» множество гнезд JT. е. ^множество пар (i, j), imin г^ i sg; 
imax, jmin ^ j sS jmax) такое, что прямоугольник объекта этим множеством 
покрывается целиком. программа для каждого объекта имеющего отношение к 
    (вх : П : прямоугольник) выполнить (вх : действие) . дано        :   
действие : имя программы | и прямоугольник П . получить: | действие выполнено 
для всех гнезд, задеваемых П . объекты: .   Imin, Imax, Jmin, jmax: индекс гнезда 
    .	imin := минимум (k —1, целое ( (n.umin — uO)/du) ) 
    .	jmin := минимум (k—1, целое ( (n.vmin—vO)/dv) ) 
    .	imax:= минимум (k — 1, целое ( (П.umax — uO)/du) )   • 
    .	jmax := минимум (k—1, целое ( (Fl.vmax — vO)/dv)  } 
    .	цикл V i г imin .. imax выполнять 
    .	.     цикл V j г jmin .. jmax выполнять 
    .	.     .     Гнезда.для каждого объекта из гнезда (ex:i,j) 
    .	.     .                                                        выполнить 
(вх: действие) 
    ,	.     конец цикла 
    .	конец цикла 
    конец программы 
    программа кончить работу == Гнезда.кончить работу 
    конец исполнителя 1-...»=,.«».»..=.».«»-»--«----.--=»'. 

    242 ГЛ. 3. СТРУКТУРЫ  ДАННЫХ  И  ИХ  РЕАЛИЗАЦИИ 
    15. ДВУМЕРНОЕ  ХЕШИРОВАНИЕ ПО РАВНОМЕРНОЙ СЕТКЕ     243 

    Итак, мы совершили шаг декомпозиции, получили реализацию ЩГнездователь, 
Гнезда), а заодно придумали и самого исполнителя «Гнезда». Поскольку, однако, 
исполнитель «Гнезда» не является базовым, то надо совершить следующий шаг 
декомпозиции и реали» зовать этого исполнителя на базе чего-то еще. 
    Мы могли бы сказать сейчас, что исполнитель «Гнезда» — это исполнитель 
типа матрица элементов типа гнездо с индексами типа О.. 29, 0.. 29, где тип 
гнездо — это последовательность элементов типа Е. При этом, правда, надо было 
бы изменить форму обращу ний к исполнителю «Гнезда», т. е. вместо 
Гнезда.добавить объект {вх:е) в гнездо (ex:i,j) 
    написать 
    Гнезда (i,j).добавить {вх:е) в конец последовательности, 
    а вместо 
    Гнезда.для каждого объекта из гнезда {ax:i,j) 
    выполнить {вх! действие) написать 
    Гнезда (I,j). встать в начало последовательности цикл V е е непрочитанной 
части Гнезда (i, j) выполнить 
    действие {вх: е) конец цикла 
    ((В последнем случае вызов предписания исполнителя «Гнезда» оказался 
замененным на встроенный в Универсальный Выполни* тель цикл, перебирающий все 
элементы из непрочитанной части последовательности.) 
    Мы,   однако,   обещали,   что   такими   «структурами   структур», " ' 
как   матрица   последовательностей,   в   этой   книге  пользоваться   не 
^будем, Поэтому в соответствии с традициями этой главы реализуем иШЖителя  
«Гнезда»  на   базе вектора,  почти  дословно  повторив ссылочную реализацию 
исполнителя «р множеств» из предыдущего раздела. и 
    сполнитель Гнезда 
    . cm 
    ,  1. начать работу 
    -      2. добавить объект {вх: е i Е)  в  гнездо  {вх: i, j: индекс гнезда) 
    .      3. для каждого объекта из гнезда {вх: i, j: индекс гнезда) 
    .	выполнить {вх: действие: имя программы) 
    — связать {вх: И1 ,И2: индекс) .     4. кончить работу 
    макс число объектов •• максинд	! 
    «k * k | общее число гнезд в сетке 
    . 1000 , 
    •• р + макс число объектов 
    типы: 
    индекс гнезда =* 0 ,. k — 1 индекс = 0 .. максинд номер =0 .. р — 1 
    используемые исполнители: информация: вектор Е (р + 1 ц максинд) @ 
следующий : вектор индекс (нндекс)	• идеи реализации: 
    Каждое состояние вектора ''в следующий" определяет отобра^ жение f 
множества индексов в себя. 
    f i и—> в следующий (и) 
    Мы реализуем Гнезда так, что в каждый момент времени отображение f взаимно 
однозначно и имеет ровно р + 1 траектории. Множество о индексами 1, j 
определяется траекторией, прохо* дишсА через точку n «-= i * k + j (нил этого 
множества). Каждой точке t этой траектории (кроме точки п) отвечает элемент 
мно-. жества, лежащий в информация(1). 
    конец описаний |. 
    КОНСТАНТЫ! 
    k . 
    =30    [число делений сетки 
    программа начать работу 
    , дано        :   мяксинд > р 
    . получить: | траектория каждого множества состоит из точки  нил. 
    ,	| траектория "свободное место" = р ., максинд 
    ,	информация.начать работу 
    .	в следующий.начать работу 
    ,	цикл V п е номер выполнять 
    .	.     связать {п,п) | траектории множеств 
    ,	конец цикла 
    ,	цикл V Игр ., максинд—1 выполнять 
    .	,     связать {И,И+ 1) 
    .	конец цикла 
    ,	снизать {максинд,р) 
    конец программы 
    программа добавить объект (exjejE) в гнездо <ex:i,J) . дико    , i	' 


    244 ГЛ. 3. СТРУКТУРЫ   ДАННЫХ   И   ИХ   РЕАЛИЗАЦИИ 

    ©следующий (р)?= р |т. е. есть свободное место 
    . получить: 
    . п := i *k + j	I нил соответствующего множества . И := & следующий (р)    
        | захватить место из траектории . связать (р, ©следующий (И)) |        
           "свободное место". . связать (И, & следующий (n)) | включить И в 
начало . связать (п, И)                            [траектории п-го множества 
. информация (И) :=е                | добавить объект конец программы 
    программа для каждого объекта из гнезда (вх: i,J: индекс   гнезда) 
выполнить (вх : действие : имя программы) 
    | нил соответствующего множества 
    . дано        : . получить: 
    .   п :=. i*k + J 
    ,   И := ® следующий (п) 
    .   цикл пока Ит^п выполнять   [для каждого эл-та мн-ва 
    .   .     действие (вх : информация (И)) 
    .   .     И := в следующий (И) 
    .   конец цикла 
    конец программы 
    программа связать (вх: И1.И2 : индекс) == ^следующий (И1) :=И2 
    программа кончить работу == 
    информация. кончить работу; @ следующий . кончить работу конец исполнителя 
----_--_»----== = - ——— __ — = »-__=, 

    Замечание. В случае, если возникает необходимость выполнить какое-то 
действие для каждого из объектов, хранящихся в некотором исполнителе X, можно 
поступить двояко. Один путь — добавить исполнителю X предписания «начать 
обработку», «есть необработанные объекты», «полу», чить очередной объект в 
<вых ; е>», «кончить обработку» и написать фрагмент программы вида 

    X. начать обработку 
    цикл пока Х.есть необработанные объекты выполнять X. получить очередное 
объект в (вых '. е) 
    .    действие <вх : е) 
    конец цикла 
    X. кончить обработку 

    Другой  путь,  который  и  был  применен  выше, — «поручить»   перебор 
объект тов самому исполнителю X, т. е. ввести предписание 

    Х.для каждого объекта выполнять <вх : действие). 

    При   первом   подходе   в   цикле  обработки   кроме   выполнения   
действия -Происходят   как   минимум   два    вызова    предписаний  
исполнителя   X.   Если исполнитель X реализован на базе исполнителя V, 
который в свою очередь реализован на базе Z( и перебираемые объекты реально 
хранятся в нспол-, 

    15.   ДВУМЕРНОЕ   ХЕШИРОВАНИЕ  ПО   РАВНОМЕРНОЙ   СЕТКЕ     245 

    нителе Z, то при получении очередного объекта в цикле обработки эти 
исполнители будут «по цепочке» вызывать друг друга и передавать полученный 
объект е обратно. При втором подходе «по цепочке» будет передан только запрос 
на перебор объектов, а сам перебор будет осуществляться исполнителем Z. Таким 
образом, второй подход (в программировании ов называется запроцедуриванием 
циклов) позволяет писать не только более короткие и более понятные, Но и более 
аффективные программы. 
    Оценки эффективности двумерного хеширования. Мы реализовали построение 
изображения полиэдра на основе идей двумерного хеширования по равномерной 
сетке. Правомерно, однако, задать вопрос: а что дает такая реализация? 
Интуитивно кажется, что .число учитываемых для каждого ребра граней должно 
существенно сократиться. Однако, что значит существенно? Можно, ли, например, 
гарантировать, что в среднем для каждого ребра будет перебираться не более 
некоторой доли от общего числа граней? Можно ли вообще хоть как-то более или 
менее строго оценить эффективность полученной реализации? 
    Получение подобного рода оценок является не программистской, а 
математической деятельностью. Пригодность или непригод» ность новой программы 
в программировании обычно определяется по результатам работы программы на 
конкретных данных. Если, однако, ноная программа оказалась 
неудовлетворительной и надо разобраться, почему она работает медленно, или 
если надо понять, на каких классах данных новая программа эффективна, то 
получение строгих математических оценок может оказаться полезным. 
    Мы сформулируем сейчас оценки эффективности двумерного хеширования по 
равномерной сетке и покажем, как их можно доказать. Основную ценность при этом 
представляют не столько сами оценки, сколько демонстрация применения 
математических методов рассуждения к чисто практической программистской задаче. 
    Итик, пусть полиэдр имеет N ребер и М граней. Нас интересует оценка 
времени tp построения изображения полиэдра для больших N и М при заданном 
векторе проектирования р. Прежде псего пренебрежем затратами на 
предварительное гнездование граней — они линейно зависят от числа граней. Тогда 

    N 
    tp-YZ™!» 
    i-l 

    где mi — число граней, имеющих отношение к i-му ребру (грань имеет 
отношение к ребру, если существует гнездо, которое заде-пнют и грань, и 
ребро); \ — константа, характеризующая время обработки одной пары (ребро, грань). 
    Максимальное значение каждого числа mi равно общему числу М граней 
полиэдра, Можно подумать полиэдры, для которых 

    246	;   ГЛ' 3- СТРУКТУРЫ  ДАННЫХ   И   ИХ  РЕАЛИЗАЦИИ 

    хеширование ничего не дает, —jjce ^.действительнр равны М и 1Р»в,\МЫ. 
Поэтому применять хеширование (и получать какие бы то ни было оценки) надо 
лишь при некоторых органичениях, пред»; положениях о полиэдре. 
    Мы будем предполагать, что грааи полиэдра имеют примерно одинаковый размер 
и не очень вытянуты, а размер гнезд близок к размеру граней. Более формально 
это предположение можно сформулировать так: существуют константы d> О, С ^ 1 
такие, что для любой грани Г существуют круги Ва/с и Вас в плоскости грани 
радиусов d/C и dC соответственно такие, что } 
    1. Bd/c <= Г с Bdc.	(1) При тех же константах d и С для любого гнезда G 
существуют «руги Ва/с и Вас такие, что 
    BdyccQc:B 
    dc. 
    Кроме того,  введем  еще  одну  характеристику  полиэдра   (на-. вовем ее 
кратностью поверхности); 
    •    ...	..-.--                                                 *• '  .««Ufcb. 
    К «= max KL. 
    L> 
    где L — ^севрзможные прямые, a KL — число трансверсальных пересечений (т. 
е, пересечений без касания) прямой L с гранями полиэдра, (На практике К обычно 
находится в диапазоне от 2 до 6.) Тогда время построения изображения полиэдра 
при векторе проектирования р (без учета линейных по числу граней затрат на 
предварительное гнездование граней) можно оценить как 

    ra" 
    (2) 

    где mi — число граней, задевающих цилиндр радиуса 3dC с осью, параллельной 
р, выбранный так, что 1-е ребро содержится в ци* Линдре радиуса dC с той же 
осью (это возможно, так как всякое ребро принадлежит некоторой грани, • для 
грани выполнено условие (1)). 
    Здесь и далее а й^Ь (меньше с точностью до константы) озпа« яает, что 
существует* константа q > О, на зависящая от полиэдре (т, в, от N, М, А, К), 
такая, что а < qb. 
    Формула (2) очевидна, во ничего не говорит об эффективности двумерного 
хеширования. Из нее, однако, ужа чисто формально ]иожно получить еледующие оценки: 
    А) в среднем DO всем направлениям проектирования ори М > I 

    d5.  ДВУМЕРНОЕ  ХЕШИРОВАНИЕ  ПО  РАВНОМЕРНОЙ СЕТКЕ  247 

    В) при любом направлении проектирования р 
    где Dp — диаметр проекции модели на прямую, параллельную р. 
    В частности, если полиэдр не очень вытянут вдоль р, т, е< Dp/d^VR то 
tp^KNVN"
    Эти оценки являются оценками сверху, Кроме того, можно привести примеры 
полиэдров, показывающие, что оценки А) и В) не улучшаемы, а именно: 
    С) клетчатый лист п * п, вектор р ортогонален плоскости листа, К = 1: 
    t 
    N; 
    D) клетчатый лист п * п, вектор р параллелен плоскости листа к одному из 
направлений сетки листа, К =• U 
    tp « N 
    Е) многогранник из  п2 граней,  удовлетворяющих   (1), вписанный в сферу 
радиуса nd, р — любое, К = 2, п > 5Cs 
    tp x NInM 
    (а « b означает, что а ^ b и b ^ а). 
    Доказательства оценок А), В) и Е)  базируются на том факте, что 
    поверхности фигуры Ф 
    поверхности любой фигуры, содержащей Ф 
    (3) 
    где К — кратность поверхности фигуры О, определяемая аналогично кратности 
пош'рхности полиэдра. 
    ('.им »тот фпкт очевидно следует из известной формулы интегральной 
геометрии (см., например, Сантало Л, Интегральная геометрия и геометрические 
вероятности, гл. 14, раздел 5), выражающей площадь S поверхности компактного 
двумерного, дифференцируемого кусочно-гладкого многообразия Ма через число Кь 
транспсрсальных пересечений всевозможных прямых L 
    с многообразием М2: 
    4       \       KLdL. 
    (2), 
    Из А) и В) докажем как более простую оценку В). Согласно 
    i < N max m 


    248	ГЛ. 3. СТРУКТУРЫ  ДАННЫХ   И  ИХ   РЕАЛИЗАЦИИ 

    Из (1) следует, что все грани j, дающие вклад в mi, т.е. задевающие 
цилиндр i-ro ребра вдоль р радиуса 3dC, содержатся в бесконечном цилиндре 
радиуса R = 4dC с той же осью, что и цилиндр i-ro ребра. Так как диаметр 
проекции полиэдра на ось цилиндра равен Dp, то можно выделить часть цилиндра, 
скажем В, длины DU такую, что все грани j из ггц лежат в этой части. Площадь 
поверхности этой части цилиндра 

    SB = 2iiR2 + 2jtRDp = 2nR (R + Dp). 

    На основании (З) суммарная площадь S граней j из mi удовлетворяет неравенству 

    S < К • SB = 2nKR (Dp + R) « 2яК4 dC (Dp + 4dC). 

    С другой стороны, из (1) имеем 

    S > я (d/C)2 mi. Следовательно, 
    m, < (C/d)" 2K4 dC (Dp + 4dC) 
    8C2CK (Dp/d + 4C) ^ К (Dp/d + 1). 

    Значит, 

    tp < N max mi ^ KN (Dp/d + 1 ). 

    Доказательства оценок А) и Е), хотя и более сложны и требуют ряда 
дополнительных построений, проводятся в принципе таким же образом на основе 
формулы (3), Доказательства оценок С) и D) тривиальны и оставляются читателю. 
    Приведенные выше оценки показывают, что двумерное хеширование по 
равномерной сетке наиболее эффективно на участках поверхности полиэдра, 
нормальных к вектору проектирования, — • на этих участках tp ж KN. На 
участках, почти касательных к вектору проектирования, tp к K.N V-M (если 
только поверхность не яъ<< лается сильно вытянутой вдоль р), а в целом для 
шарообразной) модели (например, для аппроксимации сферы), равно как и в 
среднем по всем направлениям проектирования для любой модели, 
    
    ЗАДАЧИ И УПРАЖНЕНИЯ 

    1. Реализуйте   предписание   «Ш/.прямоугольник   полиэдра». 
    2. Модифицируйте построение изображения полиэдра следующим образом: 
введите три дополнительные сетки гнезд, такие же как и первая, но со сдвигом 
на половину размера гнезда по горизонтали и/или по вертикали, с тем чтобы 
«накрыть» гнездами 

    16. ВИРТУАЛЬНАЯ  ПАМЯТЬ 249 

    дополнительных сеток вертикальные и горизонтальные линии первой сетки. При 
гнездовании грани ее следует добавлять во все задеваемые гнезда всех сеток, а 
при обработке ребра следует выбрать сетку, в которой ребро задевает наименьшее 
количество гнезд, и работать так, как если бы других сеток не существовало. 
(Для полиэдров с гранями примерно одинакового размера такая модификация 
обеспечивает практически 100 %-ное попадание изображаемого ребра целиком в 
одно гнездо, что приводит к ускорению построения изображения полиэдра в 1.5—2 раза.) 
    3. Докажите оценки С) и D) эффективности двумерного хеширования для 
клетчатого листа из п » п граней. 
    4. Пусть Ml—множество отрезков в R3 и М2-w множество треугольников в R3. 
Реализуйте программу построения изображения отрезков из Ml с учетом 
загораживания их треугольниками из М2. 
    5. Решите задачу 4 так, чтобы в процесса построения изображения Ml каждый 
треугольник из М2 рассматривался не более одного раза. 
    6. Примените двумерное хеширование  при  решении  задачи  б, В  задачах  
7—11   требуется  придумать, максимально  эффективную реализацию.  Как  
минимум, программа  не должна  анализировать все пары (a, b), a s A, be В. 
    7. Пусть А и В — два множества точек на прямой. Напишите программу, 
которая находит а) расстояние между множествами, б) пересечение множеств. 
    8. Пусть А и В — два множества отрезков на прямой. Напишите программу, 
которая находит а) расстояние между множествами, б) пересечение множеств. 
    II. Пусть Л м В дня множества точек на плоскости. Напи« шмтг и|)ог|)11мму, 
которая находит их пересечение. 
    10. Пусть А и В — два множества целых точек в R3, лежащих и таре радиуса 
127. Напишите программу, которая находит их пересечение. 
    11. Пусть А и В — два множества точек в единичном круге ня плоскости, 
Напишите программу, которая находит расстояние между ними с точностью до 1/10. 