Местоположение точки

Проблема расположения точек является фундаментальной темой вычислительной геометрии . Он находит применение в областях, связанных с обработкой геометрических данных: компьютерная графика , географические информационные системы (ГИС), планирование движения и компьютерное проектирование (САПР).

В самом общем виде задача состоит в том, чтобы при разделении пространства на непересекающиеся области определить область, в которой находится точка запроса. Например, проблему определения того, какое окно графического пользовательского интерфейса содержит данный щелчок мыши, можно сформулировать как случай расположения точки с подразделением, образованным видимыми частями каждого окна, хотя специализированные структуры данных могут быть более подходящими, чем структуры данных о местоположении точек общего назначения в этом приложении. Другим особым случаем является задача «точка в многоугольнике» , в которой необходимо определить, находится ли точка внутри, снаружи или на границе одного многоугольника .

Во многих приложениях необходимо определить расположение нескольких разных точек относительно одного и того же раздела пространства. Чтобы эффективно решить эту проблему, полезно построить структуру данных , которая по заданной точке запроса быстро определяет, какой регион содержит точку запроса (например, диаграмма Вороного ).

Плоский случай

Плоское подразделение внутри ограничивающей рамки

В плоском случае нам дано плоское подразделение S , образованное несколькими многоугольниками, называемыми гранями, и нам нужно определить, какая грань содержит точку запроса. Перебор алгоритма каждой грани с использованием «точка в многоугольнике» возможен, но обычно неосуществим для подразделений высокой сложности. Несколько различных подходов приводят к оптимальным структурам данных с O ( n O(log n ) и временем запроса ), где n — общее количество вершин в S. объемом памяти Для простоты мы предполагаем, что плоское подразделение содержится внутри квадратной ограничивающей рамки.

Разложение плиты

Плоское подразделение, разделенное на плиты.

Самая простая и ранняя структура данных для достижения времени O(log n ) была обнаружена Добкиным и Липтоном в 1976 году. Она основана на подразделении S с использованием вертикальных линий, проходящих через каждую вершину S. в Область между двумя последовательными вертикальными линиями называется плитой . Обратите внимание, что каждая плита разделена непересекающимися отрезками линий, которые полностью пересекают плиту слева направо. Область между двумя последовательными сегментами внутри плиты соответствует уникальной S. грани Поэтому мы сводим нашу задачу о расположении точек к двум более простым задачам:

1. Учитывая разделение плоскости на вертикальные плиты, определите, какая плита содержит данную точку.
2. Дана плита, разделенная на области непересекающимися отрезками, полностью пересекающими плиту слева направо, определить, в какой области находится данная точка.

Первую проблему можно решить с помощью двоичного поиска по координате 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 ).

Высшие измерения

Не существует известных общих структур данных о местоположении точек с линейным пространством и логарифмическим временем запроса для размерностей больше 2. . Поэтому нам нужно пожертвовать либо временем запроса, либо пространством хранения, либо ограничиться каким-то менее общим типом подразделения.

В трехмерном пространстве можно отвечать на запросы о местоположении точек за O(log² n ), используя O( n log n пространство ). Общая идея состоит в том, чтобы поддерживать несколько структур данных о местоположении плоских точек, соответствующих пересечению подразделения с n параллельными плоскостями, содержащими каждую вершину подразделения. Наивное использование этой идеи увеличило бы объем памяти до O( n² ). Так же, как и при слябовой декомпозиции, сходство между последовательными структурами данных можно использовать для уменьшения объема памяти до O( n log n ), но время запроса увеличивается до O(log² n ).

В d -мерном пространстве местоположение точки можно решить путем рекурсивного проецирования граней в ( d -1)-мерное пространство. Хотя время запроса равно O(log n ), объем памяти может достигать $O(n^{2^{d}})$. Высокая сложность d -мерных структур данных привела к изучению специальных типов подразделения.

Одним из важных примеров является случай расположения гиперплоскостей . Расположение n гиперплоскостей определяет O( n ^д ) ячеек, но местоположение точки может быть выполнено за время O(log n ) с помощью O( n ^д ) пространство с использованием Шазель иерархических вырезок .

Другой особый тип подразделения называется прямолинейным (или ортогональным) подразделением. В прямолинейном подразделении все ребра параллельны одной из ортогональных осей d . В этом случае на местоположение точки можно ответить за O(log ^{д -1} n ) время с пространством O( n ).

Ссылки

Источники

• де Берг, Марк; ван Кревелд, Марк; Овермарс, Марк ; Шварцкопф, Отфрид (2000). «Глава 6: Расположение точки». Вычислительная геометрия (2-е исправленное изд.). Издательство Спрингер . стр. 121–146 . ISBN  3-540-65620-0 .
• Берн, Маршалл (1990). «Удаление скрытых поверхностей для прямоугольников» . Журнал компьютерных и системных наук . 40 (1): 49–69. дои : 10.1016/0022-0000(90)90018-G . МР   1047289 .
• Добкин, Дэвид ; Липтон, Ричард Дж. (1976). «Многомерные задачи поиска». SIAM Journal по вычислительной технике . 5 (2): 181–186. дои : 10.1137/0205015 .
• Эдельсбруннер, Герберт ; Гибас, Леонидас Дж .; Столфи, Хорхе (1986). «Оптимальное расположение точки в монотонном подразделении». SIAM Journal по вычислительной технике . 15 (2): 317–340. дои : 10.1137/0215023 .
• Киркпатрик, Дэвид Г. (1983). «Оптимальный поиск в плоских подразделениях». SIAM Journal по вычислительной технике . 12 (1): 28–35. CiteSeerX   10.1.1.461.1866 . дои : 10.1137/0212002 .
• Сарнак, Нил; Тарьян, Роберт Э. (1986). «Расположение плоской точки с использованием постоянных деревьев поиска» . Коммуникации АКМ . 29 (7): 669–679. дои : 10.1145/6138.6151 .

Дальнейшее чтение

• Снойинк, Джек (2004). Глава 34: «Расположение точки». В книге Гудман, Джейкоб Э .; О'Рурк, Джозеф (ред.). Справочник по дискретной и вычислительной геометрии (2-е изд.). Чепмен и Холл / CRC. ISBN.  1-58488-301-4 .

Внешние ссылки

• Репозиторий источников точечного местоположения в Университете Стоуни-Брук
• Запросы местоположения точек в CGAL , библиотеке алгоритмов вычислительной геометрии