228
правок
Изменения
Нет описания правки
|statement= Любой face трапецоидной карты ограничен одним или двумя вертикальными отрезками и обязательно двумя не вертикальными отрезками.
}}
[[Файл:Trapezoidmapnavigationshagal.jpg|650px|thumb|right|навигация в трапецоидной карте]]
Именно отсюда берется название стрктуры, так как любой face либо трапеция, либо треугольник.
Тогда <tex>\Delta_1</tex>,<tex>\Delta_2</tex> называют либо большими левыми соседями, либо меньшими.
Хранить трапецоиды можно в чем угодно. Вместе с самим трапецоидом, стоит хранить leftp, rightp, top и bottom так же следует хранить соседей трапецоида.
----
*''Поисковая структура''
Поисковая структура(в дальнейшем <tex> D</tex>) предсталяет из себя ацикличный граф с одним корнем и каждому трапецоиду в структре соответствует один лист.
У каждого узла есль два ребенка и при этом узел может быть двух типов.
[[Файл:Trapezoidmapsearchstructureshagal.jpg|650px|thumb|right|навигация в трапецоидной карте]]
Первый тип узла - точка, соответствующая концу отрезка.
Второй тип узла - отрезок.
Во время запроса мы двигаемся по графу от его корня до момента, когда окажемся в листе, это и будет означать что точка находится внутри трапецоида.
Если мы находимся не в листе, то мы должны опрелетиться в каком из детей мы окажемся дальше.
Еcть два правила:
*Если текущий узел соответсвует вершине, то смотрим левее или провее мы находимся(проверка по x-координате).
*Если текущий узел соответствует отрезку, то смотрим выше или ниже мы находимся(проверка по y-координате).
*Плохие случаи:
Мы находимся на одной вертикале с вершиной
Мы находимся на отрезке
(Решение: молиться, или просто обрабатывать вручную.)
