algorithm - 将形状描画为最大 n 条边的多边形

Question

我正在寻找一种算法，可以在表面上找到不规则的形状，也许不太不规则，比如压扁的圆，并在该形状周围追踪最多有 n 条边的多边形。 “n”最大值可能基于形状的面积。

Answer 1

我会这样做:

1. 计算切线角 ang及其变化dang对于所有曲线段

   您可以使用atanxy或atan2为此

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

2. 找到拐点(黑色)

   在这些点上的符号为 dang正在改变

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

   但是你需要处理dang=0.0正确地扫描元素(需要在它们之前和之后扫描)。这些点将成为输出多边形的基本骨架

3. 添加凹凸最大点数(绿色)

   在这些点处，切线角位于最近的拐点之间，以便找到两个拐点之间的最大点 i0和i1找到最接近的角度

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

   别忘了

   |ang[i]-angavg|<=PI
   

   所以+/- 2.0*PI如果这不是真的

4. 现在您应该拥有闭合多重曲线的所有重要点...

   它应该看起来像这样:

   

   CW/CCW或红/蓝仅代表 dang[i] 的符号...

[注释]

应保留输出点类型(inflex/maxpoint)，因为它可以稍后用于形状的比较和检测...