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

Question

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

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

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

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

Это все 2D.

---

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

Answer 1

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

Найдите пересечение, подобное этому:

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

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

---

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

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

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

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

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

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

Это O (sqrt (N)).

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

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

Answer 2

Ищете методы сканирования / Active Edge Table? Вы можете взглянуть на запись в Википедии для Scanline Rendering или найти в каталоге Graphics Gems алгоритмы (в основном C, но также немного кода C ++).

Answer 3

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

Answer 4

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

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

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

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

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

Answer 5

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

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

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