2 つのビットマップがあり、ピクセルが 4 つの角 (四角形) で定義された領域内にある場合にのみ、ピクセルを A から B にコピーしたいと考えています。ビットマップ A と B は同じサイズで、四角形は画像のピクセル空間の 4 つの {x,y} 座標として定義されます。
最悪の場合、クワッドに対して各ピクセルの中心をテストして、ピクセルの中心がクワッドの内側にあるかどうかを確認できますが、これは非常に遅いです。より良いアルゴリズムは何ですか?
1 に答える
7
四角形が凸面の場合、次のアルゴリズムを使用できます。
短いバージョン: 各スキャンライン (水平ビットマップ ライン) について、そのスキャンラインと交差するエッジを見つけ、それらの間のピクセルをコピーします。
長いバージョン: スキャンラインごとに移動します。上部の頂点 (最小の y) から開始し、左側と右側のエッジを追跡します。各 y 値について、2 つのエッジの x 値を計算します (直線方程式を直接使用するか、ブレゼンハムのアルゴリズムを使用します)。次に、(xLeft,y) から (xRight,y) までのピクセルを 2 番目のビットマップにコピーします。
エッジの端にある頂点に到達したら、その頂点に接続されている他のエッジに切り替えます。これを下の頂点に到達するまで続けます。
凹型クワッドの場合、これはより複雑になります。同様のアルゴリズムを使用できますが、一部のスキャンラインでは、スキャンラインと交差する 4 つのエッジがあります。その場合、エッジ #1 から #2、および #3 から #4 の間のピクセルをコピーする必要があります (エッジは x 値で並べ替えられます)。もう 1 つのオプションは、クワッドを 2 つの三角形に分割し、それらに対して上記のアルゴリズムを使用することです。
于 2010-06-26T22:32:35.000 に答える