[School_ĐHMT] 線を引くための中間点アルゴリズム

12月 16, 2014 nguyenvanquan7826 学校コンピューターグラフィックス応答を残し

コンテンツ
構成アルゴリズム
続きを読む
1. 直線を描くの一般原則
 2. 線を引くためのDDAアルゴリズム
 3. アルゴリズムBreshenhamは直線を引く

構成アルゴリズム
与える 2 エンドポイントM1(X1, Y1), とM2(X2, Y2). M1を介して式ライン, M2フォーム
$\frac{x-x1}{y-y1} = \frac{x2-x1}{y2-y1} \\ \Leftrightarrow \left ( y2-y1 \right )x - \left ( x2-x1 \right )y + x2y1-x1y2 \\ \Leftrightarrow Ax + By + C = 0 \\ Voi \indent A = Dy, B = -Dx, C = x2y1-x1y2$
中間点

ステップk 1で我々は、xを1単位だけ増加され、整数xに係る医療算出シークを行う. Sを呼び出し, 座標Pそれぞれのポイント $(x_{k} + 1, y_{k}) , (x_{k} + 1, y_{k} + 1), M(x_{k} + 1, y_{k} + 0.5)$ SPの中間点 (ポイント中点), Qが探しています. ポイント $Q(x_{k} + 1, y)$ 値は、点Mよりも、点Qの位置に依存する. QがM未満である場合、我々は、点Sを取る $(y = y_{k})$ , 逆の点Pをとる $(y = y_{k} + 1)$ .
セット $F(x, y) = Ax + By + C = 0$ . 私が持っている:
M1M2 Mのポイント <=> F(M) = 0.
M1M2上記Mポイント <=> F(M) < 0.
ポイントMはM1M2の下にある <=> F(M) > 0.
Mの位置を決定するために、我々は一定の符号を考える $P_{k} = 2F(M) = 2A(x_{k} + 1) + 2B(y_{k} + 0.5) + 2C$ .
+/ もし $P_{k} < 0$ , M上に横たわるM1M2はその後、Qは、我々はポイントSを取るのMすなわち下にある $y = y_{k}$
$=> P_{k+1} = 2A(x_{k} + 1) + 2B(y_{k}) + 2C = 2A(x_{k}) + 2B(y_{k}) + 2C + 2A = P_{k} + 2Dy$
+/ もし $P_{k} \geq 0$ , またはその後、QはMに位置していますM1M2の下に属するM我々は、Pのニュースを入手 $y = y_{k} + 1$
$\Rightarrow P_{k+1} = 2A(x_{k} + 1) + 2B(y_{k} + 1) + 2C \\ \indent \indent = 2A(x_{k}) + 2B(y_{k}) + 2C + 2A + 2B \\ \indent \indent = P_{k} + 2(Dy - Dx)$
今、私たちは初期値P1を計算.
$P_{1} = 2A(x_{1} + 1) + 2B(y_{1} + 0.5) + 2C \\ \indent \indent = 2Ax_{1} + 2By_{1} + 2C + 2A + B\\ \indent \indent = 2(Ax + By + C) + 2Dy - Dx \\ \indent \indent = 2Dy - Dx \\ \indent \indent(Ax + By + C = 0)\\$
私はシンプルを構築するために同一の結果Breshenhamアルゴリズムで計算するための中点アルゴリズムに気づいたが、はるかに.