有没有一种算法可以在给定公差角度的情况下找到几乎凸的船体?

计算科学 算法 计算几何
2021-11-27 06:22:54

我想知道是否有一种算法可以给定一组 o 点,如果角度为,则角度计算凸包α=0并给出一个α>0计算更接近“周长”的信封。

$\alpha$ 尺寸效应示意图

如果有一组点的不相交周长的定义,在这种情况下,生成的多边形α很大。

问题的另一种观点可以是找到一个可以参数化的算法α=0最小周长解决方案(凸包)和α=1(归一化)包围所有点的最小面积折线。

2个回答

您可能会调查所谓的alpha-hull,例如: CRAN 包关于 alpha 形状的维基百科
       在此处输入图像描述
      [来自此链接的图片。]

alpha-hull 具有非常好的几何特性,并且已经过大量研究,但它仍然可能无法满足您的目的。

这可能太简单而没有兴趣,但一种方法是找到凸包并使用多边形边界分段来定位满足α-角度标准,一旦完成完整的电路就停止而不添加更多顶点。可能需要多次通过才能达到“收敛”。

α-角度标准可以针对给定的一对连续边界顶点制定为位于圆弧与其弦=边界段之间的区域。人们可以将其称为圆形部分。

我们想对一种数据结构进行一些思考,该结构可以有效地找到指定的点。一个想法是为每个段计算一个边界框,并根据点的排序列表对其进行检查。