ペイント・ルーチン (1)シード・フィル アルゴリズム
ここでは、シード・フィル(seed fill)による閉領域の塗り潰し、いわゆるペイント・ルーチンについて取り上げたいと思います。 シード・フィル アルゴリズムは、以下のような流れになります。 塗り潰しの開始点(シード)として指定した 1ピクセルを塗る 今塗ったシード・ピクセルの周囲から塗り潰すべきピクセルを探す そのピクセルを新たなシードとして 1,2と同様の処理を繰り返す 新たなシードとなるピクセルがなくなった時点で塗り潰しは完了している 2のステップで見つかるシードの候補は一点だけとは限らないので、見つけたシードの候補は全てどこかに記憶しておく必要があります。そのあたりを考慮してアルゴリズムを練り直すと次のようになります。 シードとして指定した 1ピクセルを塗る 今塗ったシードピクセルの周囲から塗り潰すべきピクセルを探し、シードの候補としてその座標をバッファに記憶する バッファから 1
興味深いデータ構造：BK木 | POSTD
BK木とは、 距離空間 内のデータをインデックス化する目的に特化した、木構造を指します。距離空間は基本的に、要素の組 $ (a,b) $ 全てについて距離関数 $ d(a,b) $ を持つオブジェクトの集合です。この距離関数は正しく動作することを保証するために、一連の公理を満たしていなければなりません。これが必要になる理由は、後述の「検索」のセクションできちんと説明します。 BK木のデータ構造は、一連のキーを検索し、与えられた検索キーの値に最も近いキーを見つける問題の解決策として、 1973年にBurkhardとKellerが提案したもの です。この問題を解決する素朴な方法は、要素の組に含まれる各要素と検索キーの値を単純に比較することです。一定の時間内に比較が完了した場合、この検索の解は $ O(n) $ となります。一方、BK木を採用すると、この時実行する比較の回数を減らせる可能性が高く
二次ベジェ曲線と線分の当たり判定
二次ベジェ曲線の式。x0,y0は始点、x2,y2は終点、x1,y1は制御点。 線分の式。px,pyが始点、qx,qyが終点。 上記の式からtを消すと ベジェ曲線の式を代入するとtの二次方程式になるので、解の公式で解くとtが求められる。 式が少々複雑だったので置き換え。 tが0から1のときに直線との交点を持つ。tを二次ベジェ曲線の式に戻して座標を得る。 線分と当たっているか求めたいので、直線との交点の座標が線分の範囲にあるか調べればOK。 二次ベジェ曲線の法線 当たった位置の法線は、二次ベジェ曲線の式をtで微分して接線を求め変形する。 法線が分かったら当たった時の反射する方向が求められる。 二次ベジェ曲線のバウンディングボックス 毎回、当たり判定するとコストが高いので、二次ベジェ曲線のバウンディングボックスを求めてまずはAABBと当たり判定をとる。 二次ベジェ曲線の座標の最大、最小を求めるに
【第2回】点の多角形に対する内外判定｜【技業LOG】技術者が紹介するNTTPCのテクノロジー｜【公式】NTTPC
前回(と言っても一年近く経過していますね・・・。遅くなりました。)に引き続き、地図上に存在するエリアと現在地との関係性を計算機上で把握する手法の第2回目です。今回は、第3工程にあたる、「内外判定」について解説します。 現在地があるエリアの内側にいるか外側にいるかを考える場合、２次元平面上に存在する任意の点Pと多角形Tについて、点Pが多角形Tの内側にいるか外側にいるかを判定するにはどうしたらよいかを考えます。 この時、主に次の2つのアルゴリズムが利用されていることがわかりました。 Crossing Number Algorithm Winding Number Algorithm そこで、今回はこれらのアルゴリズムと実装方法(コード)について説明します。 まずはそれぞれのアルゴリズムの概要を簡単に説明します。 1.1.Crossing Number Algorithm（交差数判定）の概要 こ
乱数のたのしい話と遺伝アルゴリズム - きしだのHatena
金曜日の「プログラマのための数学勉強会＠福岡」で乱数の話をしてきました。 プログラマのための数学勉強会@福岡 #3 - connpass で、乱数の生成だとか、クイックソートや素数判定などの乱択アルゴリズムの話とかをしました。 乱数タノシイヨ 乱数のたのしい話 from なおき きしだ その中で、遺伝アルゴリズムで巡回セールスマン問題(TSP)を解くというのをやってみました。遺伝アルゴリズム、すいぶん昔から名前は知ってて、どういうアルゴリズムかも知ってて、実装もそんな難しくないと知りつつ、書く機会がありませんでした。なので、この機会に書いてみようと。 とりあえず最初に完全にランダムでTSPを解いてみます。 TSP with random ぐちゃぐちゃですね。 下部のグラフはその時点での最短距離。最初に距離が短いものをみつけていくけどだんだんみつかりにくくなる、という感じになっています。 1
♪ドレミファソート
特 徴 イントロソートなどは、「クイックソート並みに速い」と表現されますが、♪ドレミファソートは実際にクイックソートよりも速く動作します。ただし、もともとクイックソートなので、何倍も速くなったというわけではありません。 クイックソートにとって「メディアンキラー」は天敵ですが、♪ドレミファソートはメディアンキラーが大好物です。 Quick3 ソート ♪ドレミファソートの正体はクイックソートと表現しましたが、実際には Quick3 ソートと呼ばれる技法がベースです。これは、 3 way partition とか、3 way segmentation などと呼ばれる技法です。言葉は難しいのですが、ピボットよりも小さなデータ、ピボットと同一キーを持つデータ、ピボットより大きなデータの３つに分離する方法です。 開発者自身が執筆した Quick3 の紹介記事（英語） えぇっ、普通のクイックソートもそう
ハクビシンにもわかる全文検索 - Qiita
高速な全文検索アルゴリズムであるFM-indexについて解説する。理解しがたい点や間違っている点があれば是非コメントで指摘してほしい。 概要 FM-indexはリニアな文字列に対して検索をするアルゴリズムで、主に簡潔データ構造とBWT(およびLF mapping)という二つのアイデアから成り立っている。BWTはBurrows-Wheeler変換のことで、文字列を特殊な並び順に変換するという可逆関数である。BWTされた文字列を簡潔データ構造固有の操作をすることで、クエリ文字列の長さに比例した短い時間で文字列を探し出すのがFM-indexだ。 簡潔データ構造 簡潔データ構造に関してはFM-indexで必要となる二つの関数だけ説明して、詳細は次の機会に譲るとする。さて、二つの関数はともに文字列のある位置より前の部分に含まれている文字の数を数え上げるというものでrank()とrankLessTha
CodeIQについてのお知らせ
2018年4月25日をもちまして、 『CodeIQ』のプログラミング腕試しサービス、年収確約スカウトサービスは、 ITエンジニアのための年収確約スカウトサービス『moffers by CodeIQ』https://moffers.jp/ へ一本化いたしました。 これまで多くのITエンジニアの方に『CodeIQ』をご利用いただきまして、 改めて心より深く御礼申し上げます。 また、エンジニアのためのWebマガジン「CodeIQ MAGAZINE」は、 リクナビNEXTジャーナル( https://next.rikunabi.com/journal/ )に一部の記事の移行を予定しております。 今後は『moffers by CodeIQ』にて、 ITエンジニアの皆様のより良い転職をサポートするために、より一層努めてまいりますので、 引き続きご愛顧のほど何卒よろしくお願い申し上げます。 また、Cod
levenshtein gem で DroidKaigi と DanKogai の類似度を測定する #ruby #droidkaigi - Qiita
と呟いたら・・・ @tbpgr 遅くなってすみません。ご査収ください。 pic.twitter.com/ag3Vve9rCP — ハト (@rosylilly) 2015, 2月 3 作っていただけた！ @rosylilly さん、ありがとうございます！ ちなみに DanKogai さんご本人の目にも止まり、こんな結果になった模様。 アイコンこれにしたろか… <@rosylilly: DanKogai 、すごく楽しみなイベントになった pic.twitter.com/aW1f4ZyzeC — Dan Kogai (@dankogai) 2015, 2月 3 本題 levenshtein gem で DroidKaigi と DanKogai の類似度を測定します。 levenshtein は レーベンシュタイン距離 で類似度を計測します。 サンプルコード1 require 'levensh
Situs Judi Slot Online Terlengkap dan Terpercaya Indonesia
MORE INFORMATION Nama : QQDeluxe Website : http://qqdeluxe6.com Server : QQSLOT Negara : Indonesia Min Deposit : Rp 20.000 Deposit via : Bank, Pulsa, E-wallet Platform : Windows, IOS, Android Situs Slot Indonesia, Judi Slot Online Terpercaya Game Slot Online merupakan jenis permainan yang saat ini menjadi primadona di kalangan masyarakat Indonesia. Permainan slot online memiliki sistem yang sangat
ないんたんの天気予報と画像処理アルゴリズム（2014年9月13日 情報科学若手の会）
ないんたんの天気予報と 画像処理アルゴリズム (http://j.mp/ninetan2014) Kentaro Imajo (@imos) 第47回 情報科学若手の会 （2014年9月13日）
コロキウム室(Bezier曲線の問題)
Bezier曲線の問題 Bezier曲線（ベジェ曲線）は、TrueTypeフォントやAdobe Illustrator等のソフト で利用されている、コンピュータグラフィクスでお馴染みの曲線です。 平面上の3次Bezier曲線とは、以下の様に媒介変数表示できる有限長の曲線です： 任意の4点P1(x1,y1)、P2(x2,y2)、 P3(x3,y3)、P4(x4,y4)を与え、 x = t3 ・ x4 + t2 ・ (1-t) ・ x3 + t ・ (1-t)2 ・ x2 + (1-t)3 ・ x1 y = t3 ・ y4 + t2 ・ (1-t) ・ y3 + t ・ (1-t)2 ・ y2 + (1-t)3 ・ y1 0≦t≦1 そこで、問題です。 『互いに異なる任意の4点を与えた時、この4点で描いた3次Bezier曲線C までの距離が定数L>0である点が描く軌跡Fを求めて下さい』 つまり
ロスレス圧縮アルゴリズムの歴史
江添亮 自由ソフトウェア主義者 C++ Evangelist C++標準化委員会の委員 ドワンゴ社員 C++11本を執筆した。 株式会社ドワンゴで働いている。 Mail:boostcpp@gmail.com Twitter:@EzoeRyou GitHub: https://github.com/EzoeRyou 江添亮のマストドン@EzoeRyou 筆者にブログのネタを提供するために、品物をアマゾンお気に入りリスト経由で送りたい場合： Amazon.co.jp: 江添亮: 江添のほしい物リスト 筆者にブログのネタを提供するために、直接に品物を送りたい場合、住所をメールで質問してください。 View my complete profile ► 2020 (31) ► December (2) ► November (2) ► September (2) ► August (4) ► Jul
ある三角形の頂点のうち、最後の頂点を求める方法 - 株式会社CFlatの明後日スタイルのブログ
今日は小ネタです。 三角形ABCの各頂点の座標が、a, b, c であるものとします。 この三角形ABCのうち、外から渡した座標 d, e のいずれでもない、最後の頂点を求めて下さい。ただし d, e は、必ず a, b, c のうちのいずれかと一致し、また d≠e であるものとします。 答え：a + b + c - d - e 案外、思いつかないものです。 ちなみにこの方法は、a〜e が頂点座標ではなく、頂点配列のインデックスの場合にも利用できます。 似たようなテクニックに、「3つの数字のうち、真ん中の値を求める」のがあります。 template <class T> T middle(const T& a, const T& b, const T& c) { return a + b + c - std::min(a, std::min(b, c)) - std::max(a, std:
多倍精度整数の基礎 ( 四則演算編 ) - Qiita
coe は次数 i ごとの任意の係数, radix は基数. 具体的には std::vector の template 引数に coe を指定し配列の添え字を i とする. 実装 準備 まずクラスに与えられるべき必要な template parameters を確認する. template< class UInt = std::uint16_t, class DoubleUInt = std::uint32_t, class DoubleInt = std::int32_t, DoubleUInt BitNum = sizeof(UInt) * CHAR_BIT > class integer; class UInt = std::uint16_t ここには coe の型を指定する. coe で表現できる最も大きな値 + 1 が radix になる. class DoubleUInt =
RSA公開鍵から素数の積を取り出す方法 - hnwの日記
RSA暗号はHTTPSやSSHの通信で利用されている暗号化方式です。公開鍵として巨大な素数の積を交換しあって暗号に利用しており、この素因数分解が困難であることにより安全性が担保されています。このことは教科書にも載っているような内容で、ご存じの方も多いかと思います。 ところで、その素数の積を実際に見たことってありますか？少なくとも僕は見たことがありませんでしたし、大抵の人は見たことが無いのではないでしょうか。本稿ではこの公開鍵の情報を見る方法を紹介します。 OpenSSH公開鍵の中身を見る まずはOpenSSHの公開鍵の情報を取り出してみます。OpenSSHの公開鍵は次のようなものです。 ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQCw+XdXSrhBcDFAXPcisrc8im4y8ytC46HEQ0GsWOph9OPK1elTQmBD5LATGfp4JG4
平方数かどうかを高速に判定する方法 - hnwの日記
平方数とは、ある整数の平方（＝二乗）であるような整数のことを言います。つまり、0,1,4,9,16,...が平方数ということになります。 ところで、与えられた整数が平方数かどうかを判定するにはどうすれば良いでしょうか。与えられた整数の平方根の小数点以下を切り捨て、それを二乗して元の数になるかどうか、というのがすぐ思いつく実装です。 <?php function is_square($n) { $sqrt = floor(sqrt($n)); return ($sqrt*$sqrt == $n); } しかし、平方根の計算は比較的重い処理です。もっと高速化する方法は無いのでしょうか。 多倍長整数演算ライブラリGNU MPには平方数かどうかを判定するmpz_perfect_square_p関数が存在します（PHPでもgmp_perfect_square関数として利用できます）。本稿ではこの実装
JPEG画像形式の概要(圧縮アルゴリズム) - ウェブで用いられる画像形式。
JPEG画像の圧縮アルゴリズムについて解説します。 具体的なファイルフォーマットは、別ページで解説しました。 JPEG画像とは。 JPEGとは規格策定団体(ジョイント・フォトグラフィック・エクスパーツ・グループ)の名称であり、正しくはJFIF画像(JPEG・ファイル・インターチェンジ・フォーマット)と言うべきですが、現状数あるJPEG策定規格でほぼ唯一JFIF画像のみが採用されており、JPEG画像と呼んでも殆ど差障りが無いようです。 JPEG形式は、策定団体の名前どおり、写真の効率良い圧縮を行うためのフォーマットです。 JPEG形式はフルカラー及びグレイスケールに対応しております。 JPEG形式では多くの場合、圧縮の際にデータの一部を切捨てる事で圧縮効率を高めると言うアルゴリズムを採用しております。従って、JPEG形式は圧縮された画像を展開した場合、元通りにはならない不可逆圧縮となります。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ページ移転のお知らせ
重複のない10桁の数字をIDとして採番するアルゴリズムを教えて下さい。…