如何高效地在當前圖形區域繪製可見對象？

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

將整個區域分解成不連續的區域，將您的對象分成這些區域，並只渲染那些可見的區域。

更新它們所屬的區域（如果它們移動的話）。