65.9K
CodeProject 正在变化。 阅读更多。
Home

在 MSChart 扩展中实现下采样算法

代码艺术家
starIconstarIconstarIconstarIconstarIcon

5.00/5 (3投票s)

2023年10月22日

MIT

5分钟阅读

viewsIcon

5844

downloadIcon

124

DynamicX-Largest-Triangle-Three-Bucket 算法在图数据绘图中的实现

引言

多年来，WinForms 应用程序的 MSChart Extension 在显示大量数据时的性能问题仍未得到解决。在刷新应用程序中的图表时，我们希望它尽可能快地绘制，以最大限度地减少用户等待时间和内存消耗。在使用 WinForms 中的 Microsoft Chart Control (MSChart) 时，随着数据量的增加，内存使用量和图表绘制时间也会随之增长。FastLine 系列的性能更好，但在数据量超过 10 万个数据点时仍然会遇到性能瓶颈。

此外，在有限的像素屏幕上绘制大量数据点会导致所有数据点和线条重叠，从而导致用户误解信息。下面的示例显示了频率为 10 万个数据点的正弦波与仅有 500 个数据点的降采样图的对比。

10 万个数据点的正弦波

降采样到 500 个数据点的正弦波

关于“最大三角形三桶”（LTTB）算法

显然，我们需要某种降采样策略来在屏幕上绘制足够的数据点，以获得更好的速度，同时保留波形的峰值和谷值。重要的是要记住，降采样数据仅用于数据可视化目的，而非定量分析。

在 MSChart Extension 中，我们决定实现 Sveinn Steinarsson 在他的硕士论文中描述的 最大三角形三桶 (LTTB) 算法。完整的论文和在不同编程语言中的实现可在 Sveinn Steinarsson 的 GitHub 页面上找到。MSChartExtension 中的实现基于 Adrian Seeley 的 C# 代码。

该算法一次处理三个桶，并从左向右遍历分割的桶，选择一个具有最大有效面积的点来代表降采样数据中的每个桶。下面的示例显示了包含 5000 个数据点的随机数据系列，以及相同系列降采样到 500 个数据点的对比。

5000 点的随机数据

降采样到 500 点的随机数据

对于选定桶 n 中的每个点，通过点 a 和 avg 计算每个点的三角形面积，其中点 a 是前一个桶中选定的点，而点 avg 是下一个桶中的临时点。具有从桶 n 中获得的最大面积的数据点将被选中。

最大三角形三桶计算

算法实现如下，其中 window[x] 代表每个桶中选定的点。
我们在代码中进行了进一步优化，移除了乘以 0.5 的操作，因为使用三角形面积和正方形面积计算在选择点方面没有影响。

    double max_area = double.MinValue;
    for (int n = bucket_start; n < bucket_end; n++)
    {
        // Calculate triangle area over three buckets
        double area = Math.Abs((a_x - avg_x) * 
                      (array[n].Y - a_y) - (a_x - n) * (avg_y - a_y));
        if (area > max_area)
        {
            max_area = area;
            max_area_point = array[n];
            next_a = n; // Next a is this b
        }
    }
    // Pick this point from the Bucket
    window[w++] = max_area_point;

动态 X - 最大三角形三桶（DLTTB）算法

如果您阅读了 Sveinn Steinarsson 的论文和 GitHub 页面，您应该会注意到 LTTB 存在以下限制。

  1. 不支持数据数组中的间隙（null 值）。
  2. X 值必须严格递增。

我们决定更进一步，解决原始 LTTB 算法中描述的限制。

改进的 DyanmicX-Largest-Triangle-Three-Bucket (DLTTB) 算法不是按数据索引分割数据点，而是将数据点划分并分组到每个具有固定 X 间隔的桶中。每个桶中的数据点数量可能因数据而异。如果没有任何数据点的 x 值落在桶的边界之间，则该桶可能不包含任何数据。

   while (array[start].X < bucketBoundary) { start++; }
    bucketBoundary += bucketSizeX;
    end = start;
    if (end <= (array.Length - 1)) //Prevent buffer overrun
    {
        while (array[end].X < bucketBoundary)
        {
            end++;
            if (end == array.Length) break;
        }
    }

没有数据点的桶将不会被绘制，而其他桶的降采样数据将基于 LTTB 算法进行计算。考虑到某些桶可能为空，DLTTB 算法的降采样数据可能包含少于指定显示数据量的点。

下面的示例显示了具有 2 个不同间隔的正弦波的 5000 个数据点，其中前 4500 个数据点的 x 增加了 1，而后 500 个数据点的 x 增加了 20。请注意前 4500 个数据点被绘制成实心块的数据量。

原始 5000 点数据

下图显示了使用 LTTB 算法将原始数据降采样到 800 个数据点。最后 500 个数据点看起来很糟糕并且丢失了重要细节，因为 LTTB 无法识别数据中不同的 X 间隔。

使用 LTTB 降采样到 800 点

下一个图像显示了使用 DLTTB 算法将系列降采样到 800 个数据点，效果更好。

使用 DLTTB 降采样到 800 点

DLTTB 和 LTTB 的性能相同，因为两种算法都使用了单次遍历方法，不涉及复杂的乘法计算。

在 MSChart Extension 中的实现

LTTB 和 DLTTB 算法在 MSChartExtension 的 DownSampling 类中实现。将 dynamicX 设置为 true（DLTTB）或 false（LTTB）以选择不同的算法。在 ChartOption 类中引入了一个名为 BufferedMode 的新选项。

要使用缓冲模式，请首先启用 BufferedMode ，并在调用 EnableZoomAndPanControls 方法时在 ChartOption 中设置 DisplayDataSize ，如下所示：

new ChartOption()
{
    ...
    BufferedMode = true,
    DisplayDataSize = 800
    ...
});

接下来，使用 Series 类的以下扩展方法向系列添加数据点：

series.AddXYBuffered( xvalue, yvalue);

在缓冲模式下，图表上显示的最大数据点数量由 DisplayDataSize 属性定义。当用户放大图表时，可见数据的数量将根据比例重新评估。如果可见数据的数量是所定义显示数据大小的两倍以上，则降采样算法将生效。否则，将绘制所有可见数据。这样，当用户放大时，数据的细节将可用。系列的第一点和最后一点始终被绘制，以确保 PAN 功能正常工作。

未来更新

未来的更新和更改可在 GitHub - MSChartExtension 项目中公开获取。

历史

  • 2023年10月22日：初始版本
© . All rights reserved.