228
правок
Изменения
→Структура данных
|statement= Любой <tex>\operatorname{face}</tex> трапецоидной карты ограничен одним или двумя вертикальными отрезками и обязательно двумя не вертикальными отрезками.
}}
[[Файл:Trapezoidmapnavigationshagal.jpgpng|650px|thumb|right|навигация в трапецоидной карте]]
Именно отсюда берется название структуры, так как любой <tex>\operatorname{face}</tex> либо трапеция, либо треугольник.
|proof=
*''вершины'', а точнее откуда они берутся.
**4 вершины уходит на оболочку <tex>R</tex>
**<tex>2 \cdot n</tex> концы отрезков
----
[[Файл:Trapezoidmapsearchstructureshagal.png|650px|thumb|right|навигация в трапецоидной карте]]
*''Поисковая структура''
Поисковая структура представляет из себя ациклический граф с одним корнем и соответствующими трапецоидам листьями.
У каждого узла есть два ребенка. При этом узел может быть двух типов.
*Первый тип узла - точка, соответствующая концу отрезка.
Если мы находимся не в листе, то мы должны опредетиться, в каком из детей мы окажемся дальше.
Еcть два правила:
