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

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

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

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

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

Это все 2D.

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

источник

2009-04-09 mpen

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

Найдите intesection так:

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

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

Или использовать подход я сделал в моей Raytracer:

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

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

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

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

Это O (sqrt (N)).

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

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

источник

2009-06-14 12:59:25

Нет, O (log n), о котором я думал, был только для горизонтальных или вертикальных сегментов. Алгоритм Брешенема выглядит так, будто он может пропустить перекрестки, хотя, не так ли? Он не «заполняет» каждую ячейку, в которую он входит. В противном случае это выглядит как хороший подход. – mpen

Вы правы, обход сетки должен выполняться с помощью упомянутого здесь алгоритма http://www.devmaster.net/articles/raytracing_series/part4.php, см. Раздел «Обход сетки». Обратите внимание, что вы, вероятно, только выиграете, если ваш многоугольник имеет много (~ сотни) ребер, как они показывают в статье. –

Ну, вероятно, он не будет сотни ребер, но одни и те же края могут использоваться тысячи раз. Это похоже на лучший ответ на то, что я считал мертвым, поэтому я дам вам чек;) Спасибо. – mpen

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

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

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

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

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

источник

2009-04-09 03:55:16 simon

Я могу гарантировать, что луч ударит хотя бы по одному отрезку. Луч отбрасывается от вершины к внутренней части многоугольника. (Это 2D) – mpen

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

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

источник

2009-04-09 03:56:16 dirkgently

На первый взгляд похоже, что это работает только потому, что многоугольники/сегменты линии сортируются по y-порядку, а строки сканирования строго горизонтальны. Мои лучи могут быть брошены в любом направлении ... это может быть серьезной проблемой. – mpen

@Mark: Если бы вы могли дать нам общую картину того, что вы пытаетесь сделать (например, заполнение полигона), то мы можем указать некоторые специализированные алгоритмы. – dirkgently

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

источник

2009-04-09 03:58:50 rlbond

Все в порядке со мной. Весь мой алгоритм будет в лучшем случае O (n^2 log n), и мне нужно бросить много лучей ... – mpen

Сортировка не является операцией O (N log N). Сортировка с использованием только двухэлементных транзитивных сравнений есть, но не сортировка вообще. – SPWorley

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

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

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

источник

2009-06-15 00:11:08 jacob

Это правильно, Джейкоб. Направление дается другой точкой, но не углом, если это имеет значение. Несколько лучей будут сравниваться с одним и тем же набором сегментов линии, поэтому я полагаю, что может оказаться целесообразным выполнить некоторую предварительную обработку на линиях, если это поможет. – mpen

Возможно, мне также следует указать, что мы, вероятно, только смотрим на 20 строк линии и 5 лучей в среднем, но нет жесткого верхнего предела. Причина, по которой это должно быть эффективным, заключается в том, что ее часть рекурсивного алгоритма может стать довольно дорогостоящей. (Одна из моих реализаций заняла около минуты, чтобы обработать ~ 13 строк, и помимо этого вы даже не хотите попробовать). – mpen

Даже реализация грубой силы с использованием 20 линий и 5 лучей должна занимать несколько миллисекунд? Почему ваши так долго? – jacob

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

ответ

Смежные вопросы