Изменения

Трапецоидная карта {{- --}} геометрическая структура позволяющая локализоваться на площади за <tex>\mathcal{O}(\log(n))</tex>.

Есть запрос (точка <tex>q</tex>), на выходе {{---}} область, в которой находится точка <tex>q</tex>.

[[Файл:Trapazoidmapshagal.jpg|650px|thumb|right|трапецоидная карта]]

У нас есть множество отрезков , ограниченных оболочкой <tex>R</tex>(это не выпуклая оболочка, а просто мнимая граница плоскости , за которую не вылезают отрезки). Мы договариваемся , что никакие две точки не лежат на одной вертикале(в противном случаи все еще противнее).

''Трапецоидная карта'' множества отрезков <tex>S </tex> {{- --}} это эти отрезки + и из каждой точки выпущены два луча, {{---}} вверх и вниз , до первого пересечения с другим отрезком или с оболочкой <tex>R</tex>.

|statement= Любой <tex>\operatorname{face }</tex> трапецоидной карты ограничен одним или двумя вертикальными отрезками и обязательно двумя не вертикальными отрезками.

Именно отсюда берется название структуры, так как любой <tex>\operatorname{face }</tex> либо трапеция, либо треугольник.

*''левая граница'' (<tex>\operatorname{leftp}</tex>) {{--- }} точка , определяющая левую сторону трапецоида или , в случаи треугольника , просто являющаяся левой вершиной.*''правая граница'' (<tex>\operatorname{rightp}</tex>) {{--- }} аналогично левой , только справа. *''верхний отрезок'' (<tex>\operatorname{top}</tex>) и нижний отрезок(<tex>\operatorname{bottom}</tex>) {{- --}} отрезки , ограничивающие , трапецоид сверху и снизу. *трапецоиды называются ''смежными'', если имеют общую вертикальную границу. *пусть <tex>\Delta_1 </tex> и <tex>\Delta_2</tex> смежны и либо top(<tex>\operatorname{top}(\Delta_1</tex>) = \operatorname{top}(<tex>\Delta_2)</tex>), либо bottom(<tex>\operatorname{bottom}(\Delta_1</tex>) = \operatorname{bottom}(<tex>\Delta_2)</tex>) . Тогда <tex>\Delta_1</tex>,и <tex>\Delta_2</tex> называют либо нижними левыми соседями, либо верхнимилевыми соседями.

|statement=Трапецоидная карта , построенная на <tex>n </tex> отрезках содержит максимум <tex>6n+4 </tex> вершины и максимум <tex>3n+1 </tex> трапецоид.

**4 вершины уходит на оболочку <tex>R.</tex>

У каждого трапецоида есть точка leftp(<tex>\operatorname{leftp}(\Delta)</tex>). Либо это конец какого-то отрезка, либо это левый нижний угол оболочки.

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

Далее заметим, что правый конец отрезка может быть leftp(<tex>\operatorname{leftp}(\Delta)</tex>) только для одного трапецоида.

Левый конец может быть leftp(<tex>\operatorname{leftp}(\Delta)</tex>) максимум для двух трапецоидов.

Хранить трапецоиды можно в чем угодно. Вместе с самим трапецоидом, стоит хранить <tex>\operatorname{leftp}</tex>, <tex>\operatorname{rightp}</tex>, <tex>\operatorname{top }</tex> и <tex>\operatorname{bottom так }</tex>. Так же следует хранить соседей трапецоида.