Можно ли с помощью Python устранить множественные рекурсивные хвостовые вызовы (преобразовать в итерацию) в реализации дерева квадрантов, которая назначает точки (X, Y) поддоменам (также известным как конечные узлы)? Вот не очень псевдокод:
def decompose(inX, inY, xmin, xmax, ymin, ymax, maxP):
#Paramters: Lists of X and Y coordinates, boundaries, max. #points per subdomain
if len(inX) <= maxP: #base case
--write out list of points and boundaries--
else:
xB = (xmin + xmax) / 2 #calculate new boundaries
yB = (ymin + ymax) / 2
for x, y in zip(inX, inY): #assign points to subdomains (a.k.a. children-nodes)
if x < xB:
if y < yB:
R1X.append(x), R1Y.append(y)
else:
R2X.append(x), R2Y.append(y)
else:
if y < yB:
R3X.append(x), R3Y.append(y)
else:
R4X.append(x), R4Y.append(y)
decompose(R1X, R1Y, xmin, xB, ymin, yB, maxP) #recursive tail calls (which I want to eliminate)
decompose(R2X, R2Y, xmin, xB, yB, ymax, maxP)
decompose(R3X, R3Y, xB, xmax, ymin, yB, maxP)
decompose(R4X, R4Y, xB, xmax, yB, ymax, maxP)
Мне известны методы устранения хвостовых вызовов, но примеры, которые я видел, не демонстрируют шаблона разветвления, присущего рекурсивной декомпозиции дерева квадрантов (несколько независимых рекурсивных хвостовых вызовов). Моя мотивация состоит в том, чтобы написать код, который не исчерпывает стек, если я использую его на миллионах точек, которые могут демонстрировать существенную кластеризацию, что приводит к очень глубокой рекурсии. Кроме того, я хочу включить временное измерение и реализовать пространственные буферы, чтобы точки можно было назначать нескольким подобластям (мне это нужно для дальнейшей обработки). Из-за большого количества настроек существующие реализации quadtree могут оказаться непригодными. Если вам надоел еще один новичок, задающий тот же старый вопрос, продолжайте и хорошего дня, спасибо за чтение. В противном случае вы могли бы либо указать мне на ресурсы, которые помогут мне решить проблему, либо опубликовать потенциальное решение. Я был бы рад, если бы вы это сделали.
