2

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.

ProfK
  • 49,207
  • 121
  • 399
  • 775
  • what is the input data? point set, polygon, raster image? what is desired accuracy ? is it matching against table of shapes or just need to find shape? what do you mean by shape closed area/polygon or feature on surface? what space ? 2D,3D,N-D ? add example images of input and output – Spektre Oct 10 '14 at 11:16
  • The input data will be basically irregular oval shaped blobs, such as a young child would outline things with. Just need to reduce the set of points on the perimeter into a set of triangles that can define an approximation of the blob. 2D space. – ProfK Oct 10 '14 at 12:06
  • and the input is vector or raster and how many dimensions ???!!! – Spektre Oct 10 '14 at 12:08
  • The output is vector and in 2 dimensions - a polygon - e.g. if the input was a circle, and the maximum sides was 8, the output would be an octagon. – ProfK Oct 10 '14 at 12:26
  • in that case check my answer if it is what you need/want – Spektre Oct 10 '14 at 12:46

1 Answers1

2

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

Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380
  • plus http://en.wikipedia.org/wiki/Ramer–Douglas–Peucker_algorithm for line simplification if needed – MBo Oct 10 '14 at 14:03