3

Bresenham のアルゴリズムは、ピクセルなどの正方形のグリッドに線を描画するために使用されます。

このアルゴリズムの一部は、平面をオクタントと呼ばれる 8 つの部分に分割することに基づいています。

オクタント

トリックは、対称性を使用して、2 番目のポイントがどこにあるかに関係なく、アルゴリズムを一般化することです。まず、最初の八分円に「移動」し、次に計算が行われ、最後に、生成されたポイントが元の八分円に変換されます。

ウィキペディアは、トリックを実行するための基本的な機能を提供します。

 function switchToOctantZeroFrom(octant, x, y) 
   switch(octant)  
     case 1: return (x, y)
     case 2: return (y, x)
     case 3: return (y, -x)
     case 4: return (-x, y)
     case 5: return (-x, -y)
     case 6: return (-y, -x)
     case 7: return (-y, x)
     case 8: return (x, -y)

さらに、次のことを行う必要があると書かれています。

入力と出力の座標系を反転する

これは、これらの転置が実際には退縮であるという事実に基づいています。f(f(x)) = x

あまり気にせずに、最初はうまくいくと思いました。

ただし、ケース 3 と 7 の場合は、退縮ではないため機能しません。

例えば：

Case 4: (-5, 1) => (5, 1) => (-5, 1) // Good
Case 3: (-1, 5) => (5, 1) => (1, -5) // Not good

もう一度トリックを実行する必要があります。

Case 3: (-1, 5) => (5, 1) => (1, -5) => (-5, -1) => (-1, 5) // Good

それで、私は何かを誤解しましたか？

それとも、ウィキペディアの記事の草稿の正確さの欠如であり、誰かがそれを改善する必要がありますか?

switchToOctant_onInput2 つの関数を使用せずにこれらの遷移を行うより良い方法はありませんswitchToOctant_onOutputか?

4

2 に答える 2

2

オクタント 2、4、6、8 は、インボリュティブ (自己反転) であるリフレクションによってオクタント 1 にマッピングされます。オクタント 5 は、180 度の回転によってオクタント 1 にマッピングされますが、これもまた involutive です。ただし、オクタント 7 と 3 は、非ボリューティブではない +-90 度の回転によってオクタント 1 にマッピングされます。マッピングは単に複雑ではないため、それについてできることは何もありません。逆関数が必要な場合は、それを作成する必要があります。

ウィキペディアのページは、関数が退縮を示唆する「反転」であると述べているため、誤解を招く可能性があります。

この問題に対処するために私が考えることができる 3 つのアプローチがあります。2) 逆関数を表す負のオクタントのケースを追加して、 の逆関数がswitchOctant(3,x,y)とswitchOctant(-3,x,y)同じになるようswitchOctant(7,x,y)にします (ただし、これを行う場合は、オクタント 0 について慎重に検討する必要があります)。または 3) 線画機能を強化することで、幾何学的変換機能の必要性を軽減または排除します。特に、第 1 象限 (第 1 八分円だけでなく!) の任意の線を処理するように線描画機能を拡張すると、任意の象限を第 1 象限に写像する幾何学的変換を使用できます。

アップデート

この質問についてもう 1 つの「角度」を考えました (いわば): 反射によって 3 番目のオクタントを 1 番目のオクタントにマッピングすることが可能です。原点を通り傾きθをもつ直線による鏡映は、次の式で与えられます。

x' = x * cos(2*theta) + y * sin(2*theta)
y' = x * sin(2*theta) - y * cos(2*theta)

1 番目と 3 番目の八分円の間の反射線には傾斜theta = 45 + 45/2.0度があるので、2*theta = 135度と

x' = -sqrt(2)/2 * x + sqrt(2)/2 * y
y' =  sqrt(2)/2 * x + sqrt(2)/2 * y

同様の式を使用して、7 番目のオクタントを 1 番目のオクタントにマップできます。したがって、各八分円を最初の八分円にマッピングするインボリューションを見つけることができます。(x,y)ただし、このマッピングには 2 つの問題があります。1) ウィキペディアの記事に示されているマッピングは連続的ですが、連続的ではありません (点が平面上を移動するときに、画像に突然のジャンプがないことを意味します)。2) 整数演算を使用してマッピングを行う方法が明確ではありません。

継続性は単なる理論上の問題ではありません。2 つの八分円の境界にポイントをマッピングする方法を検討すると、実用的になります。不連続なマップでこれを慎重に行わないと、間違いなく間違った結果が得られます。

したがって、この考えは良くありませんが、完全を期すために言及したいと思いました。

于 2015-07-11T15:35:40.800 に答える