3

特定の有限線分の一部に接触または含まれているすべてのグリッドタイルを検索したいと思います。グリッドは2次元の通常のグリッドであるため、タイルの位置（行、列）から任意のタイルの中心を推定できます。逆に、2つの高速整数除算を使用して特定の浮動小数点座標からタイルの位置を計算できます。タイルは2次式で、たとえば0.25x0.25で、0.25がタイル幅として定義されています。次に、特定の線分が接しているすべてのタイルを決定する必要があります（floatで指定された2つの2Dポイントが線分を定義します）。私の現在のアプローチは、セグメントをタイル幅の半分の距離で等距離のポイントに分割することです（シャノンに挨拶します）。指定されたポイントを含むすべてのタイルを収集し、重複するタイルを削除するよりも。

編集：パトリシアが指摘したように、私の現在のアプローチでは、線がごくわずかにしか触れられていないタイルは含まれないため、完全なタイルセットにはなりません。私の場合、精度よりも速度の方が重要なので、これは私には受け入れられますが、それでも注意する必要があります。

明確にするために：画像内のすべての赤いタイルが必要ですが、速度を上げれば、たとえばバラのタイルなどを節約できます。

見つかったタイルのグリッド

4

3 に答える 3

5

問題は基本的に、ラスターイメージに線分を描画することです。

ピンクのタイルを惜しまない場合は、ブレゼンハムのアルゴリズムを使用してください。それ以外の場合は、アンチエイリアス処理された線を描画するために使用されるのと同様の手法を使用します。

セグメントの一方の端を含むタイルから開始し、それをキューに入れます。次に、通常のBFSアルゴリズムに従い、セグメントと交差するタイルのみをキューに入れます。

1回の反復で、キューの一方の端から1つのタイルを取得します。これは、次に見つかった交差するタイルです。次に、すべての隣接ノードを見つけて、セグメントと交差するもの（この場合は線との交差をテストするのに十分です）をキューのもう一方の端に配置します。隣接線は、線の方向に従って選択する必要があります。右下に行く場合は、下、右、右下のタイルを隣接タイルとして使用し、上に移動する場合は、上にある隣接タイルのみを使用します。

セグメントのもう一方の端を含むタイルに到達すると、終了します。

于 2012-11-12T22:23:49.010 に答える
1

同じ勾配符号を持つタイルの対角線に対して、線の勾配をテストします。タイルの対角線よりも急な場合は、次のようにx座標とy座標を交換します。

グラデーションがタイルの対角線よりも浅く、線が特定のタイルに接触または交差し、タイルに終点が含まれていない場合、タイルのエッジとの交点の少なくとも1つはタイルのx境界上にある必要があります。

線の端ごとに、端点を含むタイルまたは端点に接触しているタイルを収集します。

2つの終点のx座標間のタイルエッジである各x座標について、線のy座標を計算します。そのポイントに触れているタイルを収集します。

これはすべて、勾配チェックを行うためにせいぜい2、3の分割で行うことができると思います。主なプロセスは、すべての乗算、加算、および比較です。

于 2012-11-12T22:20:42.783 に答える
1

線分の終点が与えられると、線の方程式を簡単に計算できますy = mx + b。また、セグメントの長さが与えられると、パラメトリック形式を計算できます。

x = x0 + ft
y = y0 + gt

これらの方程式のいずれかが与えられると、ライン上のy任意の座標の座標を計算できます。xそれで ...

線の最初の終点から開始して、その点を含むセルがセットに含まれていることがわかります。各セルの座標がわかっているので、線分がセルの境界を横切る座標をxすばやく決定できます。yそのy座標がセルの最上位y座標より上にある場合、線分は開始セルの上のセルと交差します。（線の勾配が「下」の場合は、「下」に置き換えます。）

軸に沿ったセル境界ごとにそのテストを繰り返すとx、セグメントが交差するすべてのセルのリストが表示されます。

于 2012-11-12T22:31:28.323 に答える