1

考慮
ここに画像の説明を入力
してください: 目的は、任意の線分 (赤い線) を、任意のグリッド (青い線分) に整列された一連の接続された線分に離散化することです。ここでは、グリッドの 2 つの単純な形式、つまり、正方形グリッドと回転した正方形グリッドのみが示されています。赤い線は、任意の角度とサイズにすることができます。タイプとセル サイズを含むグリッド構成は、ユーザーの選択次第です。Bresenham の離散化は単純なケースではうまくいくかもしれませんが、それでも 2 つの障害があります。

  1. 垂直および水平に配置されたグリッドに限定されます。
  2. 線分が必要なピクセル (つまり、正方形のブロック) を指定します。

重要な更新: 重要な更新: グリッドの複雑さに対して機能する一般的なソリューションに関心があります。 ここに画像の説明を入力

より一般化されたアプローチが興味深い。疑似コードまたはコードの提供は非常に高く評価されています。この質問もここにあります。

4

1 に答える 1

0

回転した長方形グリッドの場合:

  • 線分の端点に逆回転変換を適用する
  • 従来のハーフ ピクセル オフセットなしで Bresenham を使用します (ピクセル ブロックを中央に配置するため)。
    • アルゴリズムは、水平および垂直 [または短軸、長軸] の増分を与えます
  • 線分に正転変換を適用する

「ランダム」グリッドの場合、セルベースのアプローチを使用することをお勧めします。必要に応じて、各セルが最初に凸面 (ボロノイ領域) に分割されます。例えば。六角形グリッドはすでにボロノイ領域で構成されています。各セルの隣接リストを保持します。

  • 最初のタスクは、開始セルから終了セルまで、各セルの隣接部分のみを通過することです。幸いなことに、凸テッセレーションの場合、中心がターゲットに近い/最も近いセルを選択できます。(進行不能の場合、検索は終了します)。

  • 次のタスクは、各セルの入口点から出口点までのパス (時計回りまたは反時計回り) を見つけることです。1つは短いです。

形： 

a----------b--------------d  
*          |              |  
     A     c       B      |     C
                          e
                          |           x
                          f-----------g

ここで、端点「*」と「x」はセルの境界にあります。パターン '*abcbdefgx' を形成し、それを '*abdfgx' または '*adfgx' に縮小します。これは、'ba' ドット 'db' (正規化) がゼロまたは少なくとも非常に近いためです。

于 2012-10-28T06:34:50.523 に答える