Контейнер линейного сегмента для быстрого пересечения лучей? (2D)
У меня есть луч, мне нужно найти ближайший отрезок, который он попадает. Я думаю, что можно сделать это за O(log n), если я сначала отсортирую отрезки, но я не могу вспомнить, как их сортировать... Я думаю, что какое-то дерево будет работать лучше, но как мне отсортировать их как начальной, так и конечной точкой? Я также хотел бы быстрые вставки в эту структуру данных, если это возможно.
Существует много кода для одного луча против одного отрезка, но мне нужно кое-что для одного луча против множества отрезков... Я не знаю, какие термины использовать в Google.
Ссылка на соответствующую статью хорошая, код на C++ еще лучше. Спасибо!:)
PS: Сегменты линии на самом деле являются краями несамопересекающегося многоугольника, отсортированного по порядку CCW... но я думаю, что может быть какое-то преимущество в их сортировке по-другому?
Это все 2D.
Если подумать, я не совсем уверен, что это возможно. Может помочь какое-то пространственное разбиение, но в остальном я не могу придумать способ сортировки линий, чтобы их можно было сравнивать с произвольным лучом.
5 ответов
Вы можете взять ограничивающий прямоугольник многоугольника (min-max x,y координаты) и построить сетку внутри прямоугольника. Затем для каждой ячейки запомните все линии, которые пересекают ячейку.
Найдите пересечение как это:
- Узнайте, в какую клетку луч попадает первым (O(1))
- Используйте алгоритм обхода сетки, чтобы "нарисовать" луч через сетку. Когда вы нажмете на непустую ячейку, проверьте все ее линии, проверьте, находится ли пересечение внутри ячейки, и выберите самое близкое пересечение. Если все пересечения находятся за пределами ячейки, продолжайте (это O (длина сетки)).
Вы также можете сделать иерархическую сетку (то есть quadtree - дерево, о котором вы просили) и пройти по нему, используя тот же алгоритм. Это делается в трассировке лучей в 3D, а временная сложность составляет O(sqrt(N)).
Или используйте подход, который я использовал в моем raytracer:
- Создайте квадродерево, содержащее линии (построение квадродерева описано в статье) - вы разделяете узлы (= области), если они содержат слишком много объектов, на 4 подузла (подобласти)
Соберите все листовые узлы дерева квадратов, которые попали под луч:
Вычислить пересечение луча с прямоугольником (не сложно) для корня. Если луч поражен корнем, рекурсивно продолжите работу с его дочерними элементами.
Крутая вещь в этом заключается в том, что когда узел дерева не ударил, вы пропустили обработку всего поддерева (потенциально большой прямоугольной области).
В конце концов, это равносильно обходу сетки - вы собираете наименьшие ячейки на пути луча, а затем проверяете все объекты в них на предмет пересечения. Вам просто нужно проверить все из них и выбрать ближайший перекресток (чтобы вы исследовали все линии на пути луча).
Это O(sqrt(N)).
При обходе сетки, когда вы найдете пересечение, вы можете остановить поиск. Чтобы достичь этого с помощью обхода дерева квадрантов, вам нужно будет найти детей в правильном порядке - либо отсортировать 4 прямоугольных пересечения по расстоянию, либо хитро пересечь сетку из 4 ячеек (и мы вернулись к обходу).
Это просто другой подход, сравнительно такой же сложный для реализации, как мне кажется, и хорошо работающий (я проверил его на реальных данных - O(sqrt(N))). Опять же, вы только выиграете от этого подхода, если у вас будет хотя бы пара линий, когда полигон имеет 10 ребер, выигрыш по сравнению с простым тестированием всех из них будет небольшим, я думаю.
Имейте в виду, что сортировка - это в лучшем случае операция O(n log n). Вам может быть лучше просто проверить каждый в отдельности.
Вы ищете методы на основе сканлайнов /Active Edge Table? Вы можете взглянуть на запись в Википедии для Scanline Rendering или найти в каталоге Graphics Gems алгоритмы (в основном C, но также и некоторый код C++).
Как ты уверен, что ударишь кого-нибудь из них? Если они линии, это маловероятно.
Если вы пытаетесь протестировать действительно многоугольник (то есть, плоский), обычный способ сделать это - сначала пересечь плоскость, а затем проверить эту точку (в двухмерных координатах) для внутреннего / внешнего многоугольника.
Может быть, я неправильно понял, что вы на самом деле делаете.
В общем, ускорение пересечений со сложными фигурами осуществляется с помощью пространственного разбиения (и затем таких методов, как почтовый ящик, если ваши тесты дороги).
[Обновление: я неверно истолковал первоначальное намерение] Вы все еще можете использовать (2d) пространственное разделение, но накладные расходы могут не стоить этого. Индивидуальные тесты дешевы, если ваши полисы не сложны, может быть дешевле просто пройтись по ним. Трудно сказать из описания.
Попросите разъяснений, это правильно?
- У вас есть динамический набор отрезков L.
- Запрос: учитывая любую точку (x,y) и любое направление луча от этой точки, вы хотите определить ближайшую линию в L (если есть)?
Таким образом, точка (х, у) не является фиксированной? (Это может быть любая точка и любое направление?)