Достижения высшей школы

Алгоритмы с кэшированием поиска треугольников

Предложенные автором алгоритмы триангуляции с кэшированием поиска [1, 2, 3, 4] несколько похожи на алгоритмы триангуляции с индекси рованием центров треугольников. При этом строится кэш - специальная структура, позволяющая за время O(1) находить некоторый треугольник, близкий к искомому. В отличие от алгоритмов триангуляции с индексированием изменённые треугольники из кэша не удаляются (предполагается, что каждый удаленный треугольник как запись в памяти компьютера превращается в новый треугольник, и поэтому допустимость ссылок на треугольники не нарушается при работе алгоритма), один и тот же треугольник может многократно находится в кэше, а некоторые треугольники вообще там отсутствовать [4].

Подпись: Рис. 1. Локализация точек в кэше (S – найденный квадрат, – связанный с квадратом треугольник, Т – конечный треугольник)

Основная идея кэширования заключается в построении некоторого более простого чем триангуляция планарного разбиения плоскости, в котором можно быстро выполнять локализацию точек. Для каждого элемента простого разбиения делается ссылка на треугольник триангуляции. Процедура поиска сводится к локализации элемента простого разбиения, перехода по ссылке к треугольнику и последующей локализации искомого треугольника алгоритмом из простого итеративного алгоритма триангуляции Делоне. В качестве такого разбиения проще всего использовать регулярную сеть квадратов (рис. 1). Например, если данное планарное разбиение полностью покрывается квадратом [0; 1] х [0; 1], то его можно разбить на равных квадратов. Занумеруем их всех естественным образом двумя параметрами . Тогда по данной точке (х,у) мы мгновенно можемнайти квадрат [x/m] [y/m], где […] - операция взятия целой части числа.

Кэш в виде регулярной сети квадратов наиболее хорошо работает для равномерного распределения исходных точек и распределений, не имеющих высоких пиков в функции плотности. В случае же, если заранее известен харак тер распределения, можно выбрать какое-то иное разбиение плоскости, напри мер, в виде неравномерно отстоящих вертикальных и горизонтальных прямых.

Итеративный алгоритм триангуляции со статическим кэшированием поиска

В предложенном автором алгоритме триангуляции со статическим кэшированием поиска [1, 2, 3, 4] необходимо выбрать число т и завести кэш в виде 2-мерного массива r размером mхm ссылок на треугольники. Первоначально этот массив надо заполнить ссылками на самый первый построенный треугольник. Затем, после выполнения очередного поиска, начатого с квадрата (i,j), и в котором был найден некоторый треугольник Т, необходимо обновить информацию в кэше: ссылка_на_Т. Размер статического кэша следует выбирать по формуле , где s - коэффициент статического кэша [1, 3]. На практике значение s следует брать 0,6 - 0,9 (рис. 2).

Подпись: Рис. 2. Зависимость временипостроения триангуляции Делоне алгоритмом статистического кеширование t от значения s

Первое время, пока кэш не обновится полностью, поиск может идти довольно долго, но потом скорость повышается. Этого недостатка лишён следующий алгоритм.

Итеративный алгоритм триангуляции с динамическим кэшированием поиска

В предложенном автором алгоритме триангуляции с динамическим кэ шированием поиска [1, 2, 3, 4] необходимо завести кэш минимального размера, например 2 х 2. По мере роста числа добавленных в триангуляцию то чек необходимо последовательно увеличивать его размер в 4 раза (в 2 раза по обеим осям координат), переписывая при этом информацию из старого кэша в новый. При этом для увеличения кэша надо выполнить следующие пересылки (h - старый кэш, - новый): Данный алгоритм кэширования позволяет одинаково эффективно работать на маленьком и большом количестве точек, заранее не зная их числа.

Увеличение размера динамического кэша в 2 раза следует производить каждый раз при достижении числа точек в триангуляции , где r - ко эффициент роста динамического кэша, a m - текущий размер кэша. На практике значение коэффициента роста динамического кэша следует выбрать 3 – 8 (рис. 3).

Подпись: Рис. 3. Зависимость временипостроения триангуляции Делоне алгоритмом динамического кеширование t от значения r

Для большинства случайных распределений исходных точек данный ал горитм работает значительно быстрее всех остальных алгоритмов [4]. Однако на некоторых реальных данных, в которых последовательные исходные точки находятся вблизи друг друга (например, точки изолиний карт рельефа), алго ритм динамического кэширования может тратить большее время, чем другие алгоритмы. Для учета такой ситуации в алгоритм следует добавить дополни тельную проверку. Если очередная добавляемая точка находится от предьщу- щей точки на расстоянии большем, чем некоторое (порядка текущего размера клетки кэша), то поиск необходимо начать с треугольника из кэша, иначе нуж но начать с последнего построенного треугольника. В такой модификации алгоритм динамического кэширования становится непревзойденным по скорости работы на большинстве реальных данных.

Литература:

1. Скворцов А.В. Обзор алгоритмов построения триангуляции Делоне // Вычислительные методы и программирование, 2002, Т. 3, раздел 1, с. 14 - 39 (http://num-meth.srcc.msu.su).

2. Скворцов А.В. Построение триангуляции Делоне за линейное время // Изв. вузов. Физика, 1999, No3, с. 120-126.

3. Скворцов А.В. Триангуляция Делоне и её применение. - Томск: Изд-во Томск,ун-та, 2002. 128с.

4. Скворцов А.В., Костюк Ю.Л. Эффективные алгоритмы построения триан гуляции Делоне // Геоинформатика: Теория и практика. Выпуск 1. - Томск: Изд-во Томск, ун-та, 1998, с. 22 - 47 .