左上隅と右下隅（すべて整数座標）で定義された軸平行な2次元長方形のセットがあります。ポイント クエリが与えられた場合、それが長方形の 1 つに含まれているかどうかを効率的に判断するにはどうすればよいでしょうか? はい/いいえの答えが必要なだけで、それがどの長方形にあるかを心配する必要はありません。
(x,y) が ((x1, y1), (x2, y2)) にあるかどうかは、x が x1 と x2 の間にあり、y が y1 と y2 の間にあるかどうかを確認することで確認できます。これは、長方形の数で線形時間で実行される各長方形に対して個別に行うことができます。しかし、私はたくさんの長方形を持っていて、たくさんのポイント クエリを実行するので、もっと速いものが欲しいです。
さまざまな 2D ジオメトリ クエリで私のお気に入りはSweep Line Algorithmです。それはCADソフトウェアで広く利用されていますが、これはあなたのプログラムの目的について私の勝手な推測です。
基本的に、X 軸に沿ってすべてのポイントとすべてのポリゴン頂点 (この場合は 4 つの四角形の角すべて) を並べ、X 軸に沿ってあるポイントから次のポイントへと進みます。マンハッタン以外のジオメトリの場合、セグメントの交点である中間点も導入します。
データ構造は、現在の X 位置で Y 方向に並べられた、点とポリゴン (長方形) エッジの交点のバランスの取れたツリーです。構造が適切に維持されていれば、現在の X 位置にあるポイントが長方形に含まれているかどうかを判断するのは非常に簡単です。ポイント エッジの交点に垂直に隣接する Y 方向を調べるだけです。長方形が重なったり、長方形の穴が開いたりすることが許可されている場合は、もう少し複雑になりますが、それでも非常に高速です。
N 個の点と M 個の長方形の全体的な複雑さは O((N+M)*log(N+M)) です。これが漸近的に最適であることを実際に証明できます。