Контейнер Line Segment для быстрого пересечения Ray? (2D)

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

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

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

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

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

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

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

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

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

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

Это O (кварт (N)).

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

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

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

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

Как вы уверены, что попадете в любой из них? Если это линии, то маловероятно.

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

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

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

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

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

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

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