Сегменты пересечения линий

Question

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

N (up to 100,000) Есть линейные сегменты, определенные как [(x1, y1), (x2, y2)], где x1 < x2 и y1 < y2 (например, сегменты линии имеют положительный наклон). Никакие сегменты линии не касаются или не пересекаются даже в конечных точках. Первый сегмент имеет (x1, y1) = (0, 0). Представьте себе, что каждый сегмент, как двумерный холм, должен подняться.

Человек начинается от (0, 0) и приземляется на первом холме. Всякий раз, когда человек приземляется на холм, он поднимается до конца, то есть (x2, y2) и прыгает прямо вниз. Если он приземляется на другой холм (где-нибудь на участке), процесс продолжается: он поднимается на этот холм и прыгает. Если больше нет холмов, он падает до -INFINITY, и процесс завершен. Каждый холм (x1, y1) -> (x2, y2) должен быть считается содержащим точку (x1, y1), но не содержащую точку (x2, y2), чтобы человек приземлился на холм, если он падает на него сверху на с позиции x = x1, но он не приземлится на холм если он падает на он сверху на x = x2.

Цель состоит в том, чтобы подсчитать, сколько холмов он касается.

Мои текущие мысли

Я имею в виду подметание линию поперек плоскости вдоль оси х. Каждый сегмент состоит из события BEGIN и END; каждый раз, когда мы сталкиваемся с началом сегмента линии, мы добавляем его в набор. Каждый раз, когда мы сталкиваемся с окончанием сегмента линии, мы удаляем его из набора. И когда мы нажмем точку КОНЕЦ нынешнего холма, на котором мы остановились, мы должны проверить комплект для самого высокого холма, на который мы можем приземлиться. Однако я не знаю, как определить, как быстро это проверить, потому что в наборе могут быть потенциально N записей. Кроме того, после перехода на другой холм порядок этих изменений изменится, потому что наклоны каждого сегмента, вероятно, разные, и я не знаю, как объяснить эту разницу.

Любые мысли?

Answer 1

Я думаю, что алгоритм развертки строк - хорошая идея. Позвольте мне суммировать ваш алгоритм до сих пор и добавить свои улучшения:

• Вы подметаете линию слева направо.
• У вас есть активный список, в котором перечислены все активные в данный момент сегменты. Этих сегменты, пересекающиеся с sweepline
• Каждой конечной точкой каждого отрезка считается «событием»
• , когда линия проносится через «старт» сегмент, сегмент будет добавлен в список активных сегментов
• Когда линия проносится через «конец» сегмент, сегмент получает удаляется из списка активных сегментов
• Если нет отрезков в активном наборе после удаления сегмента линии, процесс заканчивается
• Если в активном наборе есть сегменты линий при удалении сегмента линии, нам необходимо определить
  • A) Есть ли какие-либо сегменты линии в активном наборе с частями «ниже» ранее удаленной конечной вершины и
  • B) Какой из этих сегментов линии должен приземлиться человек.

Идея заключается в том, чтобы отсортировать сегменты линии в «активном наборе», что этот запрос является эффективным. То, что я имею в виде, что если мы знаем линию по крутизне и у перехватывать мы можем вычислить точки пересечения для й положения А начальной вершиной в

GreaterThan(segment1,segment2){ // is segment 1 higher than segment 2? 
//y = mx + b; compute y value of point on segment 2 for a given x value from s1 
//that is, m and b are slope and y-intercept of s2 
yVal = m * (segment1.first.x) + b 
if (yVal < segment1.first.y) 
    return true //the point on s2 corresponding to s1.first is lower than s1.first 
return false 
} 

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

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

Теперь нам просто нужно беспокоиться о том, что специальный случай вершины последнего сегмента линии не является «доступным». Поскольку вершины являются событиями, мы будем обрабатывать все события, прежде чем мы проведем тестирование нашего сегмента. таким образом, вы случайно не приземлитесь на конечную вершину линии в активном наборе, но вы получите WILL участок только что добавленного участка.

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

Как это звучит?

Answer 2

Вот приблизительное направление в Haskell. «сегменты» - это сегменты линий. (В этом примере третий сегмент немного превышает второй сегмент, чтобы проверить код.) «Matches» находит холмы/сегменты, которые помещают верхнюю часть последнего сегмента pt (x0, y0) в пределах своих границ и выше или равные y, соответствующие их аффинному преобразованию x0 («аффинный» вычисляет аффинную функцию для отрезка - топор + b, так сказать). Наконец, countHills проверяет возможные совпадения для следующего холма и выбирает ту, которая находится ближе всего y к y0 (вычислена по аффинному а * x0 + b), и выводит результат, аккумулируя холмы, поднявшиеся по порядку. Очевидно, что этой идее может потребоваться оптимизация для более длинных списков сегментов.

Результат, полученный ниже, показывает первый и третий сегменты. Второй холм/сегмент не является результатом, потому что он ниже третьего - мы приземляемся на третьем месте:

* Главная> countЧасы сегментов
[((0,0,0,0), (2,0,5,0)), ((1.0,1.5), (5.0,3.0))]

import Data.List 

segments = [((0,0),(2,5)),((1,1),(5,2)),((1,1.5),(5,3))] 

top segment = snd segment 

matches pt = 
    let x0 = fst pt 
     y0 = snd pt 
    in filter (\x -> x0 >= fst (fst x) 
        && x0 < fst (snd x) 
        && (affine x) x0 <= y0) segments 

affine segment = 
    let x1 = fst $ fst segment 
     y1 = snd $ fst segment 
     x2 = fst $ snd segment 
     y2 = snd $ snd segment 
    in (+ ((x1*y2-x2*y1)/(x1-x2))) . (* ((y2-y1)/(x2-x1))) 

countHills segments = countHills' (head segments) [] where 
    countHills' x result = 
    let hills = matches $ top x 
     x0 = fst (top x) 
     y0 = snd (top x) 
    in if null hills 
      then result ++ [x] 
      else let nextHill = 
        minimumBy (\a b -> compare 
             (y0 - (affine a) x0) 
             (y0 - (affine b) x0)) hills 
       in countHills' nextHill (result ++ [x]) 

Answer 3

В предварительной обработки вы можете пройти все сегменты и добавлять точки в СТЛ MultiMap < пары, LineSegment> или что-то в этом роде. Стоимость этой предварительной обработки будет O (NlogN). Затем вы можете продолжить свой метод линии развертки. Вам нужно перебирать точки из мультимапа. Поскольку все точки отсортированы и содержат ссылку на строку, которой соответствует точка, она будет стоить O (N).

Answer 4

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

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