Hello all.

I have a list of 2D points in random order (typically 100s).

These points correspond to the pixel coordinates of the boundary of an object. They are in ‘raster’ order. If I plot them I get this:

I am trying to order them so that if I plot a line between successive pairs, them I will have a closed polygon.

There is an algorithm that works well *if the polygon is convex*: You get a point inside the polygon, and order points by the angle of the line that join the center to them.

But as you can see, my contours are sometimes **not convex**. I have read a bit on the subject, and in summary as soon as the polygons are not convex, you cannot get a unique polygon with this algorithm. If I run it on this set of points using their centroid, I get this:

It’s not great…

So my question is:

There is no algorithm that returns a unique “good” polygon for non-convex polygons, but do you guys know an algorithm that can handle such polygons **when we know that each points are close to each other** (they are on the pixel grid and tangent)?

Right now we are recreating a pseudo image with these coordinates and filling the polygon before extracting the bounds of the BW patch obtained. But I am looking for an algorithm that operates directly on the XY coordinates.