Проблема местоположения точки - фундаментальная тема вычислительной геометрии . Он находит приложения в областях, связанных с обработкой геометрических данных: компьютерная графика , географические информационные системы (ГИС), планирование движения и компьютерное проектирование (САПР).
В самом общем виде задача состоит в том, чтобы при разбиении пространства на непересекающиеся области определить область, в которой находится точка запроса. В качестве примера приложения, каждый раз, когда кто-то щелкает мышью, чтобы перейти по ссылке в веб-браузере , эта проблема должна быть решена, чтобы определить, какая область экрана компьютера находится под указателем мыши. Простым частным случаем является задача о точке в многоугольнике . В этом случае нам нужно определить, находится ли точка внутри, снаружи или на границе одного многоугольника.
Во многих приложениях нам необходимо определить расположение нескольких разных точек по отношению к одному и тому же разделу пространства. Для эффективного решения этой проблемы полезно построить структуру данных, которая, учитывая точку запроса, быстро определяет, в каком регионе содержится точка запроса (например, диаграмма Вороного ).
Плоский корпус
В плоском случае нам дается планарное подразделение S , образованное несколькими многоугольниками, называемыми гранями, и нам нужно определить, какая грань содержит точку запроса. Поиск грубой силы каждой грани , используя точки в многоугольнике алгоритм можно, но , как правило , не представляется возможный для подразделений высокой сложности. Несколько различного подход приводит к оптимальным структурам данных, с О ( п пространства) для хранения и вывод (лог - п ) время запроса, где п представляет собой общее количество вершин в S . Для простоты мы предполагаем, что планарное подразделение содержится внутри квадратного ограничивающего прямоугольника.
Разложение плиты
Простая и ранняя структура данных для достижения O (журнал N ) время было обнаружено Добкиным и Lipton в 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 (1) раз. Каждый треугольник имеет указатели на треугольники, которые он пересекает на следующем уровне иерархии, и количество указателей также ограничено константой. Мы продолжаем запрос, определяя, какой треугольник содержит точку запроса, уровень за уровнем.
Структура данных строится в обратном порядке, то есть снизу вверх. Мы начинаем с триангулированного подразделения и выбираем независимый набор вершин, которые нужно удалить. После удаления вершин мы повторно триангулируем подразделение. Поскольку подразделение состоит из треугольников, жадный алгоритм может найти независимый набор, содержащий постоянную долю вершин. Следовательно, количество шагов удаления равно O (log n ).
Трапециевидное разложение
Рандомизированное подход к этой проблеме, и , вероятно , наиболее практический характер , основывается на трапециевидной разложении , или трапециевидной карте. Трапецеидальное разложение получается путем стрельбы вертикальными пулями, идущими как вверх, так и вниз из каждой вершины в исходном подразделении. Пули останавливаются, когда попадают в край, и образуют новый край в подразделении. Таким образом, мы получаем подмножество декомпозиции плиты, состоящее только из O ( n ) ребер и вершин, поскольку для каждой вершины в исходном разбиении мы добавляем только две новые вершины и увеличиваем количество ребер на четыре.
Непросто понять, как использовать трапециевидное разложение для определения местоположения точки, поскольку двоичный поиск, аналогичный тому, который используется в разложении плиты, больше не может выполняться. Вместо этого нам нужно ответить на запрос так же, как при подходе к уточнению триангуляции, но структура данных строится сверху вниз. Первоначально мы строим трапециевидную декомпозицию, содержащую только ограничивающую рамку, но без внутренней вершины. Затем мы добавляем сегменты из подразделения один за другим в случайном порядке, уточняя трапециевидное разложение. Используя обратный анализ , мы можем показать, что ожидаемое количество трапеций, созданных для каждой вставки, ограничено константой.
Мы строим ориентированный ациклический граф , вершины которого - это трапеции, существовавшие в какой-то момент уточнения, а направленные ребра соединяют трапеции, полученные в результате разбиения. Ожидаемая глубина поиска в этом орграфе, начиная с вершины, соответствующей ограничивающему прямоугольнику, составляет O (log n ) [ требуется пояснение ] .
Высшие измерения
Нет известных общих структур данных точечного местоположения с линейным пространством и логарифмическим временем запроса для измерений больше 2 [ необходима ссылка ] . Следовательно, нам нужно пожертвовать либо временем запроса, либо пространством для хранения, либо ограничиться каким-то менее общим типом подразделения.
В трехмерном пространстве можно ответить на запросы о местоположении точки в O (log² n ), используя пространство O ( n log n ). Общая идея состоит в том, чтобы поддерживать несколько структур данных местоположения плоских точек, соответствующих пересечению подразделения с n параллельными плоскостями, которые содержат каждую вершину подразделения. Наивное использование этой идеи увеличило бы объем памяти до O ( n ²). Таким же образом, как и при декомпозиции slab, можно использовать сходство между последовательными структурами данных, чтобы уменьшить пространство для хранения до O ( n log n ), но время запроса увеличивается до O (log² n ). [ необходима цитата ]
В d- мерном пространстве местоположение точки может быть решено путем рекурсивного проецирования граней в ( d -1) -мерное пространство. Хотя время запроса равно O (log n ), объем памяти может достигать. Высокая сложность d- мерных структур данных привела к изучению специальных типов подразделения.
Одним из важных примеров является случай расположения гиперплоскостей . Расположение п Гиперплоскость определяет О ( п д ) клетка, но положение точки может быть выполнено в O (журнал п ) время с О ( п г ) пространства с использованием Chazelle иерархические «ы шлама .
Другой особый тип деления называется прямолинейным (или ортогональным) делением. При прямолинейном делении все ребра параллельны одной из ортогональных осей d . В этом случае на определение местоположения точки можно ответить за время O (log d -1 n ) с интервалом O ( n ).
Рекомендации
- де Берг, Марк; ван Кревельд, Марк; Овермарс, Марк ; Шварцкопф, Отфрид (2000). «Глава 6: Местоположение точки». Вычислительная геометрия (2-е изд., Перераб.). Springer-Verlag . С. 121–146 . ISBN 3-540-65620-0.
- Добкин, Дэвид ; Липтон, Ричард Дж. (1976). «Многомерные поисковые задачи». SIAM Journal on Computing . 5 (2): 181–186. DOI : 10.1137 / 0205015 .
- Snoeyink, Джек (2004). Глава 34: «Местоположение точки». В Goodman, Jacob E .; O'Rourke, Joseph (eds.). Handbook of Discrete and Computational Geometry (2 ed.). Chapman & Hall / CRC. ISBN 1-58488-301-4.
- Сарнак, Нил; Тарджан, Роберт Э. (1986). «Расположение точек на плоскости с использованием постоянных деревьев поиска». Коммуникации ACM . 29 (7): 669–679. DOI : 10.1145 / 6138.6151 .
- Эдельсбруннер, Герберт ; Гибас, Леонидас Дж .; Столфи, Хорхе (1986). «Оптимальное расположение точки на монотонном участке». SIAM Journal on Computing . 15 (2): 317–340. DOI : 10.1137 / 0215023 .
- Киркпатрик, Дэвид Г. (1983). «Оптимальный поиск в плоских сечениях». SIAM Journal on Computing . 12 (1): 28–35. CiteSeerX 10.1.1.461.1866 . DOI : 10.1137 / 0212002 .
Внешние ссылки
- Репозиторий источников Point-Location в Университете Стони Брук
- Запросы местоположения точек в CGAL , библиотеке алгоритмов вычислительной геометрии