Задача определения местоположения точки является фундаментальной темой вычислительной геометрии . Она находит применение в областях, связанных с обработкой геометрических данных: компьютерная графика , географические информационные системы (ГИС), планирование движения и автоматизированное проектирование (САПР).
В наиболее общем виде задача заключается в том, чтобы, имея разбиение пространства на непересекающиеся области, определить область, в которой находится точка запроса. Например, задача определения того, какое окно графического пользовательского интерфейса содержит заданный щелчок мыши, может быть сформулирована как пример местоположения точки с подразделением, образованным видимыми частями каждого окна, хотя специализированные структуры данных могут быть более подходящими, чем структуры данных местоположения точки общего назначения в этом приложении. [1] Другим особым случаем является задача точки в многоугольнике , в которой необходимо определить, находится ли точка внутри, снаружи или на границе одного многоугольника .
Во многих приложениях необходимо определить местоположение нескольких различных точек относительно одного и того же раздела пространства. Для эффективного решения этой проблемы полезно построить структуру данных , которая, учитывая точку запроса, быстро определяет, какой регион содержит точку запроса (например, диаграмма Вороного ).
В плоском случае нам дано плоское подразделение S , образованное несколькими полигонами, называемыми гранями, и нам нужно определить, какая грань содержит точку запроса. Поиск методом грубой силы каждой грани с использованием алгоритма «точка в полигоне» возможен, но обычно нецелесообразен для подразделений высокой сложности. Несколько различных подходов приводят к оптимальным структурам данных с O ( n ) дисковым пространством и O(log n ) временем запроса, где n — общее количество вершин в S . Для простоты мы предполагаем, что плоское подразделение содержится внутри квадратной ограничивающей рамки.
Самая простая и ранняя структура данных, позволяющая достичь времени O(log n ), была открыта Добкиным и Липтоном в 1976 году. Она основана на подразделении S с помощью вертикальных линий, проходящих через каждую вершину в S . Область между двумя последовательными вертикальными линиями называется плитой . Обратите внимание, что каждая плита разделена непересекающимися отрезками линий, которые полностью пересекают плиту слева направо. Область между двумя последовательными отрезками внутри плиты соответствует уникальной грани S . Поэтому мы сводим нашу задачу определения местоположения точки к двум более простым задачам: [2]
Первая задача может быть решена бинарным поиском по координате x вертикальных линий за время O(log n ). Вторая задача также может быть решена за время O(log n ) бинарным поиском. Чтобы увидеть, как это сделать, обратите внимание, что, поскольку сегменты не пересекаются и полностью пересекают плиту, сегменты могут быть отсортированы по вертикали внутри каждой плиты. Хотя этот алгоритм позволяет определять местоположение точек за логарифмическое время и прост в реализации, пространство, необходимое для построения плит и областей, содержащихся внутри плит, может достигать O( n ²), поскольку каждая плита может пересекать значительную часть сегментов. [2]
Несколько авторов заметили, что сегменты, пересекающие две соседние плиты, в основном одинаковы. Поэтому размер структуры данных может быть значительно уменьшен. Более конкретно, Сарнак и Тарьян проводят вертикальную линию l слева направо по плоскости, сохраняя сегменты, пересекающие l, в постоянном красно-черном дереве . Это позволяет им уменьшить объем памяти до O( n ), сохраняя при этом время запроса O(log n ). [3]
(Вертикальная) монотонная цепь — это путь, такой, что координата y никогда не увеличивается вдоль пути. Простой многоугольник является (вертикальным) монотонным, если он образован двумя монотонными цепями с общей первой и последней вершиной. Можно добавить несколько ребер к плоскому подразделению, чтобы сделать все грани монотонными, получив то, что называется монотонным подразделением. Этот процесс не добавляет никаких вершин к подразделению (следовательно, размер остается O( n )), и может быть выполнен за время O( n log n ) путем плоскостной развертки (его также можно выполнить за линейное время, используя триангуляцию многоугольника ). Поэтому нет потери общности, если мы ограничим нашу структуру данных случаем монотонных подразделений, как мы делаем в этом разделе.
Слабость разложения плит заключается в том, что вертикальные линии создают дополнительные сегменты в разложении, что затрудняет достижение O( n ) пространства хранения. Герберт Эдельсбруннер , Леонидас Дж. Гибас и Хорхе Столфи открыли оптимальную структуру данных, которая использует только ребра в монотонном подразделении. Идея заключается в использовании вертикальных монотонных цепей вместо использования вертикальных линий для разбиения подразделения. [4]
Преобразование этой общей идеи в фактическую эффективную структуру данных — непростая задача. Во-первых, нам нужно уметь вычислять монотонную цепочку, которая делит подразделение на две половины схожих размеров. Во-вторых, поскольку некоторые ребра могут содержаться в нескольких монотонных цепочках, нам нужно быть осторожными, чтобы гарантировать, что пространство для хранения равно O(n). В-третьих, проверка того, находится ли точка на левой или правой стороне монотонного подразделения, занимает O( n ) времени, если выполняется наивно. [4]
Подробности решения первых двух проблем выходят за рамки этой статьи. Мы кратко упомянем, как решить третью проблему. Используя бинарный поиск, мы можем проверить, находится ли точка слева или справа от монотонной цепи за время O(log n ). Поскольку нам нужно выполнить еще один вложенный бинарный поиск по цепям O(log n ), чтобы фактически определить местоположение точки, время запроса составляет O(log² n). Чтобы достичь времени запроса O(log n ), нам нужно использовать дробное каскадирование , сохраняя указатели между краями различных монотонных цепей. [4]
Многоугольник с m вершинами можно разбить на m –2 треугольников. Это можно показать индукцией , начинающейся с треугольника. Существует множество алгоритмов для эффективной триангуляции многоугольника , самый быстрый из которых имеет время O( n ) в худшем случае. Поэтому мы можем разложить каждый многоугольник нашего подразделения на треугольники и ограничить нашу структуру данных случаем подразделений, образованных исключительно треугольниками. Киркпатрик дает структуру данных для расположения точек в триангулированных подразделениях с O( n ) дискового пространства и временем запроса O(log n ). [5]
Общая идея заключается в построении иерархии треугольников. Для выполнения запроса мы начинаем с поиска треугольника верхнего уровня, который содержит точку запроса. Поскольку количество треугольников верхнего уровня ограничено константой, эта операция может быть выполнена за время O(1). Каждый треугольник имеет указатели на треугольники, которые он пересекает на следующем уровне иерархии, и количество указателей также ограничено константой. Мы продолжаем запрос, находя, какой треугольник содержит точку запроса уровень за уровнем. [5]
Структура данных строится в обратном порядке, то есть снизу вверх. Мы начинаем с триангулированного подразделения и выбираем независимый набор вершин для удаления. После удаления вершин мы повторно триангулируем подразделение. Поскольку подразделение образовано треугольниками, жадный алгоритм может найти независимый набор, содержащий постоянную долю вершин. Следовательно, количество шагов удаления равно O(log n ). [5]
Рандомизированный подход к этой проблеме основан на трапециевидной декомпозиции или трапециевидной карте. Трапециевидная декомпозиция получается путем стрельбы вертикальными пулями, идущими как вверх, так и вниз из каждой вершины в исходном подразделении. Пули останавливаются, когда они попадают в ребро, и формируют новое ребро в подразделении. Таким образом, мы получаем подмножество разложения плиты, только с O( n ) ребрами и вершинами, поскольку для каждой вершины в исходном подразделении мы добавляем только две новые вершины и увеличиваем количество ребер на четыре. [6]
Трапециевидное разложение может быть построено путем добавления сегментов из исходного подразделения, один за другим, в случайном порядке. Первоначально (до того, как сегменты не были добавлены) трапециевидное разложение состоит из одной трапеции, ограничивающего прямоугольника подразделения. Каждый последующий шаг использует запрос местоположения точки для определения одной конечной точки следующего сегмента линии в текущем трапециевидном разложении, а затем идет от полученной трапеции к соседним трапециям, содержащим тот же сегмент, подразделяя и рекомбинируя их для формирования уточненного разложения. Обратный анализ, форма анализа, обычно используемая для этого вида рандомизированного инкрементального геометрического алгоритма, показывает, что ожидаемое количество трапеций, созданных для каждой вставки, ограничено константой, и, следовательно, что общее количество шагов этого алгоритма, за пределами местоположений точек, является линейным. [6]
Расположение точек в текущем подразделении, выполняемое в рамках этого алгоритма, может быть выполнено с использованием той же структуры, которая в конце алгоритма может быть использована для запросов местоположения точек в окончательном трапециевидном разложении. Эта структура данных местоположения точек принимает форму направленного ациклического графа , где вершинами являются трапеции, которые существовали в некоторой точке уточнения, а направленные ребра соединяют каждую трапецию, которая больше не находится в уточнении, с трапециями, которые ее заменили. Запрос местоположения точек выполняется путем следования по пути в этом графе, начиная с начальной трапеции, и на каждом шаге выбирая заменяющую трапецию, которая содержит точку запроса, пока не достигнет трапеции, которая не была заменена. Ожидаемая глубина поиска в этом орграфе, начиная с любой точки запроса, составляет O(log n ). Пространство для структуры данных пропорционально количеству трапеций, созданных в ходе этого процесса уточнения, которое в ожидании составляет O( n ). [6]
Не существует известных общих структур данных о местоположении точек с линейным пространством и логарифмическим временем запроса для измерений больше 2 [ требуется ссылка ] . Поэтому нам нужно пожертвовать либо временем запроса, либо пространством хранения, либо ограничиться каким-то менее общим типом подразделения.
В трехмерном пространстве можно отвечать на запросы о местоположении точек за O(log² n ), используя O( n log n ) пространства. Общая идея заключается в том, чтобы поддерживать несколько планарных структур данных о местоположении точек, соответствующих пересечению подразделения с n параллельными плоскостями, которые содержат каждую вершину подразделения. Наивное использование этой идеи увеличило бы пространство хранения до O( n ²). Таким же образом, как и в разложении плиты, сходство между последовательными структурами данных может быть использовано для того, чтобы уменьшить пространство хранения до O( n log n ), но время запроса увеличивается до O(log² n ). [7]
В d -мерном пространстве местоположение точки может быть решено путем рекурсивного проецирования граней в ( d -1) -мерное пространство. В то время как время запроса составляет O(log n ), пространство для хранения может достигать . Высокая сложность d -мерных структур данных привела к изучению специальных типов подразделений.
Одним из важных примеров является случай расположений гиперплоскостей . Расположение n гиперплоскостей определяет O( n d ) ячеек, но расположение точек может быть выполнено за время O(log n ) с O( n d ) пространством с использованием иерархических разрезов Шазелла .
Другой специальный тип подразделения называется прямолинейным (или ортогональным) подразделением. В прямолинейном подразделении все ребра параллельны одной из ортогональных осей d . В этом случае определение местоположения точки может быть выполнено за время O(log d -1 n ) с использованием пространства O( n ).
