Алгоритм сканирования для поиска пересечений между линиями

У меня есть набор прямых L и набор точек P. Я хочу найти, сколько прямых L пересекается горизонтальной линией, проходящей через точку p. Как я могу это вычислить?


algorithm computational-geometry pseudocode
person jaketz    schedule 03.02.2021    source источник
comment
Ожидаете ли вы сделать это, не просматривая каждую строку в L (скажем, используя некоторый оптимизирующий тип данных контейнера)?   -  person rici    schedule 04.02.2021
comment
У вас есть набор линий или набор сегментов линии? В первом случае это просто проверка того, какие линии параллельны оси X.   -  person orlp    schedule 04.02.2021
comment
Также как хранятся ваши линии L, если они сегменты? Как пары точек (начало / конец)?   -  person orlp    schedule 04.02.2021
comment
Что, если линейный сегмент пересекается несколькими горизонтальными линиями, исходящими из точек в P? Считается ли это несколько раз или только один раз?   -  person orlp    schedule 04.02.2021
comment
Линии или отрезки ?? Сколько строк? Сколько очков?   -  person Yves Daoust    schedule 04.02.2021

Ответы (1)


arrow_upward
1
arrow_downward

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

Первый шаг - отбросить все x координаты - имеют значение только y координаты. Затем создайте массив пар из L и P. Для каждого сегмента линии в L добавьте (y_start, START) и (y_stop, STOP) в массив. Для каждой точки в P добавьте (y, POINT) в массив (START, STOP, POINT - это просто произвольные значения, например, перечисление C). Отсортируйте массив пар по первому значению.

Затем инициализируйте n = 0, l = 0, пройдитесь по массиву и посмотрите на второе значение каждой пары:

  1. Если это START, увеличьте l.
  2. Если это STOP, уменьшите l.
  3. Если это POINT, добавьте l к n.

n - ваш окончательный результат. В общей сложности преобладает сортировка O((|L| + |P|) log(|L| + |P|)).

person orlp    schedule 04.02.2021