Как применить рекурсивную функцию в земельном подразделении?

Question

Я сделал код подразделения, который позволяет разделить полигон методом ограничительной рамки. subdivision(coordinates) приводит к subblockL и subblockR (слева и справа). Если я хочу повторить этот код подразделения, пока он не достигнет области меньше 200, мне нужно будет использовать метод рекурсии.

ex: B = subdivision(A)[0], C = subdivision(B)[0], D = subdivision(C)[0] ... пока не достигнет области, близкой к 200. (Другими словами,

subdivision(subdivision(subdivision(A)[0])[0])[0]...)

Как я могу упростить повторениеподразделения и как я могу применить подразделение к каждому блоку вместо одного блока?

while area(subdivision(A)[0]) < 200:  
    for i in range(A):   
        subdivision(i)[0]

def sd_recursion(x):  
    if x == subdivision(A):  
        return subdivision(A)      
    else:   
        return   

Я не уверен, какую функцию поместить в

Answer 1

«Какую функцию вставить» - это сама функция;это определение рекурсии.

def sd_recursive(coordinates):
    if area(coordinates) < 200:
        return [coordinates]
    else:
        a, b = subdivision(coordinates)
        return sd_recursive(a) + sd_recursive(b)  # list combination, not arithmetic addition

Если перефразировать, если площадь меньше 200, просто верните сам многоугольник. В противном случае разделите многоугольник на две части и верните ... результат применения одной и той же логики к каждой части по очереди.

Рекурсивные функции сложны, потому что рекурсивные функции сложны. Пока вы не обернетесь вокруг этого явно круглого аргумента, все будет трудно понять. Важнейшим моментом проектирования является наличие «базового случая», который не повторяется, иными словами, он выходит за пределы бесконечного цикла функции, вызывающей себя при некоторых четко определенных условиях. (Существует также косвенная рекурсия, где X вызывает Y, который вызывает X, который вызывает Y ...)

Если у вас все еще возникают проблемы, посмотрите на один из многих вопросов об отладке рекурсивных функций. Например, Понимание рекурсии в Python

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

(В Python ['a'] + ['b'] возвращает ['a', 'b'], так что это не арифметическое добавление двух списков, это простоудобный способ вернуть один список из объединения двух других списков один за другим.)

Рекурсию всегда можно развернуть;вышеприведенное может быть реорганизовано в

def sd_unrolled(coordinates):
    result = []
    while coordinates:
        if area(coordinates[0]) < 200:
            result.extend(coordinates[0])
            coordinates = coordinates[1:]
        a, b = subdivision(coordinates[0])
        coordinates = [a, b] + coordinates[1:]
    return result

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