three.js勉強日誌 【No.7】
ディジタル画像とアルゴリズム2

ディジタル画像とアルゴリズム2

2015年4月1日 NO.7

円のラスタ化

先日のブログでは、直線のラスタ化について記事を書いきましたが、本日は円のラスタ化について書いていこうと思います。(今回の記事は短いです。)

円を８つに均等に割ることを考えます。 0度から45度の部分、以後第一八分円と呼びます。 第一八分円は$$y=x$$にたいして、第二八分円(45度から90度)と対称です。 もし、第一八分円が発生できたならば、$$y=x$$に関して線対称変換を行い第二八分円の生成が可能となり、第一象限において円弧を生成する事ができます。 この第一象限の円弧を$$x=0$$においてまら線対称変換を行うことで、半円ができ、その半円を$$y=0$$で線対称変換を行うことで円ができます。 さて、つまり第一八分円さえ出来てしまえば、円は作成できます。

八分円を作成するアルゴリズム

では、八分円を作成するとします。 半径Rの八分円を反時計回りに作成します。 $$(x_i,y_i)$$が一つ前の点だとしたら、次の点は$$(x_{i+1},y_i)$$か$$(x_{i+1},y_{i+1})$$もしくは$$(x_i,y_{i+1})$$のみしか進みません。すなわち、左に進むか、上に進むか、斜め左上に進むかしか選択肢はないのです。 選択のアルゴリズム自体はごく当たり前なアルゴリズムなのですが、円の本来の 点ともっとも近い点を３点から選びます。 具体的な計算としては、
$$m=(x_{i+1})^2+(y_i)^2-R^2$$ $$m=(x_{i+1})^2+(y_{i+1})^2-R^2$$ $$m=(x_{i})^2+(y_{i+1})^2-R^2$$ をして各mの絶対値をとり最小の値を選択します。 これを繰り返すことで八分円は作成され、円は生成されます。