ブレゼンハムの線分描画アルゴリズム
文章：syun
日付：2005/9/10
目次
1.はじめに
2.入力と出力
3.アルゴリズム
1.はじめに
ブレゼンハムの線分描画アルゴリズムとは、
描画座標が「整数値」を取る場合に有効なアルゴリズムです。
例えば、青丸から緑丸への線分は以下のようになって欲しいですよね。
こういった線分を描画するアルゴリズムがブレゼンハムです。
このアルゴリズムを使えば、例えば戦術シミュレーションゲームでの
「最短経路の探索」などに応用することができます。
2.入力と出力
まず、入力と出力を押さえておきます。
入力となるのは、
となります。
これを元に、
- １ステップごとの座標を保持する配列（またはリスト）
例えば、開始座標を(1,1)、終了座標(4,6)とすると、
ret[0]→(1,1)
ret[1]→(2,2)
ret[2]→(2,3)
ret[3]→(3,4)
ret[4]→(3,5)
ret[5]→(4,6)
が出力となります。
3.アルゴリズム
以下の一時変数が必要になります。
- vNext（次の目標座標）
- vDelta（開始座標から終了座標までのベクトル）
- vStep（１ステップの増分）
そして、準備として以下の処理を行います。
- vNextに開始座標を代入
- vDeltaに（終了座標−開始座標）を代入
- vDeltaの値を元に、vStepに値を代入
- vDelta.x/yが0以上であれば、vStep.x/yに1を代入
- vDelta.x/yが0より小さければ、vStep.x/yに-1を代入
- vDeltaの値を２倍する
…で、メインアルゴリズムなのですが、、、。
その先は、次のソースコードを見て理解してください、、、。
手抜きでスミマセン…（´Д｀；
例えば、Pythonで実装すると以下のようになります。
class Vec2D:
def __init__(self, x=0, y=0):
self.x = x
self.y = y
# インスタンスのコピーを返す
def clone(self):
return Vec2D(self.x, self.y)
# ブレゼンハムの線分描画
# @return selfからvEndへのポイントリスト
def bresenham(self, vEnd):
# 準備
vNext = Vec2D(self.x, self.y)
vDelta = Vec2D(vEnd.x-self.x, vEnd.y-self.y)
vStep = Vec2D(1, 1)
if vDelta.x < 0:
vStep.x = -1
if vDelta.y < 0:
vStep.y = -1
vDelta.x = abs(vDelta.x*2)
vDelta.y = abs(vDelta.y*2)
pList = []
pList.append(vNext.clone())
# 線分の座標リストを作る
if vDelta.x > vDelta.y:
frac = vDelta.y*2 - vDelta.x
while vNext.x != vEnd.x:
if frac >= 0:
vNext.y += vStep.y
frac -= vDelta.x
vNext.x += vStep.x
frac += vDelta.y
pList.append(vNext.clone())
else:
frac = vDelta.x*2 - vDelta.y
while vNext.y != vEnd.y:
if frac >= 0:
vNext.x += vStep.x
frac -= vDelta.y
vNext.y += vStep.y
frac += vDelta.x
pList.append(vNext.clone())
return pList
大まかな流れとしては、
vDeltaのxとyを比較して、処理を２つに分けます。
そして、vDeltaをfracから引いたり足したりして、
ある条件を満たす・満たさないの場合分けをして、
vStepをvNextに足しこんでいます。