I know this sounds trivial, but my head is refusing to give an algorithm for this.

I have a bunch of points scattered on a 2-D plane and want to store them in a list such that they create a ring. The points do not belong on a cycle.

Start from the first point in the list (red in this pic) and sequentially add the rest based on their distance.

Since I cannot answer my question I will post here a possible answer.

This is an approach that seems to do the job. V.pos holds the positions of the nodes and distance() is just a function that returns the Euclidean distance between two points. A faster approach would also delete the next_node after appending it to the ring so that you don't have to go through the already connected points

ring = [nodes[0]]while len(ring) < len(nodes): minl=99999for 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 = distnext_node = nodes[i]ring.append(next_node)

Here's an idea that will give okay-ish results if your point cloud is already ring-shaped like your example:

• Determine a centre point; this can either be the centre of gravity of all points or the centre of the bounding box.
• Represent all points in radial coordinates (radius, angle) with reference to the centre
• Sort by angle

This will, of course, produce jagged stars for random clouds, but it is not clear, what exactly a "ring" is. You could probably use this as a first draft and start swapping nodes if that gives you a shorter overall distance. Maybe this simple code is all you need short of implementing the minimum distance over all nodes of a graph.

Anayway, here goes:

import mathpoints = [(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 += xy0 += yx0 = 1.0 * x0 / len(points)
y0 = 1.0 * y0 / len(points)# calculate angles
for i, p in enumerate(points):x, y = pphi = 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]