凸四角形同士の転送ルーチン(2) - melpon日記 - HaskellもC++もまともに扱えないへたれのページ

大まかなアルゴリズムについては前回（id:melpon:20061025）で書きました。
それをもうちょっと詰めて考えてみます。

前回みたいに、毎ループ交点を求めていたのでは結構なネックになってしまうので、ここを最適化することを考えてみます。
同じ直線と交差するループでは、転送先の Y の値が１つ増えたときの、転送先の X の増分、転送元の X,Y の増分をそれぞれ求めてやり、ループするたびにその増分を足してやれば、そこが交点になります。

まず、?の場所（ $y=0$ ）での交点を求めます。そしてその交点から一番近い高さの点の位置（?）を求めます。
このとき、最初の点 $A_d$ を $(px_1,py_1)$ 、その交点から一番近い高さの点 $D_d$ を $(px_2,py_2)$ とし、それに対応した転送元の点 $A_s,D_s$ をそれぞれ $(px_3,py_3)$ 、 $(px_4,py_4)$ とすれば、 $py_1$ が１増えたときの転送先 X、転送元 X,Y のそれぞれの増分 $dx_2,sx_2,sy_2$ は、
$\begin{array}dx_2&=&\frac{px_2-px_1}{py_2-py_1}\\sx_2&=&\frac{px_4-px_3}{py_2-py_1}\\sy_2&=&\frac{py_4-py_3}{py_2-py_1}\end{array}$
となり、これを使えば高速に交点を求めることが可能になります。

あとは同様にして、この転送先の X の値が一つ増えたときの、転送元の増分を計算して、毎ループその値を加算して転送してやります。

転送先の交点の位置を $(RX_1,Y),(RX_2,Y)$ とし、転送元の交点の位置を $(PX_1,PY_1),(PX_2,PY_2)$ とすれば、転送先の X が１増えたときの転送元 X,Y のそれぞれの増分 $SX,SY$ は、
$\begin{array}SX&=&\frac{PX_2-PX_1}{RX_2-RX_1}\\SY&=&\frac{PY_2-PY_1}{RX_2-RX_1}\end{array}$
となり、この増分 $SX,SY$ を毎ループ加算して転送すれば完成です。