How to fit polygon to irregular set of points with only vertical and horizontal edges?

Hi everyone,

I've been battling with this for a few days now, so hoping for some help on here. I have a set of points (actually quite a few sets, over 11k) that form a boundary around an area of interest. I'm trying to calculate the average value of pixels within each boundary. My issue is that the set of points is not ordered cw or ccw - it's basically random. They are also not concave, and so I can't use (or I can't figure out) the polygon functions (polyshape, boundary, alphaShape, convhull, etc) as they do not draw the boundaries correctly, and hence can't use inpolygon or poly2mask functions.

At the moment, the best I can get is by calculating the angle of each point from the centroid and then putting them in order following THIS answer, however this does not work for certain parts of the areas of interest - see the figures below. The markers represent the set of points, and the blue/orange is the best polygon I've been able to draw so far for each. The top right corner shows in a red line what the boundary should be.

Any ideas or suggestions for me to look at?

Thanks in advance!

Answer 1

[Matt J]

You will need to use a Traveling Salesman Problem solver to sort the vertices. There are a number of them on the File Exchange. This one has worked well for me,

https://www.mathworks.com/matlabcentral/fileexchange/71226-tspsearch?s_tid=srchtitle

[Alex Linossier]

Amazing, thanks Matt. The one you linked is working perfectly for me, appreciate your quick help!