我想从点列表中创建相对于单个点的标题，这些点之间有角度。有这个功能吗？

Question

我有一个点的列表和它们从一个中心点到彼此的角度。由于列表是如何生成的，因此列表没有顺序，也不能保证两点之间的角度是否存在。也无法保证角度是顺时针还是逆时针。你知道吗

嵌套列表或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函数可以循环遍历一个列表，并基于列表中的公共值创建一个新的值列表，我可以在本例中使用它？你知道吗

Answer 1

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

在上面的例子中，假设您想要顺时针方向旋转（我假设这是因为A和F之间的角度是257，而不是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]]

Answer 2

这是一个图形问题。你知道吗

原始列表中的每一对都可以看作一条边。你知道吗

从这个列表构造一个图，然后运行深度优先搜索。你知道吗

从绝对角度设置为零的随机节点开始。向下遍历边时，将与该边关联的角度添加到当前绝对角度。在向上方向，减去边的角度。节点被访问后，请对其进行标记，不要再访问它。你知道吗

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

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