На этом шаге мы рассмотрим алгоритм слияния контуров.

Задача объединения контуров - новая отдельная вычислительная задача. В то время как большинство решений в различных источниках является итерационными, мы предложим линейно-рекурсивный метод. Его входы - два сортированных списка кортежей, представляющих собой контур. Кроме того, поскольку кортеж задаёт изменение высоты контура, метод, прежде чем изменить высоту, должен иметь доступ к предыдущей высоте. Более того, поскольку предлагаемый алгоритм обрабатывает список с первого кортежа (до исчерпания списка), последовательно удаляя обработанные кортежи, предыдущих высот не будет во входных списках. Таким образом, метод требует двух дополнительных параметров, скажем p₁ и p₂, для сохранения предыдущих высот контура. Естественно, оба этих параметра должны получить начальное значение 0 при первом вызове метода из основной функции (см. строку 9 примера 6.14).

Размер задачи зависит от длин входных списков контуров, скажем n₁ и n₂. Можно считать, что начальное условие выполняется, когда один из списков пуст, и метод в таком случае должен тривиально вернуть второй список. В примере 6.15 приведён код, где начальные условия описаны в строках 2-5.

Пример 6.15. Рекурсивный метод объединения контуров

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

def merge_skylines(sky1, sky2, p1, p2):
    if sky1 == []:
        return sky2
    elif sky2 == []:
        return sky1
    else:
        x1 = sky1[0][0]
        x2 = sky2[0][0]
        h1 = sky1[0][1]
        h2 = sky2[0][1]

        if x1 == x2:
            h = max(p1, p2)
            new_h = max(h1, h2)
            if h == new_h:
                return merge_skylines(sky1[1:], sky2[1:],
                                      h1, h2)
            else:
                return ([(x1, new_h)]
                        + merge_skylines(sky1[1:], sky2[1:],
                                         h1, h2))

        elif x1 < x2:
            if h1 > p2:
                return ([(x1, h1)]
                        + merge_skylines(sky1[1:], sky2,
                                         h1, p2))
            elif p1 > p2:
                return ([(x1, p2)]
                        + merge_skylines(sky1[1:], sky2,
                                         h1, p2))
            else:
                return merge_skylines(sky1[1:], sky2,
                                      h1, p2)

        else:
            if h2 > p1:
                return ([(x2, h2)]
                        + merge_skylines(sky1, sky2[1:],
                                         p1, h2))
            elif p2 > p1:
                return ([(x2, p1)]
                        + merge_skylines(sky1, sky2[1:],
                                          p1, h2))
            else:
                return merge_skylines(sky1, sky2[1:], p1, h2)

Архив с полным текстом приложения можно взять здесь.

Ключом для определения подходящей декомпозиции является то, что результат объединяющей функции - это новое очертание (контур), кортежи которого отсортированы в порядке возрастания значения х. Таким образом, алгоритм анализирует первые кортежи каждого списка и обрабатывает тот, что имеет меньшее значение х (или оба, если их значения х равны). Значит, в рекурсивных условиях, помимо первых кортежей контуров (х₁, h₁) и (х₂, h₂), нам нужны ещё и их предыдущие высоты p₁ и p₂.

Давайте сначала рассмотрим случай, когда х₁ = х₂ = х. Так как кортежи маркируют изменения в горизонте, нам, возможно, придётся включать в решение кортеж с наибольшей высотой. Например, на рисунке 1(a) точка (х, h₂) должна быть включена в конечный горизонт.

Рис.1. Случаи объединения контуров, когда их высота меняется в одной и той же точке x

Далее рекурсивный вызов будет использовать хвосты обоих входных списков без (х, h₁) и (х, h₂), так как возможные изменения в точке х уже обработаны правильно. Это делается в строках 19-21. Наконец, бывают ситуации, когда новый кортеж не включается в решение. Это происходит, когда новая наибольшая высота совпадает с предыдущей наибольшей высотой контура (то есть когда max(h₁, h₂) = max(p₁, p₂)), так как в точке х высота не меняется. Рисунок 1(b) иллюстрирует этот случай, где точка (x, h₂) не должна включаться в конечный контур (см. строки 16 и 17).

Теперь проанализируем возможные сценарии, когда значения x первых кортежей горизонтов не равны. Без потери общности допустим, что х₁ < х₂. В этом случае алгоритм должен решить, включать ли кортеж (х₁, h₁), или (х₁, p₂), или ни тот, ни другой, как показано на рисунке 2.

Рис.2. Возможные варианты слияния контуров при x₁ < x₂

Если h₁ > p₂, то в точке х₁ первый контур выше второго, и поэтому в объединение должен быть включён кортеж (х₁, h₁) (см. строки 25-27). Если же h₁ < p₂, то алгоритм должен проверить условие p₁ > p₂. Если условие истинно, то метод включает кортеж (х₁, p₂) (см. строки 29-31). Обратите внимание, что при h₁ < р₂ создаётся новый кортеж, которого нет во входных списках контуров. Случаи р₂ ≥ h₁ и р₂ ≥ р₁ означают, что объединённый контур не меняется в x₁. В итоге, обработав первый кортеж первого контура (x₁, h₁), метод отбрасывает его при вызове самого себя в соответствующих рекурсивных условиях. Кроме этого, аргументами, задающими предыдущие высоты горизонтов, будут h₁ и р₂ (см. строки 27, 31 и 34). Остальная часть кода в строках 36-46 похожа на код в строках 23-34 и обрабатывает случай x₂ < x₁.

На следующем шаге мы приведем решения нескольких задач.

Предыдущий шаг Содержание Следующий шаг