How to find vertices of a polygon with convex or concaved sides?

I have a bunch of polygons with convex or concaved shapes, and I would like to find the vertices of each point, then plot a line from point to point. In blue, I have the polygon that I generated, and then I manually found the vertices and plotted a line between them.

The polygons can have different numbers of sides (but can be predicted with reasonable accuracy), and can be either concave or convex.

I tried using Ramer-Douglas -Pecker algorithm but it doesn’t work for shapes that are too concave or convex like the one above. My end goal is to find how much out of tolerance the blue line is from flatness.

Heres an example where RPD worked, even then it is slightly offset.

Is there a better approach than what I am currently doing?

[Matt J]

It's not clear how you are defining a "vertex". For a convex polygon, a vertex or extreme point would normally be any point that doesn't lie in the middle of a straight boundary edge. By that definition, every point on your blue square-like shape would be a vertex, because it has no straight edges. Perhaps you instead mean a point with a non-unique tangent line?

[Hasan]

Thanks for responding, I meant a corner which makes it a non-unique tangent line

Answer 1

[Matt J]

This assumes that flattening the sides always gives a convex shape, like in your examples.

load data 

qConcave=getCorners(pConcave);
qConvex=getCorners(pConvex);

subplot(1,2,1)
plot(pConcave,'FaceColor','none','EdgeColor','b'); hold on
plot(qConcave,'FaceColor','none','EdgeColor','r'); hold off

subplot(1,2,2)
plot(pConvex,'FaceColor','none','EdgeColor','b'); hold on
plot(qConvex,'FaceColor','none','EdgeColor','r'); hold off

function pOut=getCorners(pIn, N,tol) 
arguments
  pIn polyshape
  N=1000;
  tol=5;
end

  theta=linspace(0,360,N+1); theta(end)=[];

  V=pIn.Vertices;

  M=size(V,1);


  [~,I]=max( V*[cosd(theta); sind(theta)]  ,[],1,'linear');

 T=zeros(M,N);
 T(I)=1;

 counts = sum(T,2);

 j=counts>median(counts)+tol; 

 pOut=polyshape(V(j,:));

end

[Hasan]

Wow! Thank you this works perfectly!