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