Трапецоидная карта — различия между версиями
| Строка 2: | Строка 2: | ||
==Постановка задачи== | ==Постановка задачи== | ||
Предположим, у нас есть наши координаты, и есть карта мира. | Предположим, у нас есть наши координаты, и есть карта мира. | ||
| + | |||
Мы можем найти по карте наше местоположение и сказать в какой области мы находимся. | Мы можем найти по карте наше местоположение и сказать в какой области мы находимся. | ||
| + | |||
Области задаются отрезками. | Области задаются отрезками. | ||
| − | + | ===Формальная постановка задачи=== | |
| + | |||
Есть множество отрезков на плоскости. | Есть множество отрезков на плоскости. | ||
| + | |||
Есть запрос (точка q), на выход подается область заданная какими-то отрезками в которой находится q. | Есть запрос (точка q), на выход подается область заданная какими-то отрезками в которой находится q. | ||
| + | |||
==Структура данных== | ==Структура данных== | ||
| − | ===Геометрическая=== | + | |
| − | + | ===Геометрическая=== | |
| − | Мы договариваемся что никакие две точки не лежат на одной вертикале(в противном случаи все еще противнее) | + | У нас есть множество отрезков ограничееных оболочкой R(это не выпуклая оболочка, а просто мнимая граница плоскости за которую не вылезают отрезки) |
| + | |||
| + | Мы договариваемся что никакие две точки не лежат на одной вертикале(в противном случаи все еще противнее) | ||
| + | |||
''Трапецоидная карта'' множества отрезков S - это эти отрезки + из кажой точки выпущены два луча, вверх и вниз до первого пересечения с другим отрезком или с оболочкой R. | ''Трапецоидная карта'' множества отрезков S - это эти отрезки + из кажой точки выпущены два луча, вверх и вниз до первого пересечения с другим отрезком или с оболочкой R. | ||
***картинака*** | ***картинака*** | ||
| Строка 16: | Строка 24: | ||
Именно отсюда берется название стрктуры, так как любой face либо трапеция, либо треугольник. | Именно отсюда берется название стрктуры, так как любой face либо трапеция, либо треугольник. | ||
Введем обозначения для навигации по карте. | Введем обозначения для навигации по карте. | ||
| − | *левая граница(leftp) - точка определяющая левуюы сторону трапецоида или в случаи треугольника просто являющаяся левой вершиной. | + | * левая граница(leftp) - точка определяющая левуюы сторону трапецоида или в случаи треугольника просто являющаяся левой вершиной. |
| − | *правая граница(rightp) - аналогично левой только справа. | + | * правая граница(rightp) - аналогично левой только справа. |
| − | *верхний отрезок(top) и нижний отрезок(bottom) - отрезки ограничивающие трапецоид сверху и снизу. | + | * верхний отрезок(top) и нижний отрезок(bottom) - отрезки ограничивающие трапецоид сверху и снизу. |
| − | + | [[Файл:Trapezoidmapshagal.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 и \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> называют либо большими левыми соседями, либо меньшими. | Тогда <tex>\Delta_1</tex>,<tex>\Delta_2</tex> называют либо большими левыми соседями, либо меньшими. | ||
| Строка 28: | Строка 36: | ||
Теорема о количетве трапецоидов | Теорема о количетве трапецоидов | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
Версия 21:25, 15 февраля 2012
Трапецоидная карта - геометрическая структура позволяющая локализоваться на площади за .
Постановка задачи
Предположим, у нас есть наши координаты, и есть карта мира. Мы можем найти по карте наше местоположение и сказать в какой области мы находимся. Области задаются отрезками. ===Формальная постановка задачи===
Есть множество отрезков на плоскости.
Есть запрос (точка q), на выход подается область заданная какими-то отрезками в которой находится q.
Структура данных
===Геометрическая=== У нас есть множество отрезков ограничееных оболочкой R(это не выпуклая оболочка, а просто мнимая граница плоскости за которую не вылезают отрезки)
Мы договариваемся что никакие две точки не лежат на одной вертикале(в противном случаи все еще противнее)
Трапецоидная карта множества отрезков S - это эти отрезки + из кажой точки выпущены два луча, вверх и вниз до первого пересечения с другим отрезком или с оболочкой R. ***картинака*** !!!Очевидный факт - любой face трапецоидной карты ограничен одним или двумя вертикальными отрезками и обязательно двумя не вертикальными отрезками. Именно отсюда берется название стрктуры, так как любой face либо трапеция, либо треугольник. Введем обозначения для навигации по карте. * левая граница(leftp) - точка определяющая левуюы сторону трапецоида или в случаи треугольника просто являющаяся левой вершиной. * правая граница(rightp) - аналогично левой только справа. * верхний отрезок(top) и нижний отрезок(bottom) - отрезки ограничивающие трапецоид сверху и снизу.
Файл:Trapezoidmapshagal.jpg
трапецоидная карта
* трапецоиды называются смежными, если имеют общую вертикальную границу. * пусть смежны и либо top() = top(), либо bottom() = bottom()
Тогда , называют либо большими левыми соседями, либо меньшими. Хранить трапецоиды можно в чем угодно. Вместе с самим трапецоидом, стоит хранить leftp, rightp, top и bottom так же следует хранить соседей трапецоида.
Теорема о количетве трапецоидов
