CODEWITHSUNDEEP
algorithmgeometry
ProfK
ProfK

Reputation: 51084

Trace a shape into a polygon of max n sides

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.

Upvotes: 2

Views: 657

Answers (1)

Spektre
Spektre

Reputation: 51873

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:

    img

    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 ...

Upvotes: 2

Related Questions