🚀 go-pugleaf

sugiharaです。


Ken-ichiro Ueda wrote in message <353A4B04.7439F598@pluto.dti.ne.jp>...

>アルゴリズム本などに、ブレゼンハムという人が考えたＤＤＡという
>アルゴリズムがあると思いますので、探してみてください。書籍では
>Ｃによるアルゴリズム辞典だかという本にのっていたはずです。

 これは真っ先に思い付いたのですが、「点を打った数 ＝ ２点間の距離」とはなら
ないと思ったのですが・・・
 たとえば （０，０）－（４０，３０） という直線と （０，０）－（４０，１０）
という直線を考えたとき、２点間の距離は ５０ と ４１（少数を四捨五入）となる
はずですが、DDAだと両方とも４０（X軸の距離）となると思うのです。


kuno@gssm.otsuka.tsukuba.ac.jp wrote in message

>> アルゴリズム本などに、ブレゼンハムという人が考えたDDAというア
>> ルゴリズムがあると思いますので、探してみてください。書籍ではC
>> によるアルゴリズム辞典だかという本にのっていたはずです。
>
>  しかしこの場合、それよりも(dx = x1 - x2, dy = y1 - y2として)
>
>    r*r <= dx*dx + dy*dy < (r+1)*(r+1)
>
>なるrを2分探索で求める方が速くないでしょうか。だいたい距離に比例
>してよいんなら(dxがdyより小さいとして)rをdyからdx+dyまで1つずつ
>変化させてしらみつぶしに探すのがいちばん簡単だったりして。


これは簡単そうでよさそうですね。試してみます。



nide@ics.nara-wu.ac.jp wrote in message <6hectf$h6j@ns.h.kyoto-u.ac.jp>...

>  非負整数の平方根をニュートン法で整数部だけ求めるという方法でも良いか
>もしれません。これなら整数の加減乗除と比較だけで済みますし。ありうる問
>題は、二乗を計算することによるオーバーフローですが、画面上の2点の距離
>を求める用途ならこの問題は考えなくとも良さそうですね。


ニュートン法ですね。調べてみます。