Мы можем найти по карте наше местоположение и сказать в какой области мы находимся.
Области задаются отрезками.
Области задаются '''Формальная постановка задачи''' Есть множество отрезков на плоскости. Есть запрос (точка q), на выход подается область заданная какими-то отрезкамив которой находится q. ===Формальная постановка задачи=Структура данных==
Есть множество отрезков на плоскости.
Есть запрос (точка q), на выход подается область заданная какими-то отрезками в которой находится q.
==Структура данных==*''Геометрическая''
===Геометрическая=== У нас есть множество отрезков ограничееных оболочкой R(это не выпуклая оболочка, а просто мнимая граница плоскости за которую не вылезают отрезки) Мы договариваемся что никакие две точки не лежат на одной вертикале(в противном случаи все еще противнее)
Мы договариваемся что никакие две ''Трапецоидная карта'' множества отрезков S - это эти отрезки + из кажой точки не лежат на одной вертикале(в противном случаи все еще противнее)выпущены два луча, вверх и вниз до первого пересечения с другим отрезком или с оболочкой R.
''Трапецоидная карта'' множества отрезков S {{Лемма - это эти отрезки + из кажой точки выпущены два луча, вверх и вниз до первого пересечения с другим отрезком или с оболочкой R. ***картинака*** !!!Очевидный факт - любой |statement= Любой face трапецоидной карты ограничен одним или двумя вертикальными отрезками и обязательно двумя не вертикальными отрезками.}} [[Файл:Trapazoidmapshagal.jpg|650px|thumb|right|трапецоидная карта]]
Именно отсюда берется название стрктуры, так как любой face либо трапеция, либо треугольник.
Введем обозначения для навигации по карте. * левая граница(leftp) - точка определяющая левуюы сторону трапецоида или в случаи треугольника просто являющаяся левой вершиной. * правая граница(rightp) - аналогично левой только справа. * верхний отрезок(top) и нижний отрезок(bottom) - отрезки ограничивающие трапецоид сверху и снизу. *трапецоиды называются смежными, если имеют общую вертикальную границу. *пусть <tex>\Delta_1 и \Delta_2</tex> смежны и либо top(<tex>\Delta_1</tex>) = top(<tex>\Delta_2</tex>), либо bottom(<tex>\Delta_1</tex>) = bottom(<tex>\Delta_2</tex>) [[Файл:TrapezoidmapshagalТогда <tex>\Delta_1</tex>,<tex>\Delta_2</tex> называют либо большими левыми соседями, либо меньшими.jpg|400px|thumb|right|трапецоидная карта]]
* трапецоиды называются смежными, если имеют общую вертикальную границу. * пусть <tex>\Delta_1 и \Delta_2</tex> смежны и либо top(<tex>\Delta_1</tex>) = top(<tex>\Delta_2</tex>), либо bottom(<tex>\Delta_1</tex>) = bottom(<tex>\Delta_2</tex>) Тогда <tex>\Delta_1</tex>,<tex>\Delta_2</tex> называют либо большими левыми соседями, либо меньшими. Хранить трапецоиды можно в чем угодно. Вместе с самим трапецоидом, стоит хранить leftp, rightp, top и bottom так же следует хранить соседей трапецоида. Теорема о количетве трапецоидов
