algorithm - 绘图的采样方法

Question

假设我们正在编写一个程序，将用户提供的函数（黑匣子）的图呈现为一系列线段。我们希望获得函数的最小样本数，以便生成的图像“看起来”像函数（这里“看起来”的确切含义是问题的一部分）。一种天真的方法可能是仅以固定间隔进行采样，但我们可能会做得更好，例如通过采样“弯曲位”而不是“线性位”。是否有关于这个问题的系统方法/研究？

标签： algorithmplotgraphicssampling

Answer 1

使用组合采样方法的此参考可能会有所帮助。在此之前，其相关著作更多地解释了其他抽样方法：

在区间 Ω = [a, b] 上绘制函数 y = f(x) 有几种策略。在[20]中描述了基于在固定数量的等间距点中对 f 进行采样的简单方法。简单函数受到过采样的影响，而振荡曲线则被欠采样；[14]中提到了这些问题。[6]、[13]、[20]中描述了另一种基于区间约束图构建曲线外壳的方法。[41]中提到了有用域和函数范围的自动检测；广义区间算术方法在[40]中描述。

通过在较高曲率区域提供较高采样密度的自适应采样来表示显着的改进。有几种曲线插值算法可以保持速度，例如：[37]、[42]、[43]。自适应进给速率技术在 [44] 中进行了描述。Mathematica 软件的早期实现见 [39]. 通过减少数据，这些方法对于曲线绘制非常有效。多篇论文都提到了基于自适应采样的参数曲线的多边形逼近。细化标准以及递归方法在 [15] 中进行了讨论。多边形曲线的近似在[7]中描述，隐式曲线的几何和空间近似的鲁棒方法可以在[27]、[10]中找到，在三角模型中的仿射算法在[32]中工作. 但是，地图投影从未由隐式方程定义。类似的方法可用于图形绘制[21]。基于断点近似的其他技术可以在许多论文中找到：[33]、[9]、[3]；这些方法用于闭合曲线的多边形近似，并应用于计算机视觉。

因此，这些是定义“好”绘图的一些度量并引入一种基于度量优化绘图的方法的参考方法：

• 构建曲线的外壳
• 自动检测有用域和函数范围
• 自适应采样：在高曲率区域提供更高的采样密度
• 在高曲率区域提供更高的采样密度
• 由多边形曲线逼近
• 在三角模型中工作的仿射算术
• 组合采样：提供涉及不连续性的参数曲线的多边形近似。修改后的方法将用于函数 f(x) 的重建和绘图。基于将域分割成没有不连续性的子区间的思想，它代表了一个可以通过递归方法解决的典型问题。