4

我有一个点列表以及它们从一个中心点相对于彼此的角度。由于列表的生成方式，列表没有顺序，也不能保证两点之间的角度存在或不存在。也无法保证角度是顺时针还是逆时针。

嵌套列表或 2D numpy 数组将如下所示：

angle_array = 
[[A, B, 32]
[C, B, 37]
[A, D, 117]
[F, E, 84]
[A, F, 103]
[D, E, 56]]

列表的“列”在哪里[Point 1, Point 2, Angle between 1 and 2]

它是由这样的一组点创建的（对不起，糟糕的手机图片和工程师抓挠）：

我试图找到的糟糕的图画

我想最终得到一个这样的列表：

direction_list = 
[[A,0]
[B,32]
[C,69]
[D,117]
[E,173]
[F,257]]

在这种情况下，“列”在哪里Point, heading relative to point A

这只是一个示例，A 点不一定是航向点，它可以是集群中的任何点。

是否有一个 numpy 或 python 函数将遍历一个列表并根据我可以在这种情况下使用的列表中的常见值创建一个新的值列表？

4

2 回答 2

2

这是一个图形问题。

原始列表中的每一对都可以视为一条边。

从此列表构造一个图，然后运行深度优先搜索。

从绝对角度设置为零的随机节点开始。当您向下遍历边时，将与该边关联的角度添加到当前绝对角度。在向上的方向上，减去边缘的角度。一个节点被访问后，标记它并且不再访问它。

如果图是连接的，则此过程应将绝对角度与每个节点相关联。否则，您将不得不尝试在图中的每个节点处重新启动 DFS 以获得断开的绝对角度集。

如果某些绝对角度为负，只需从整个绝对角度列表中减去最小角度。

于 2013-04-24T01:28:13.707 回答
2

这可以变成一个图论问题：给定一个节点和边的列表，根据边加上从起始节点到当前边的距离来计算它们之间的距离。可以通过使图形定向来对方向进行编码。

在上面的示例中，假设您要以顺时针方向旋转（我假设这是因为 和 之间的角度A是F257，而不是 103）。A因此，在这个方向上，和之间没有边F。我们可以对我们的图进行如下编码：

graph = {'A': [('B', 32), ('D', 117)],
         'B': [('C', 37)],
         'C': [('D', 48)],
         'D': [('E', 56)],
         'E': [('F', 84)],
         'F': [('A', 103)]}

然后我们进行有效的广度优先搜索，在找到边时添加边。请注意，这不会进行任何错误检查；任何非连通图都会简单地以KeyError. 错误检查应该不难添加，但是：

import queue

def calculate_distances(graph, start):
    q = queue.Queue()
    distances = {start: 0}

    for adj in graph[start]:
        distances[adj[0]] = adj[1]
        q.put(adj[0])

    while not q.empty():
        next_node = q.get()
        for adj in graph[next_node]:
            if adj[0] not in distances:
                distances[adj[0]] = adj[1] + distances[next_node]
                q.put(adj[0])
    return sorted([[x, y] for x, y in distances.items()], key=lambda x: x[0])

测试：

if __name__ == '__main__':
    dist = calculate_distances(graph ,'A')
    print(dist)

>>> [['A', 0], ['B', 32], ['C', 69], ['D', 117], ['E', 173], ['F', 257]]
于 2013-04-24T01:32:45.257 回答