23

私は私の古いプロジェクトを捨てています。それがしなければならなかったことの1つは-デカルトグリッドシステムとグリッド上の2つの正方形が与えられた場合、それらの2つの正方形の中心を結ぶ線が通過するすべての正方形のリストを見つけます。

ここでの特殊なケースは、すべての開始点と終了点が正方形/セルの正確な中心に限定されることです。

ここにいくつかの例があります-サンプルの開始点と終了点のペアを使用します。影付きの四角は、それぞれの関数呼び出しによって返される必要がある四角です。

死んだImageShackリンクを削除しました-例

始点と終点は、それらが入っている正方形で参照されます。上の図では、左下がであると仮定すると、[1,1]右下の線はとして識別さ[6,2]れ[9,5]ます。

つまり、左から6列目の（中央の）正方形から2行目の下から9列目の（中央の）正方形まで、下から5行目です。

これは実際にはそれほど複雑ではないようです。しかし、どういうわけか、オンラインで複雑なアルゴリズムを見つけて実装したようです。

とても、とても速かったことを覚えています。同様に、フレームごとに数百回または数千回の速度で最適化されます。

基本的に、線（線がグリッド線と交差する点）に沿って、正方形の境界から境界へとジャンプしました。次の交差点がどこにあるかを知るには、水平方向と垂直方向のどちらの交差点が近いかを確認し、次の交差点に移動しました。

これは概念的には大丈夫ですが、実際の実装はそれほどきれいではないことが判明し、最適化のレベルが実際に必要なものに対して高すぎる可能性があることを恐れています（私はこのトラバーサルと呼んでいます）アルゴリズムはおそらく1分間に5〜6回）。

シンプルでわかりやすく、透明な直線グリッド走査アルゴリズムはありますか？

プログラム用語で：

def traverse(start_point,end_point)
  # returns a list of all squares that this line would pass through
end

ここで、指定された座標は正方形自体を識別します。

いくつかの例：

traverse([0,0],[0,4])
# => [0,0], [0,1], [0,2], [0,3], [0,4]
traverse([0,0],[3,2])
# => [0,0], [0,1], [1,1], [2,1], [2,2], [3,2]
traverse([0,0],[3,3])
# => [0,0], [1,1], [2,2], [3,3]

コーナーを直接移動する線には、線の「翼」に正方形を含めないでください。

（古き良きブレゼンハムはここで機能するかもしれませんが、私が望むものから少し逆になっています。私が知る限り、それを使用するには、基本的にそれを線に適用してから、上のすべての正方形をスキャンする必要があります真または偽のグリッド。大きなグリッドの場合は実行不可能（または少なくともエレガントではない））

（私の誤解のため、ブレゼンハムとブレゼンハムベースのアルゴリズムを再検討しています）

明確にするために、これの1つの可能なアプリケーションは、ゾーン（グリッド）内のゲームにすべてのオブジェクトを格納していて、光線があり、光線がどのオブジェクトに接触するかを確認したい場合です。このアルゴリズムを使用すると、マップ上のすべてのオブジェクトではなく、指定されたゾーン内にあるオブジェクトのみに対して光線をテストできます。

私のアプリケーションでこれを実際に使用すると、すべてのタイルに効果が関連付けられ、オブジェクトは毎ターン特定の線分を移動します。毎ターン、オブジェクトが通過したマス目、つまりオブジェクトに適用する効果を確認する必要があります。

この時点で、私が持っている現在の実装は機能することに注意してください。この質問は主に好奇心を目的としています。このような単純な問題には、もっと簡単な方法が必要です...どういうわけか...。

私は正確に何を探していますか？概念的に/きちんとしていてきれいなもの。また、正確に指定しているため、すべての開始点と終了点は常に正方形/セルの中心にあることに気付きました。だから、おそらくそれを利用する何かもきちんとしているでしょう。

4

4 に答える 4

20

必要なのは、幾何学的オブジェクトが交差するすべてのピクセルであるスーパーカバーの特定のケースです。オブジェクトは線または三角形であり、より高い次元への一般化があります。

とにかく、これが線分の1つの実装です。そのページはまた、スーパーカバーをブレゼンハムのアルゴリズムの結果と比較しています-それらは異なります。 （ソース：free.fr）代替テキスト

そこでのアルゴリズムをエレガントでクリーンなものと見なすかどうかはわかりませんが、コードを適応させてプロジェクトの他の部分に進むのに十分簡単なようです。

ちなみに、あなたの質問は、ブレゼンハムのアルゴリズムが大きなグリッドに対して効率的ではないことを意味します。それは真実ではありません-それはライン上のピクセルだけを生成します。グリッド上のすべてのピクセルに対してtrue/falseテストを実行する必要はありません。

更新1：写真には、線が通過しないと思われる2つの「余分な」青い正方形があることに気づきました。それらの1つは、「このアルゴリズム」の「h」に隣接しています。それがアルゴリズムまたは図のエラーを反映しているかどうかはわかりません（ただし、以下の@kikitoのコメントを参照してください）。

一般に、「難しい」ケースは、線がグリッドポイントを正確に通過する場合です。浮動小数点を使用している場合、これらの場合、浮動小数点エラーが混乱する可能性があると推測します。言い換えれば、アルゴリズムはおそらく整数演算に固執する必要があります。

アップデート2： 別の実装。

于 2010-07-13T03:52:58.450 に答える
6

このトピックに関する論文はここにあります。これはレイトレーシングに関するものですが、とにかくそれはあなたが何を求めているかに非常に関連しているようで、少し作業できると思います。

同様のことを扱った別の論文もここにあります。

これらの論文は両方とも、レイトレーシングに関するJakko Bikkerの優れたチュートリアルのパート4にリンクされています（彼のソースコードも含まれているため、彼の実装を参照/調べることができます）。

于 2010-07-13T03:12:47.807 に答える
4

線形時間で実行される問題の非常に簡単なアルゴリズムがあります。

  1. 2つの点AとBが与えられた場合、この間隔内にある、グリッドのすべての垂直線との線（A、B）の交点を決定します。
  2. ポイント1からのリストの開始/終了で、AとBを含むセル内に2つの特別な交点を挿入します。
  3. 連続する2つの交点ごとに、軸に整列した長方形の最小ベクトルと最大ベクトルとして解釈し、この長方形の内側にあるすべてのグリッドセルにマークを付けます（これは非常に簡単です（2つの軸に整列した長方形の交差）。特に、長方形に幅があることを考慮してください）。 1のため、グリッドの1列のみを占有します）
例：
+------+------+------+------+
|      |      |      |      |
|      |      | B    *      |
|      |      |/     |      |
+------+------*------+------+
|      |     /|      |      |
|      |    / |      |      |
|      |   /  |      |      |
+------+--/---+------+------+
|      | /    |      |      |
|      |/     |      |      |
|      *      |      |      |
+-----/+------+------+------+
|    / |      |      |      |
*   A  |      |      |      |
|      |      |      |      |
+------+------+------+------+

「A」と「B」は、「/」で表される線を終了する点です。「*」は、線とグリッドの交点を示します。AとBを含むセルをマークし、Ax == Bxのような特殊なケースを処理するには、2つの特殊な交点が必要です。

最適化された実装では、ライン（A、B）に対してΘ（| Bx --Ax | + | By --Ay |）時間が必要です。さらに、実装者にとってより簡単な場合は、このアルゴリズムを記述して、水平グリッド線との交点を決定できます。

更新：ボーダーケース

brainjamが彼の答えで正しく指摘しているように、線がグリッドポイントを正確に通過する場合、難しいケースがあります。このような場合が発生し、浮動小数点演算が整数座標の交点を正しく返すと仮定します。この場合、提案されたアルゴリズムは正しいセルのみをマークします（OPによって提供された画像によって指定されます）。

ただし、浮動小数点エラーは遅かれ早かれ発生し、誤った結果をもたらします。私の意見では、doubleを使用しても十分ではなく、Decimal数値タイプに切り替える必要があります。最適化された実装では、そのデータ型に対してΘ（| max.x --min.x |）の加算が実行され、それぞれにΘ（log max.y）時間がかかります。つまり、最悪の場合（（0、0）、（N、N））、巨大なN（> 10 6）の場合、アルゴリズムはO（N log N）の最悪の場合の実行時間に低下します。線の傾き（A、B）に応じた水平グリッド線交差検出は、この最悪の場合には役立ちませんが、平均的な場合には確かに役立ちます-プロファイラーがDecimal操作を生成する場合にのみ、このようなスイッチを実装することを検討しますボトルネックになります。

最後に、賢い人の中には、この国境のケースを正しく処理するO（N）ソリューションを思い付くことができるかもしれないと想像できます。あなたの提案はすべて大歓迎です！

修正

brainjamは、たとえば1/3を正しく表現できないため、任意精度の浮動小数点数を表現できたとしても、10進データ型は満足のいくものではないと指摘しました。したがって、境界ケースを正しく処理できる分数データ型を使用する必要があります。Thxブレインジャム！:)

于 2010-07-13T10:43:48.013 に答える
0

これは、numpyを使用したPythonでの簡単な実装です。ただし、ここで使用されるのは、かなり一般的な2Dベクトルとコンポーネントごとの操作のみです。結果は私には非常にエレガントに見えます（コメントなしで〜20loc）。

これは、タイルが整数座標を中心としていると想定しているため、一般的ではありませんが、各整数に半分（0.5、1.5、2.5など）を加えたものに分離線が表示されます。これにより、丸めを使用してワールド座標からタイルの整数座標を取得でき（特別な場合には実際には必要ありません）0.5、最後のタイルに到達したかどうかを判断するためのマジックナンバーが得られます。

最後に、このアルゴリズムは、交差点でグリッドを正確に横切るポイントを処理しないことに注意してください。

import numpy as np

def raytrace(v0, v1):
    # The equation of the ray is v = v0 + t*d
    d = v1 - v0
    inc = np.sign(d)  # Gives the quadrant in which the ray progress

    # Rounding coordinates give us the current tile
    tile = np.array(np.round(v0), dtype=int)
    tiles = [tile]
    v = v0
    endtile = np.array(np.round(v1), dtype=int)

    # Continue as long as we are not in the last tile
    while np.max(np.abs(endtile - v)) > 0.5:
        # L = (Lx, Ly) where Lx is the x coordinate of the next vertical
        # line and Ly the y coordinate of the next horizontal line
        L = tile + 0.5*inc

        # Solve the equation v + d*t == L for t, simultaneously for the next
        # horizontal line and vertical line
        t = (L - v)/d

        if t[0] < t[1]:  # The vertical line is intersected first
            tile[0] += inc[0]
            v += t[0]*d
        else:  # The horizontal line is intersected first
            tile[1] += inc[1]
            v += t[1]*d

        tiles.append(tile)

    return tiles
于 2019-07-09T03:04:13.037 に答える