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.