Промежуточные сегменты

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

Есть сегменты линии 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 записей. Кроме того, после перехода на другой холм их порядок изменится, потому что наклоны каждого сегмента, вероятно, будут разными, и я не знаю, как объяснить эту разницу.

Любые мысли?

Ответ 1

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

Ответ 2

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

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

Ответ 3

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

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

Идея состоит в том, чтобы сортировать сегменты линий в "активном наборе", чтобы этот запрос был эффективным. Я думаю, что если мы знаем наклон линии и перехват y, мы можем вычислить точки пересечения для начальной вершины x position

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
}

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

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

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

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

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

Ответ 4

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

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

* Main > countHills сегменты
[((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])