如何写凸多边形算法

Question

我自己回去有找到了相关数学计算方法:voronoi图  ,不过没有学过这个,不知道那里能找到voronoi图程序

Answer 1

算法如下:
 1)建立坐标系
 2)标记离散点的坐标V={(Xi,yi)},V为离散点集合
 3)选择目标点U={(x0,y0)};
4)while(U!=V) 
{选择附近点(x',y')属于V-U;令T=V-U;
  while(U!=T)
   {计算距离d[i]=(x0-x')^2+(y0-y')^2;
     T=V-(x',y');
       选择附近点(x',y')属于V-U;
}
    找出d[i]中最小的点坐标(xj,yj)
    连接x0,y0,并使得x0=xj,y0=yj;
    U=U+{xj,yj}
}
    

Answer 2

面积权衡劈分法
1)建立坐标系 
2)标记离散点的坐标V={(Xi,yi)},V为离散点集合 
3)选择目标点U={(x0,y0)}; 
4)while(U!=V) 
{选择附近点(x',y')属于V-U;令T=V-U; 
  while(U!=T) 
  {计算距离d[i]=(x0-x')^2+(y0-y')^2; 
    T=V-(x',y'); 
      选择附近点(x',y')属于V-U; 
} 
    找出d[i]中最小的点坐标(xj,yj) 
    连接x0,y0,并使得x0=xj,y0=yj; 
    U=U+{xj,yj} 
} 

Answer 3

给你一个，不太成熟。
假设精度为X
把每个点理解成半径为0的圆，变量名为R，时间同步，对每个点进行X个单位的扩展。如果扩展后的圆的范围内有其它的圆的位置，该扩展点不变。其它部分继续扩展，直到该点周围已没有可扩展空间或到达图像边界。
返回该点所对应的形状的边界即为结果。
为了做高精度的结果，这个方法不太好，要全部使用矢量运算，而这种算法的判断值为位图，但是原理差不多。