graphics - 与屏幕上的五百万个点进行交互

Question

我们需要同时在屏幕上显示 500 万个点（或非常简单的图形对象），并且我们希望与每个点进行交互（例如，更改它们的颜色或拖放它们）。
为了实现这一点，我们通常在最坏的情况下 O(N) 运行一个 for 循环遍历 500 万个项目，以根据鼠标坐标 (x, y) 访问和更改点的状态。由于对象数量巨大，这种方法会导致大量开销（每当用户选择一个点时，我们都必须运行 500 万个 for 循环）。我已经测试过这种方法，但几乎不可能用它制作交互式工具。无论如何，在不运行百万个 for 循环并导致此性能问题的情况下，是否可以快速有效地访问这些点？

Answer 1

你已经看过 KineticJS框架了吗？有一个非常令人印象深刻的压力测试，具有您正在寻找的完全相同的拖放功能。如果您使用 KineticJS，您可以使用以下命令访问每个点eventlistener，当然还可以更改其颜色、大小等：

      stage.on('mousedown', function(evt) {
        var circle = evt.targetNode;
      });

Answer 2

你真的没有提供很多细节

这些问题很快浮现在脑海：

• 点的大小相同吗？
• 画布上的点是否均匀分布？
• 如果一个点被“选中”，是否只有那个点重新着色或移动了？
• 为什么你通过压倒用户来违反良好的数据可视化规则？:)

考虑到这种缺乏特异性......

...分而治之：

• 将您的点阵分成多个部分。
• 将您的点划分到多个重叠的画布上。

将您的点阵分成多个部分

这将允许您在搜索所需的 1 时检查更少的数组元素。

创建一个包含 1980 个元素的容器对象，这些元素代表屏幕上 1980 年的“x”坐标。

var container={};

for(var x=1;x<=1980;x++){
    container[x]=[];
}

每个容器元素都是一个点对象数组，它们的点中心位于该 x 坐标上。

每个点对象都有足够的信息来定位和重绘自己。

x 坐标 == 125 处的点可以这样定义：

{x:125,y:100,r:2,color:"red",canvas:1};

当您想添加一个点时，将一个点对象推送到容器对象的相应“x”元素。

// add a dot with x screen coordinate == 952
container[952].push({x:952,y:100,r:2,color:"red",canvas:1});

可以根据点对象绘制点：

function drawDot(dot,context){
    context.beginPath();
    context.fillStyle=dot.color;
    context.arc(dot.x,dot.y,dot.r,0,PI2,false);
    context.closePath();
    context.fill();
}

当用户选择一个点时，您可以通过拉动用户单击的 X 周围的几个容器元素来快速找到它：

function getDotsNearX(x,radius){

    // pull arrays from "x" plus/minus "radius"
    var dotArrays=[]
    for(var i=x-radius;i<=x+radius;i++){
        dotArrays.push(container[i]);
    }
    return(dotArray);
}

现在您可以处理这些高度针对性的数组中的点，而不是处理所有 500 万个数组元素。

当用户将点移动到新位置时，只需将点对象从其当前容器元素中拉出并将其推入适当的新“x”容器元素中。

将您的点划分到多个重叠的画布上

为了提高绘图性能，您需要将点分布在多个相互重叠的画布上。

dot 元素包含一个 canvas 属性，用于标识将在哪个画布上绘制该点。