从分散的点创建一个循环

Question

我知道这听起来很琐碎，但我的大脑拒绝给出一个算法。你知道吗

我有一堆分散在二维平面上的点，想把它们存储在一个列表中，这样它们就可以创建一个环。这些点不属于循环。你知道吗

从列表中的第一个点开始（图中为红色），然后根据它们的距离依次添加其余的点。你知道吗

由于我不能回答我的问题，我将在这里张贴一个可能的答案。你知道吗

这是一种似乎能起作用的方法。 V.pos保存节点的位置，distance（）只是一个返回两点之间欧氏距离的函数。一种更快的方法是在将下一个节点附加到环之后删除它，这样就不必经过已经连接的点

ring = [nodes[0]] while len(ring) < len(nodes): minl=99999 for i in range(len(nodes)): dist = distance(V.pos[ring[-1]],V.pos[nodes[i]]) if dist<minl and nodes[i] not in ring: minl = dist next_node = nodes[i] ring.append(next_node)

Answer 1

如果您的点云已经像您的示例一样呈环形，那么这里有一个想法可以给出令人满意的结果：

• 确定一个中心点；它可以是所有点的重心，也可以是边界框的中心。你知道吗
• 以径向坐标（半径、角度）表示相对于中心的所有点
• 按角度排序

当然，这会产生随机云的锯齿状恒星，但不清楚“环”到底是什么。您可以将其用作初稿，并开始交换节点，如果这样可以缩短总距离的话。也许除了实现图中所有节点的最小距离之外，您只需要这个简单的代码。你知道吗

Anayway，这里是：

import math

points = [(0, 4), (2, 2), ...]     # original points in Cartesian coords    
radial = []                        # list of tuples(index, angle)

# find centre point (centre of gravity)
x0, y0 = 0, 0
for x, y in points:
    x0 += x
    y0 += y

x0 = 1.0 * x0 / len(points)
y0 = 1.0 * y0 / len(points)

# calculate angles
for i, p in enumerate(points):
    x, y = p
    phi = math.atan2(y - y0, x - x0)

    radial += [(i, phi)]

# sort by angle
def rsort(a, b):
    """Sorting criterion for angles"""
    return cmp(a[1], b[1])

radial.sort(rsort)

# extract indices
ring = [a[0] for a in radial]