ordering shuffled points that can be joined to for

Question

I have a collection of points that join to form a polygon in 2D cartesian space. It is in the form of a python list of tuples

[(x1, y1), (x2, y2), ... , (xn, yn)]

the problem is the join them and form a polygon in a graph. (I'm using matplotlib.path)

I made a function to do this. It works as follows:

it goes to first point ie (x1, y1) and joins a line to next point ie (x2, y2) and a line from (x2, y2) to (x3, y3) and so on .. till the end which is (xn, yn). It closes the polygon by joining (xn, yn) to (x1, y1).

The problem is the list containing these points does not contain the points in the right order so that results in bad drawings like these(Every closed polygon is colored automatically).

Example:

for this list of vertices = `[(-0.500000050000005, -0.5), (-0.499999950000005, 0.5), (-0.500000100000005, -1.0), (-0.49999990000000505, 1.0), (0.500000050000005, -0.5), (-1.0000000250000025, -0.5), (1.0000000250000025, -0.5), (0.499999950000005, 0.5), (-0.9999999750000024, 0.5), (0.9999999750000024, 0.5), (0.500000100000005, -1.0), (0.49999990000000505, 1.0), (-1.0, 0.0), (-0.0, -1.0), (0.0, 1.0), (1.0, 0.0), (-0.500000050000005, -0.5)]

The points:

Bad order of points results in:

Correct way to join:

Is there any good (and easy if possible) algorithm to reorder the points to correct order? `

Answer 1

I wrote a paper on a generalization of your problem long ago. There is a nice desription here, created for a class in computational geometry. The generalization is that the algorithm works even if your polygon has holes; see below. If it does not have holes, it still works without modification.
     

J. O'Rourke, "Uniqueness of orthogonal connect-the-dots", Computational Morphology, G.T. Toussaint (editor), Elsevier Science Publishers, B.V.(North-Holland), 1988, 99-104.

Answer 2

This sorts your points according to polar coordinates:

import math
import matplotlib.patches as patches
import pylab
pp=[(-0.500000050000005, -0.5), (-0.499999950000005, 0.5), (-0.500000100000005, -1.0), (-0.49999990000000505, 1.0), (0.500000050000005, -0.5), (-1.0000000250000025, -0.5), (1.0000000250000025, -0.5), (0.499999950000005, 0.5), (-0.9999999750000024, 0.5), (0.9999999750000024, 0.5), (0.500000100000005, -1.0), (0.49999990000000505, 1.0), (-1.0, 0.0), (-0.0, -1.0), (0.0, 1.0), (1.0, 0.0), (-0.500000050000005, -0.5)]
# compute centroid
cent=(sum([p[0] for p in pp])/len(pp),sum([p[1] for p in pp])/len(pp))
# sort by polar angle
pp.sort(key=lambda p: math.atan2(p[1]-cent[1],p[0]-cent[0]))
# plot points
pylab.scatter([p[0] for p in pp],[p[1] for p in pp])
# plot polyline
pylab.gca().add_patch(patches.Polygon(pp,closed=False,fill=False))
pylab.grid()
pylab.show()