Блог

например, когда точки задаются в виде (x-слева, x-справа, y) в координатах x, y, ( 1 , 5 , 3), (2 , 4, 5) возвращает (1,2,3) , (2 ,4 ,5), (4,5,3)

Простой жадный алгоритм решает эту проблему аккуратно. Сортируйте свои сегменты по координате y, по убыванию; ca;; этот список seg . Теперь …

 top_hull = [empty set]
while seg is not empty
    head = seg.pop()    // pop off the highest segment.
    top_hull  = head
    for each segment in seg
        remove the interval (head.xleft, head.y-left) from segment
  

Обратите внимание, что удаление интервала может быть выполнено в нескольких случаях:

 `head`'s interval does not overlap `segment`
    no action
`head`'s interval contains `segment`
    remove segment
`segments`'s interval contains `head` (both ends stick out
    split segment into the two remaining pieces.
`head`'s interval overlaps one end of `segment`
    truncate segment
  

В зависимости от вашего языка реализации могут существовать отличные пакеты поддержки интервальной алгебры.

Самый простой эффективный ( O (N log N) ) способ решить эту проблему — с помощью алгоритма «линейной развертки».

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

Обратите внимание, что эти важные события могут происходить только в позициях x, где начинается или заканчивается один из входных сегментов. Следовательно, вместо того, чтобы плавно подметать линию, нам нужно учитывать только то, что происходит в этих позициях x. Итак:

1. Сгенерируйте список всех начальных и конечных событий для сегментов. Например, для сегмента {1, 2, 5} будут генерироваться события {1, начало 5}, {2, конец 5}
2. Создайте максимальную кучу, чтобы отслеживать самый верхний сегмент.
3. Отсортируйте все события по позиции x и обработайте их по порядку. Для событий с одинаковой позицией x сначала запустите события. Это гарантирует, что вы обработаете начальное событие каждого сегмента до его конечного события.
4. Для каждой позиции x в списке обработайте все события с этой позицией x как единое целое. Для каждого начального события {x, start y} добавьте y в кучу. Для каждого события {x, end y} удаляйте y из кучи.
5. Когда вы закончите обработку событий для позиции x, самым большим элементом в куче будет позиция y верхнего корпуса до следующей позиции x в списке.

Ответ Чернослива содержит правильную идею, но я чувствую, что он не соответствует описанию того, как проверять перекрытие интервалов. Фактически, эта часть алгоритма выполняется за квадратичное время, O(n^2) поскольку в какой-то момент он формирует все n^2 пары, в чем нет необходимости. Что бы я сделал-

Постановка в очередь

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

 heap = max_heap(segement_list)
output = []
while heap is not empty
    segment = heap.pop() # max / highest

    # trim / split segment
    # append trimmed segment(s)
  

Пересечения

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

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

 # boolean- do `a` and `b` intersect
function intersects(a, b)
    return a.upper_x >= b.lower_x

# boolean- is `b` a subsegment of `a`
function is_subsegment(a, b)
    return a.upper_x >= b.upper_x
  

Нам также понадобятся три преобразования, использующие то же самое a и b определение-

 function merge(a, b)
    a.upper_x = b.upper_x

function trim_left(a, b)
    a.upper_x = b.lower_x

function trim_right(a, b)
    b.lower_x = a.upper_x
  

Возвращаясь к идее запроса BST-take, left_segment полученного при запросе нашего сегмента segment , и посмотреть, пересекаются ли они. Если они пересекаются, проверьте, есть ли segment is_subsegment из left_segment . Если это так, прервите и continue перейдите к следующему сегменту в куче. В противном случае, при условии, что они пересекаются, нам потребуется trim_right segment . Независимо от пересечения или нет, мы будем обрабатывать любые пересечения с правой стороны. Впоследствии мы можем merge изменить segment (фактически subsegment , как вы увидите) с left_segment , если они перекрываются.

left_segment — это единственный сегмент, который может перекрываться слева, потому что мы объединяем все перекрывающиеся сегменты по мере их вставки в BST. Однако это не относится к правой стороне, поскольку наша segment еще не обрезана справа. Нам нужно будет обрабатывать обрезку постепенно.

Возьмите, right_segment чтобы быть следующим сегментом после left_segment в дереве (обход по порядку). Создайте копию segment called subsegment . Если subsegment пересекается right_segment , обрезайте его слева, вставьте subsegment в выходной массив, объедините два сегмента и удалите right_segment из BST. В противном случае просто вставьте subsegment в массив. Теперь мы можем объединить subsegment с left_segment , если они перекрываются. Если они этого не сделали, вставьте subsegment в BST и присвоите ему переменную left_segment .

Теперь мы повторяем этот процесс, пока не перестанем segment быть is_subsegment из left_segment . После этого мы повторяем весь процесс со следующим сегментом из кучи.

Анализ

Мы знаем, что формирование нашей максимальной кучи и использование ее максимальное n количество раз приведет к O(nlogn) временной сложности. Сложная часть заключается в определении временной сложности обработки пересечений. Обратите внимание, что для каждого обрабатываемого нами сегмента после того, как все subsegment s будут обработаны и объединены, мы увеличим размер нашего BST в целом не более чем на единицу. Это потому, что все наши subsegment файлы объединяются вместе на каждой итерации, так что в конечном итоге они образуют один большой сегмент. Это означает, что наш BST не больше, чем n , поэтому запрос и удаление / вставка в BST занимает O(logn) время.

Также обратите внимание, что для каждого сегмента, вставленного в BST, каждый из них будет пересекать другой сегмент только один раз — потому что, когда это произойдет, два (или более) сольются в один новый сегмент. Исключением из этого является случай, когда сегмент является подсегментом its left_segment , но в этом случае мы прерываем выполнение без создания каких-либо новых сегментов в любом случае, так что его чистое изменение размера в любом случае на 0. Используя эти знания в сочетании с предыдущим наблюдением о том, что каждый сегмент в конечном итоге вносит не более одного нового сегмента в BST, мы можем заключить, что будет не более O(n) пересечений и, следовательно, вставок / удалений. Итак, O(nlogn) пришло время поддерживать наш BST.

Учитывая, что остальные наши операции выполняются постоянно, наша общая временная сложность составляет O(nlogn) , а не O(n^2) при переборе пересечений и обрезки.