如何高效地在当前图形区域绘制可见对象？

Question

如何高效地选择在当前图纸视图中可见的图形对象？

我正在使用一个开源图表库ZegGraph来绘制数十亿个对象。 ZedGraph中的设计是循环遍历每个对象，并计算它是否在当前缩放视图中可见，并给出左上角以及对象的高度和宽度。对于成千上万的项目来说这样很好，但数百万人却变得很慢。现在我们拥有超过PC内存的数十亿项，因此我们将它们缓存到磁盘。当然，这是通过磁盘遍历它们来发现当前视图中的一小部分，这是不可想象的。

一个有用的约束是对象都具有足够接近的垂直坐标，以便如果它们水平可见，那么它们有90％的机会可见。这意味着该算法可以简单地根据左右边缘找到对象，而不管是否与可见区域重叠。

我的第一个想法是让它们按左角的X坐标排序。但是，物体可以具有不同的宽度，它们可以大于可见区域，因此左角可能不在屏幕上，但物体仍可能部分可见。

当然，由于X1和X2是区域的左右边缘，x1和x2是每个物体的左右边缘，我们需要每个物体都有x1和x2> X1。

到目前为止，似乎我们以某种方式保留了所有x1（左边缘）与对象引用的缩略列表。还有一个有关每个对象的引用的所有x2（右边缘）的排序列表。

那么下一步是在x1列表中找到第一个满足x1 < X2条件的二进制搜索？那么我们发现x2列表中的第一个满足x2> X1条件？

但是他们如何找到x1和x2的交叉点而不扫描每个项目？

Answer 1

将整个区域分解成不连续的区域，将您的对象分成这些区域，并只渲染那些可见的区域。

更新它们所属的区域（如果它们移动的话）。