巨大な 2-D 画面 (40000 * 40000 ポイント) に関する問題を解決しようとしています。無効な点がいくつかあり、長方形のウィンドウが表示されています。長方形のウィンドウ内に収まる無効なポイントの左上にあるすべてのポイントも無効になります。
次のような操作をサポートするデータ構造を構築する必要があります。1) 作業する必要がある有効なポイントの数を見つけます。2) 特定のポイントが有効かどうかを問い合わせます。
私の調査に基づいて、セグメント/インターバル ツリーを検討しましたが、それらを完全に理解することはできず、2 次元の点を処理できるかどうかもわかりません。
上記の操作を可能にするデータ構造の詳細な説明を含む素敵な記事/実装を誰か教えてもらえますか?
ありがとう、ロヒット
これは、今年の facebook ハッカーカップの「デッド ピクセル」問題です。コードと説明を含む公式のソリューションを参照してください。
長方形のウィンドウ内に収まる無効なポイントの左上にあるすべてのポイントも無効になります。
したがって、x1,y1 が無効で、x2<=x1 および y2<=y1 の場合、x2,y2 も無効です。その場合、定義点、つまりすべての無効な長方形の右下点の順序付きリストを保存します。リストは と のように並べることができx[i+1] > x[i]ますy[i+1] < y[i]。これは、他のポイントによってすでに無効であることが暗示されているすべてのポイントを省略した場合に機能します。この順序付けられたリストで、操作を実行できます。
1）私が取り組まなければならない有効なポイントの数を見つけます。
リストを反復処理し、各ポイントに対して長方形のストリップを使用して、そのようなストリップが 2 つ重ならないようにすることができます。
2) 特定のポイントが有効かどうかを問い合わせます。
ポイントが与えられた場合、xp,yp二分探索を使用して、このポイントを無効にする定義ポイントを見つけることができます。定義点の座標が小さすぎるxと高い位置を探す必要があり、y座標が小さすぎると低い位置を探す必要があります。どちらも小さすぎる場合は、そのピクセルが有効であることがわかります。そうしないと、両方の座標が十分に大きいものを見つけることができます。つまり、指定したピクセルも無効になります。