定義された領域の 2 次元空間で任意の長方形が占めるすべてのグリッド セルを計算できるアルゴリズムを探しています。長方形は、その 4 つのコーナーの座標によって定義されます。下の図では、そのうちの 2 つを赤でマークしました。グリッド セルの座標は黒です。位置合わせされていないグリッド (グリッドの中心!= 基になる座標系の中心) もカバーする一般的なケースを探していますが、セル座標間の変換 <=> 座標系は簡単で、既に実装されています。すべてのセルは正方形です。
計算は非常に短い時間で数千回行われるため、できるだけ速く実行する必要があります。
私が今していること：
現在、長方形のエッジ (AB、BC、CD、DA) を計算し、sampleRate = cellWidth / 4間隔を置いてサンプリングしています。AB + sampleRate * x中央のセルを見つけるために、 からから新しい行を作成しCD + sampleRate * x、 でそれらの行を再度サンプリングしsampleRateます。サンプリングされた各ポイントで見つけたすべてのセルを HashSet に入れて、重複を削除します。しかし、これは非常に非効率的だと感じています。
また、関連する領域のすべてのセルをバッファーに取り込み、範囲ツリーまたはインデックス ツリーを生成することも考えました。次に、長方形の境界をキューに入れ、含まれているすべてのセルを O(log n+m) で取得できますが、それを実装する方法がわからず、C# レンジ ツリーの実装も見つかりません。
コンピュータ グラフィックスに関する私の知識は非常にさびしいものですが、サンプリングせずに機能する簡単な幾何学的アプローチがあるはずではありませんか?