Контейнер отрезка линии для быстрого пересечения лучей?(2D)

Question

У меня есть луч, мне нужно найти ближайший отрезок линии, на который он попадает.Я думаю, что это можно сделать за O (log n) времени, если сначала отсортировать отрезки линии, но я не могу вспомнить, как их сортировать...Я думаю, что лучше всего подошло бы какое-то дерево, но как мне отсортировать их как по начальной, так и по конечной точке?Я бы также хотел быстрых вставок в эту структуру данных, если это возможно.

Есть много кода для одного луча против одного сегмента линии, но мне нужно что-то для одного луча против многих сегментов линии...Я не знаю, какие термины искать в Google.

Ссылка на соответствующую статью - это хорошо, код на C ++ - еще лучше.Спасибо!:)

PS:Отрезки линии на самом деле являются ребрами несамопересекающегося многоугольника, отсортированного в порядке CCW...но я думаю, что может быть какое-то преимущество в том, чтобы сортировать их по-другому?

Это все 2D.

---

С другой стороны, я не совсем уверен, что это является возможно.Могло бы помочь какое-то пространственное разделение, но в остальном я не могу придумать никакого способа отсортировать линии так, чтобы их можно было сравнить с произвольным лучом.

Answer 1

Вы могли бы взять ограничивающую рамку многоугольника (минимальные-максимальные координаты x, y) и построить сетку внутри рамки.Затем для каждой ячейки запомните все линии, которые пересекают ячейку.

Найдите раздел, подобный этому:

• Выясните, в какую ячейку луч попадает первой (O(1))
• Использование Алгоритм обхода сетки чтобы "провести" луч через сетку.Когда вы нажмете на непустую ячейку, проверьте все ее строки, проверьте, есть ли пересечение внутри ячейки, и выберите ближайшее пересечение.Если все пересечения находятся за пределами ячейки, продолжайте (это O (длина сетки)).

Вы также могли бы сделать сетку иерархической (т.е. квадродерево - дерево, о котором вы просили), и пройдитесь по нему, используя тот же алгоритм. Это делается с помощью трассировки лучей в 3D а временная сложность равна O(sqrt(N)).

---

Или используйте подход, который я использовал в своем raytracer:

• Построить квадродерево содержащий линии (построение квадрата описано в статье) - вы разбиваете узлы (= области), если они содержат слишком много объектов, на 4 подузла (подобласти)

• Соберите все конечные узлы из квадродерева , в которое попадает луч:

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

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

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

Это O(sqrt(N)).

При обходе сетки, когда вы находите пересечение, вы можете прекратить поиск.Чтобы достичь этого с помощью обхода квадратичного дерева, вам нужно будет выбрать дочерние элементы в правильном порядке - либо отсортировать 4 прямоугольных пересечения по расстоянию, либо умело пересечь сетку из 4 ячеек (и мы вернемся к обходу).

Это просто другой подход, сравнительно такой же сложный в реализации, я думаю, и работает хорошо (я протестировал его на реальных данных - O(sqrt(N))).Опять же, вы выиграете от этого подхода, только если у вас будет хотя бы пара линий, когда многоугольник имеет 10 ребер, я думаю, что выгода по сравнению с простым тестированием всех из них будет незначительной.

Answer 2

Вы ищете методы, основанные на scanline / Active Edge Table?Вы можете взглянуть на статью в Википедии для Рендеринг линии сканирования или поискать в Графические Жемчужины каталог для алгоритмов (в основном C, но также и некоторый код на C ++).

Answer 3

Имейте в виду, что сортировка - это в лучшем случае операция O (n log n).Возможно, вам будет лучше просто проверить каждый из них по отдельности.

Answer 4

Почему вы уверены, что попадете в кого-нибудь из них?Если это линии, то это маловероятно.

Если это действительно многоугольник (т.е.planar), который вы пытаетесь протестировать, обычный способ сделать такого рода вещи - сначала пересечь с плоскостью, затем протестировать эту точку (в 2d координатах) для внутреннего / внешнего многоугольника.

Может быть, я неправильно понял, что ты на самом деле делаешь.

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

[Обновить:Я неправильно истолковал первоначальное намерение] Вы все еще можете использовать (2d) пространственное разделение, но накладные расходы могут того не стоить.Индивидуальные тесты стоят дешево, если ваши полисы не сложны, возможно, было бы дешевле просто пройти их.Трудно сказать по описанию.

Answer 5

Попросите разъяснений, правильно ли это?

• У вас есть динамический набор линейных сегментов L.
• Запрос:данный Любой точка (x, y) и и Любой направление луча от этой точки, вы хотите определить ближайшую линию в L (если таковые имеются) ?

Значит, точка (x, y) не является фиксированной?(Это может быть любая точка и любое направление?)