Изменения

Мы договариваемся, что никакие две точки не лежат на одной вертикалевертикали(в противном случаи все еще случае всё ещё противнее).

*''левая граница'' (<tex>\operatorname{leftpleft}p</tex>) {{---}} точка, определяющая левую сторону трапецоида или, в случаи треугольника, просто являющаяся левой вершиной.*''правая граница'' (<tex>\operatorname{rightpright}p</tex>) {{---}} аналогично левой, только справа.

Поисковая структура представляет из себя ациклический граф с одним корнем и каждому трапецоиду в структуре соответствует один листсоответствующими трапецоидам листьями.

У каждого узла есть два ребенка и при . При этом узел может быть двух типов.

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

Если мы находимся не в листе, то мы должны опрелетиться опредетиться, в каком из детей мы окажемся дальше.

*Если текущий узел соответсвует вершине, то смотрим левее или провее правее мы находимся(проверка по <tex>x</tex>-координате). *Если текущий узел соответствует отрезку, то смотрим выше или ниже мы находимся(проверка по <tex>y</tex>-координате).

Мы находимся на одной вертикале вертикали с вершиной

Во время построения трапецоидной карты(в дальнейшем <tex> T</tex>) алгоритм так же строит структуру для поиска .

Так как трапецоидная карта {{- --}} геометрическая структура, а основные операции ведутся именно с поисковой, основной упор делается на неё.

Наш алгоритм добавляет отрезки по одному и , после каждого добававления добавления, модидицирует <tex> T</tex> и <tex> D</tex>.

Считается, что еслли если добавлять отрезки рандомнов случайном порядке, то время будет хорошим. Почему и какое время будет рассписано достигаться, расписано дальше.

*Создали новый новые трапецоиды.

===Поиск трапецоидов которых , которые пересек отрезок===Чтобы модифицировать карту, мы должны понять , где произошло изменение.

Оно произошло в тех трапецоидах , которые пересек текущий отрезок , или можно сказать, что трапецоид с <tex>i-1</tex>-ой итерации не будет в <tex>i</tex>-ой только если его пересек отрезок.

Пусть якобы есть множество трапецоидов <tex>\Delta_0, \Delta_1, \Delta_2 ... \ldots \Delta_k</tex> , упорядоченное по <tex>s_i</tex>

Пусть <tex>\Delta_{j+1}</tex> {{---}} один из правых соседей <tex>\Delta_j</tex> . Так же , при этом не сложно понять , каким соседом он является.

Если rightp(<tex>\operatorname{rightp} \Delta_j</tex>) лежит выше <tex>s_i</tex>, то сосед нижний и наоборот.

Это значит, что , если мы знаем первый трапецоид, то мы можем найти остальные просто обходя по карте соседей справа.

Чтобы найти первый трапецоид , нужно просто локализовать правый конец в текущей карте.

*Простой {{- --}} отрезок не пересекает ни одного трапецоида, то есть целеком целиком внутри.

В случаи если какие-то трапецоиды выродятся в треугольники будет не четыре новых трапецоида , а 2 или 3. Слава богу это не самая большая проблема. *Сложный {{--- }} отрезок пересекает сразу несколько трапецоидов.

Сначала добавляем вертикальные лучи из концов текущего отрезка. Это нужно, чтобы модифицировать <tex>\Delta_0 </tex> и <tex>\Delta_k</tex>.Теперь мы должны удалить соответствующие листья и на их место поставить те новые , которые появились из-за изменения лучей.

Дальше мы модифицуруем вертикальные лучи, которые пересекают текущий отрезок. Этот процесс происходит достаточно быстро, так мы храним много информацию об этих лучах в .

По -хорошему , то , как этот это происходит , просто ужасно и видеть это этого не хочется, а . А все потому, что много что добавляется добавляет много новых узлов.

<tex>\Delta_0, \Delta_1, \Delta_2 ... \ldots \Delta_k</tex>.

Скажем, что наша точка лежит правее , чем та , которая уже есть. В случаи случае, если мы попали на уже созданный отрезок , мы скажем, что находимся , например , ниже его.

*С геометрической точки зрения , появится еще ещё несколько трапецоидов , как в случааи случае, если бы вновь добавленная точка была правее на <tex> \varepsilon \rightarrow 0</tex>.

*С точки зрения поисковой структуры мы по -прежнему можем локализоваться. По крайней мере , узел , соответствующий точке <tex> p </tex> будет иметь правого сына правым сыном нашу точку. 

Итого, слова "трапецоидные карты просты отсутствие случаев" появляются именно отсюда, так как , казалось бы , неприятный случай будет прописан заменой <tex>\textless </tex>