我试图将递归函数转换为基于python限制的迭代函数。你知道吗
我正在将在this answer中找到的算法从Javascript改编为Python。为了更好地解释算法,我建议阅读我链接的答案,因为它更简洁。高层次的目的是沿着由lat/lng对(点)组成的“线”找到等距点。但是,由于Python中最大递归深度的限制,我在递归move_along_path
函数中遇到了一些问题。在阅读了一些类似的问题之后,我发现最好的办法是将它转换成一个迭代函数。我甚至开始转换都有困难。你知道吗
这是我改编的两个函数,其中move_along_path
是递归函数(只有一个需要转换),有时也调用move_towards
。你知道吗
如何开始转换?转换时需要考虑哪些基本步骤?你知道吗
# This is the base function that calls the recursive function
def get_equidistant_markers_from_polyline_points(self, points):
points = points[1::10]
# Get markers
next_marker_at = 0
markers = []
while True:
next_point = self.iterative_move_along_path(points, next_marker_at)
if next_point is not None:
markers.append({'lat': next_point[0], 'lng': next_point[1]})
next_marker_at += 80000 # About 50 miles
else:
break
print(markers)
return markers
# This function moves from point to point along a "path" of points.
# Once the "distance" threshold has been crossed then it adds the point
# to a list of equidistant markers.
def move_along_path(self, points, distance, index=0):
if index < len(points) - 1:
# There is still at least one point further from this point
# Turn points into tuples for geopy format
# point1_tuple = (points[index]['latitude'], points[index]['longitude'])
# point2_tuple = (points[index + 1]['latitude'], points[index + 1]['longitude'])
point1_tuple = (points[index]['lat'], points[index]['lng'])
point2_tuple = (points[index + 1]['lat'], points[index + 1]['lng'])
# Use geodesic method to get distance between points in meters
distance_to_next_point = geopy.distance.geodesic(point1_tuple, point2_tuple).m
if distance <= distance_to_next_point:
# Distance_to_next_point is within this point and the next
# Return the destination point with moveTowards()
return self.move_towards(point1_tuple, point2_tuple, distance)
else:
# The destination is further from the next point
# Subtract distance_to_next_point from distance and continue recursively
return self.move_along_path(points, distance - distance_to_next_point, index + 1)
else:
# There are no further points, the distance exceeds the length of the full path.
# Return None
return None
def move_towards(point1, point2, distance):
# Convert degrees to radians
lat1 = math.radians(point1[0])
lon1 = math.radians(point1[1])
lat2 = math.radians(point2[0])
d_lon = math.radians(point2[1] - point1[1])
# Find the bearing from point1 to point2
bearing = math.atan2(math.sin(d_lon) * math.cos(lat2),
math.cos(lat1) * math.sin(lat2) -
math.sin(lat1) * math.cos(lat2) *
math.cos(d_lon))
# Earth's radius
ang_dist = distance / 6371000.0
# Calculate the destination point, given the source and bearing
lat2 = math.asin(math.sin(lat1) * math.cos(ang_dist) +
math.cos(lat1) * math.sin(ang_dist) *
math.cos(bearing))
lon2 = lon1 + math.atan2(math.sin(bearing) * math.sin(ang_dist) *
math.cos(lat1),
math.cos(ang_dist) - math.sin(lat1) *
math.sin(lat2))
if math.isnan(lat2) or math.isnan(lon2):
return None
return [math.degrees(lat2), math.degrees(lon2)]
我不是python的高手,所以我相信你可以优化它,但是一般的想法是,你不需要调用递归函数,你只需要做一个while循环,直到你的条件得到满足,在循环中,你可以修改变量,就像你把它们作为参数发送给递归函数一样。你知道吗
假设您发布的代码是正确的,我认为以下函数可以作为一种迭代方法来替换当前的递归函数:
当从递归返回时,由于递归的一个步骤似乎与先前计算的值没有依赖关系,因此应该简单而正确地插入
while
循环并适当地更新变量。你知道吗相关问题 更多 >
编程相关推荐