Трапецоидная карта {{---}} структура данных для локализации в конфигурации отрезков.
==Постановка задачи==
<wikitex>{{Определение|id=arrangement|definition ='''Конфигурацией''' (англ. ''arrangement'') $\mathcal{A}(\mathcal{H})$ называется разбиение $\mathbb{R}^d$ в связные открытые(топологически) области размерностей $0, 1 \dots d $ множеством $\mathcal{H}$ гиперплоскостей в $ \mathbb{R}^d$.}} {{Определение|id=cell|definition ='''Ячейкой''' (англ. ''cell'') размерности $d$ в $\mathcal{A}(\mathcal{H})$ называется максимальная связная область в $R^d$, не пересекаемая ни одной гиперплоскостью в $\mathcal{H}$. <br>Ячейкой размерности $k$, где $0 \le k < d$ в $\mathcal{A}(\mathcal{H})$ называется максимальная связная область в пересечении гиперплоскостей подмножества $\mathcal{S} \in \mathcal{H}$, которая не пересекается ни одной гиперплоскостью из множества $\mathcal{H} \setminus \mathcal{S}$.<br>В случае ограниченных гиперплоскостей, ячейками соответствующих размерностей также считаются точки, отрезки (лучи), грани Есть конфигурация отрезков на плоскости и прочие вплоть до размерности $k dcel- 1$подобная структура, $i$-мерные объекты, ограничивающие их.}} {{Определение|id=primitives|definition ='''Вершина''' (англ. ''vertex'') — ячейка размерности 0. <br>'''Ребро''' (англ. ''edge'') — ячейка размерности 1. <br>'''Грань''' (англ. ''позволяющая по ребру из конфигурации получить соответствующий face'') — ячейка размерности 2. <br>'''Сторона''' (англ. ''facet'') — ячейка размерности d-1.}} </wikitex>ПредположимТрапецоидная карта позволяет найти ребро, у нас есть наши координаты, и есть двумерная конфигурация. Наша задача выдать грань содержащую точку. Пусть каждая грань конфигурации является трапецоидом. Тогда каждая грань однозначно задается двумя отрезками ограничивающими эту грань(боковые стороны трапеции).Таким образом задача локализации до которого можно дойти от точки сводится к тому-запроса, что нужно выдать два отрезка между которыми находится точкане пересекая образующие конфигурацию отрезки.
==Структура данных==
