- 2023-08-16 23:17:29
这篇文章来源于看到的一个回答Gnuplot: Scatter plot and density. 因为我需要绘制类似的图, 就花时间研究了一下链接中所提供的方法, 并进行了一点改进, 记在这里供需要的人参考.
首先明确一下问题: 有一组二维点, (xi, yi), i=1, 2, 3, …, n. 这些点之间存在较大程度的重叠, 我们将其绘制在平面上时想尽量直观地给出点分布的疏密情况.
下面以一个具体示例展开讨论. 我们分别以 (0, 0) 和 (2, 2) 为中心生成两组服从标准正态分布的点, 每组1000点, 共2000点.
直接绘制如下
可以看到, 直接绘制时很多点会重叠在一起, 导致无法直观地感受到数据点分布的疏密.
一种稍好点的绘制方式是使用透明度, 这样点密的位置, 看起来颜色会更深一些.
这种做法存在的问题是透明度数值的选取. 虽然也有一些方法可以估算最佳透明度, 但还是麻烦.
更好的做法是根据每个点周围其他点的密度来进行着色(或设置透明度), 一开始的链接所提供的方法就是这样. 为此, 我们先统计好每个点周围一定半径内分布的点数, 然后利用其作为点的着色变量.
我们设定统计半径为 0.1, 然后统计绘制
这个方法, 简单粗暴, 但就是慢. 因为要计算每个点到周围其他点的距离, 时间复杂度为o(N^2), 对上面测试的2000个点, 需要计算4百万次距离. 对其他脚本语言来说, 这可能不算什么, 但对gnuplot而言已经慢得有点无法接受了.
当然, 我们可以优化下距离的计算方法, 如避免使用平方根, 先进行简单判断等, 但这些都无法改进时间复杂度, 改进效果不大.
要进一步提供计算速度, 容易想到的是, 在统计每个点周围一定半径内的其他点时, 距离过大的点实际是不需要计算的, 这样的话, 我们可以先将每个点划分到一定的格子中, 在数算时只统计相邻格子中的点即可. 这种方法其实就是MD中常用的邻区搜索, 利用它可以将复杂度降低为o(N).
如果观察所得的图形, 可以发现另一问题, 那就是有些点的颜色仍然会有重叠, 导致疏密和颜色的对应并不明显. 简单的解决方法是先获得每个点周围其他点的个数, 再根据疏密进行排序, 绘制时先绘制密度低的点再绘制密度高的点, 这样颜色与疏密的对应看起来更合理.
既然我们可以分格子, 那么直接计算每个格子中点的个数, 处于同一格子中的点使用同一数据进行绘制即可. 这样虽然失去了点的具体位置信息, 但速度会有巨大提升.
当然, 我们也可以根据分格子后的数据绘制成二维密度图
