タグ

algorithmに関するpapamitraのブックマーク (1)

  • 高速塗りつぶし法

    『お絵描き掲示板』 に、「塗りつぶし」コマンド(=お絵描きソフトで、ペンキ缶のアイコンのやつ) をつけようかなと思い、そのやり方を考えてみました。 そしたら、とてもいいロジックが出来たので紹介することにしました。 このロジックは、僕が今まで調べたもののうち、どんなものよりも高速で、 かつ単純なものになっています。 (もしかしたらさらに速いやり方があるかもしれません)。 ではさっそくそのロジック(アルゴリズム)を説明します。 一般的な塗りつぶしのアルゴリズムは以下のようなもの。 これは、走査線一ごとに境界を探して行く方法なので、 「スキャンラインアルゴリズム」とか「走査線アルゴリズム」とか呼ばれている。 <処理ステップ> 前提として、図2のような、閉曲線(境界線)で囲まれた領域があるとする まず塗りつぶしを始める一点 ( X, Y ) を決める その座標 X, Y をスタックに積む

  • 1