355
правок
Изменения
→Структура данных
он был создан на шаге (2) при построении этой триангуляции.
Теперь построим структуру данных $T$ для поиска. Эта структура представляет собой направленный ацикличный граф, вершинами которого будут наши треугольники. Определим эту структуру следующим образом: из треугольника $R_k$ будет вести ребро в треугольник $R_$$$, если при построении $S_i$ из $S_{i-1}$ мы имеем
* $R_j$ удалятся из $S_{i - 1}$ на шаге (1)
* $R_k$ создается в $S_{i}$ на шаге (2)
* $R_j \cap R_k \not \bigcirc$
Очевидно, что треугольники из $S_1$ (и только они) не имеют исходящих ребер.
ВСТАВИТЬ КАРТИНКУ СТРУКТУРЫ И ЕЕ ОПИСАНИЕ
</wikitex>
===Поиск===
<wikitex> После построения структуры легко понять, как в ней происходит поиск. Элементарной операцией здесь является определение принадлежности треугольнику. Очевидно, что она выполняется константное время. Сначала мы локализуемся в треугольнике $S_1$. После этого мы строим путь от корневой вершины до листа следующим образом: находясь в какой-либо вершине $z$, просмотрим всех ее детей на принадлежность точки соответствующему треугольнику и, так как точка может находиться лишь в одном треугольнике конкретной триангуляции, перейдем в эту вершину, и продолжим поиск.
Этот поиск также можно рассматривать как последовательную локализацию в триангуляциях $S_1, \dots, S_{h(N)}$, откуда и происходит название самого метода.
