c++ - 線分と交差するすべてのタイルを見つける

Question

線分と交差するすべてのタイルを見つける必要がありますが、ブレゼンハムの線アルゴリズムは私の要件に適合しません。すべてのセルを見つける必要があります。交点を知る必要はなく、交点の事実だけを知る必要があります。手伝ってくれてありがとう。

線の方向ベクトルを見つけ、タイルサイズで分割して段階的にセルを見つけることを考えました。しかし、正しいステップサイズを選択する方法がわかりません。1 px のステップは悪いと思います。

Answer 1

2D と 3D の場合については、Amanatides と Woo の記事「A Fast Voxel Traversal Algorithm for Ray Tracing」を参照してください。実用的な実装。

Answer 2

http://www.cut-the-knot.org/Curriculum/Calculus/StraightLine.shtmlまたはhttp://mathworld.wolfram.com/Line.htmlにある多くの直線方程式の 1 つを使用できます。

座標系に 2 つの点を通る線があると仮定すると、y=mx+n方程式を推測し、タイルと照合して、座標系の単位で x をタイルの最小の x から任意の方向に移動しながら、それらが交差するかどうかを確認します。最大まで。座標系が画面の場合、1 ピクセルで十分です。

これは、あなたが直面している問題の正確な性質について詳しく知らなくても、私が正しく知っていることをほのめかすことができるクローズです.

Answer 3

Bresenham のアルゴリズムを変更して、必要なものを追跡するのは簡単です。アルゴリズムの関連するフラグメントは次のとおりです。

plot(x,y);
error = error + deltaerr;
if (error >= 0.5)
{
    y = y + ystep;
    error = error - 1.0;
}

すべてのセルを追跡するには、別の変数が必要です。厳密なチェックはしていませんのでご了承ください。

plot(x,y);
olderror = error.
error = error + deltaerr;
if (error >= 0.5)
{
    y = y + ystep;
    error = error - 1.0;
    extra = error+olderror;

    if (extra > 0)
    {
      plot (x,y); /* not plot (x-1,y); */
    }
    else if (extra < 0)
    {
      plot (x+1,y-1); /* not plot (x+1,y); */
    }
    else
    {
      // the line goes right through the cell corner
      // either do nothing, or do both plot (x-1,y) and plot (x+1,y)
      // depending on your definition of intersection           
    }
}