Trace a shape into a polygon of max n sides

Question

I'm looking for an algorithm that will find an irregular shape, maybe not too irregular, like a squashed circle, on a surface, and trace a polygon of a maximum of n sides around the shape. The 'n' maximimum might be based on the area of the shape.

Answer 1

I would do it like this:

1. compute tangent angles ang and its change dang for all curve segments

   you can use atanxy or atan2 for that

   ang[i] = atanxy(x[i]-x[i-1],y[i]-y[i-1]);
   dang[i] = ang[i]-ang[i-1];
   

2. find inflex points (Black)

   at these points the sign of dang is changing so

   dang[i-1]*dang[i+1]<0.0
   

   but you need to handle the dang=0.0 elements properly (need to scan before and after them). These points will be the fundamental skeleton for your output polygon

3. add the bumps max points (green)

   at these points the tangent angle is between nearest inflex points so to find max point between two inflex points i0 and i1 find the closest angle to

   angavg=0.5*(ang[i0]+ang[i1])
   

   do not forget that

   |ang[i]-angavg|<=PI
   

   so +/- 2.0*PI if this is not true

4. now you should have all significant points of your closed polycurve ...

   it should look like this:

   

   CW/CCW or Red/Blue just represents the sign of dang[i] ...

[Notes]

The output point type should be preserved (inflex/maxpoint) because it can be later used for comparison and detection of shapes ...