現在の図面ビューに表示されているグラフィックス オブジェクトのみを効率的に選択するにはどうすればよいですか?
私は、何十億ものオブジェクトをグラフ化するために、オープン ソースのグラフ作成ライブラリである ZegGraph を使用しています。ZedGraph の設計では、すべてのオブジェクトをループし、オブジェクトの左上隅と高さと幅を考慮して、現在のスケーリングされたビューに表示されるかどうかを計算します。数千のアイテムでは問題ありませんでしたが、数百万のアイテムでは遅くなります。現在、PC メモリを超える数十億のアイテムがあるため、それらをディスクにキャッシュしています。もちろん、ディスクからそれらすべてをループして、現在のビューにあるほんの一握りを見つけることは考えられません。
便利な制約の 1 つは、すべてのオブジェクトが十分に近い垂直座標を持っているため、それらが水平に表示されている場合、90% の確率で表示されるということです。つまり、アルゴリズムは、可視領域と重なるかどうかにかかわらず、左端と右端に基づいてオブジェクトを簡単に見つけることができます。
私が最初に考えたのは、それらを左隅の X 座標でソートしておくことでした。ただし、オブジェクトの幅はさまざまで、可視領域よりも大きくなる可能性があるため、左隅が画面からはみ出しても、オブジェクトが部分的に表示される場合があります。
もちろん、X1 と X2 が領域の左端と右端であり、x1 と x2 が各オブジェクトの左端と右端であるとすると、x1 < X2 および x2 > X1 を持つすべてのオブジェクトが必要です。
これまでのところ、オブジェクトへの参照を含むすべての x1 (左端) の短縮リストを保持しているようです。また、各オブジェクトへの参照を含むすべての x2 (右端) のソート済みリスト。
次のステップは、バイナリ検索を使用して x1 < X2 条件を満たす x1 リストの最初のものを見つけることですか? 次に、x2 > X1 条件を満たす最初の x2 リストを見つけますか?
しかし、すべてのアイテムをスキャンせずに x1 と x2 の交点を見つけるにはどうすればよいでしょうか。