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 或 Red/Blue 只是代表 dang[i] 的符号...

[注释]

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