領域内高速塗りつぶし法 / High-speed Region Fill Method – WAISJP
図１のような閉じた領域の内部を高速に塗りつぶすアルゴリズムと、プログラム例を示す Why? かつて作っていた『お絵描き掲示板』に、「塗りつぶし」コマンド（＝お絵描きソフトで、ペンキ缶のアイコンのやつ） をつけようかなと思い、そのやり方を考えてみました。そしたら、とてもいいロジックが出来たので紹介することにしました。このロジックは、私が今まで調べたもののうち、どんなものよりも高速で、 かつ単純なものになっています。 （ただし、これは2000年ごろに作ったものですし、もっと速いやり方があるかもしれません！）。 ではさっそくそのロジック（アルゴリズム）を説明します。 原理 一般的な塗りつぶしのアルゴリズムは以下のようなもの。 これは、走査線一本ごとに境界を探して行く方法なので、 「スキャンラインアルゴリズム」とか「走査線アルゴリズム」とか呼ばれている。 処理ステップ 前提として、図２のような、閉
OpenDataStructures.jp
オープンソース版 Open Data Structures 日本語訳の PDF ファイルを以下で公開しています。最新のソースコードは GitHub のリポジトリ https://github.com/spinute にあり、適宜こちらの PDF ファイルに反映しています。 以下のものは C++ 版です（Java 版はこちら、疑似コード版はこちらにあります）。 目次 訳者まえがき 本書の読み方 訳者謝辞 なぜこの本を書いたのか 謝辞 第1章 イントロダクション 効率の必要性 インターフェース 数学的背景 計算モデル 正しさ、時間計算量、空間計算量 コードサンプル データ構造の一覧 ディスカッションと練習問題 第2章 配列を使ったリスト ArrayStack：配列を使った高速なスタック操作 FastArrayStack：最適化された ArrayStack ArrayQueue：配列を使ったキュ
nude.js | Nudity detection with JavaScript and HTMLCanvas
About nude.js is a JavaScript implementation of a nudity scanner based on approaches from research papers. HTMLCanvas makes it possible to analyse image data and return whether it's nude or not. The script only detects nudity, the rest of the programming logic (image swap/auto-save ;-) /whatever) belongs to the programmer. Update: First improvements and next steps of nude.js (Article) The real wor
replace sort
はじめに プログラム内でソートを必要とする場合、バブルソートや、選択ソートをとりあえず使ってきました。 そんなある日、ソートのアルゴリズムを自分で考案したくなり、安定ソートとして使用頻度の高い挿入ソートに、匹敵するようなアルゴリズムを考えてみることにしました。 条件 安定ソートであること マージソートのように、一時的な配列を使わないこと（余計な配列は使わない） 将来的には、マルチスレッド化が可能であること 仕様 安定ソートである クイックソートのように、配列を小さい値と大きい値に分けて、再帰的にソートをします。 マージソートのように、並べ替え用に、配列を一切、使いません。 適切にマルチスレッド処理を書くことができれば、より速い処理をする可能性があります。 アルゴリズムの紹介 データの中央を基準値にします。 左右のデータを、基準値と比較していきます。 9,11,8,12,7,13
Stories of Your Life and Others » Blog Archive » C++で文字列のsplit
つい最近、C++の文字列splitが必要な場面がありました。 いい加減C++のsplitを毎回書くのが面倒になってきましたので、忘れないようにメモっておきたいと思います。 C++でsplitを書く方法はいくらでも方法があると思いますが、代表的な実装例をあげてみます。 boostが使える環境であれば一番最初の選択肢としてboostのstring algorithmを利用した方が車輪の再発明をしなくて済むかと思います。 ただ、競技プログラミングなどでは残念ながら利用できません。 find_first_ofを利用する方法 vector<string> split(const string &str, char delim){ vector<string> res; size_t current = 0, found; while((found = str.find_first_of
初級C言語Q&A(15)
初出: C MAGAZINE 1996年8月号 Updated: 1996-09-21 [←1つ前] [→1つ後] [↑質問一覧] [↑記事一覧] [ホームページ] 今回は、よく知られているけどちょっと分かりにくいアルゴリズム、あるいは、 今までの連載で出てきたトリッキーなコードについて、どのような原理で動作す るのかを紹介してみようと思います。ただし、一般論として、凝ったコードより も分かりやすいコードの方が価値がある場合が多いということも頭に入れておい てください。 凝ったアルゴリズム Ｑ 【曜日の求め方】 Comp.lang.c FAQ listを見ると、曜日を求める関数として次のものが紹介され ていた。 dayofweek(y, m, d) /* 0 = Sunday */ int y, m, d; /* 1 <= m <= 12, y > 1752 or so */ { stat
Post by @shyouhei
とりあえずHashが何であるかとか、どういう作りになっているかとか、そういうことは既知とする。リストの配列ってことね。←これで何言ってるか分からないおまえらにはこの文章はちょっとはやい。先にデータ構造の教科書を読むことをおすすめ。以下ではHashに登録されるキーとデータのペアのことをentryと呼び、リストの配列と言ったときのリストのほうをbin、配列のほうをbucketと呼ぶ。つまり、
おとうさん、ぼくにもYコンビネータがわかりましたよ！ - 2009-04-09 - きしだのはてな
やっと、Yコンビネータが何を意味するものなのか、どういう意義があるのかがわかりました。 名前を使わず再帰ができますよ！というだけのものじゃなかったのですね。 まずλありき 関数の話をしたいのです。 そのとき、いちいち hoge(x) = x * 2 としてhogeを・・・、とか名前をつけて話を進めるのがめんどうなので、関数を値としてあらわすと便利ということで、λという値を定義するのです。 そうすると、上のhoge関数なんかはλ(x)(x*2)などとあらわせますが、引数をあらわすのに()を使うといろいろまぎらわしいので、 λx.x*2 のように表記します。 というのがλ。 このとき、λになにかわたされたら、引数としてあらわされる部分を単純におきかえます。 (λx.x*2)y とあったら、xの部分をyでおきかえて (λx.x*2)y → y * 2 となります。λの引数部分を与えられた引数で置
セルオートマトンを用いたシューティングゲーム - Tosikの雑記
セルオートマトン(以下 CA)を用いた自作シューティングゲーム(パニックシュータ)を公開します。 プレイ動画 YouTubeに動画をアップロードしました。横長になっちゃいました。 動作環境 Windows2000,WindowsXP。CPU使用率が高いので注意。 ダウンロード・実行 Panic Shooter(パニックシュータ) ダウンロードしたZIPファイルを解凍し、pshooter.exeを実行してください。 遊び方 やってみればわかる、を目指したので説明なしで遊べると思いますが、下は簡単なルールと操作法です。 緑色の自機をカーソルキーとスペースキーで操作します。青色の箱に入ったらステージクリアです。黄色いドットにぶつかるとライフが減ります。ライフが0になったら残念。全部で10ステージクリアできるかな？ あれこれ 高校のころライフゲームなどのCAにはまってから、いつかゲームにしたいと考
sparsetable - steps to phantasien t(2007-09-07)
Matz日記 で紹介されている google-sparsehash を眺めてみた. ひさびさに Google 気分. :~/src/sparsehash-0.8 omo$ wc `find src/google/ -type f` 253 1348 10336 src/google//dense_hash_map 237 1309 9884 src/google//dense_hash_set 238 1244 9616 src/google//sparse_hash_map 223 1214 9245 src/google//sparse_hash_set 919 4776 37957 src/google//sparsehash/densehashtable.h 42 189 1187 src/google//sparsehash/sparseconfig.h 884 4642 371
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Glibc malloc internal
PathFinding.js