Ramer-Douglas-Peucker algorithm - Wikipedia, the free encyclopedia
The Ramer–Douglas–Peucker algorithm, also known as the Douglas–Peucker algorithm and iterative end-point fit algorithm, is an algorithm that decimates a curve composed of line segments to a similar curve with fewer points. It was one of the earliest successful algorithms developed for cartographic generalization. Idea[edit] The purpose of the algorithm is, given a curve composed of line segments (
Ramer–Douglas–Peucker Algorithm
RedisLiveのソースコードを読んでいると、時系列データのプロットに Ramer–Douglas–Peucker アルゴリズムというのが使われていた。 大量のデータがあるとき、それらをすべてつなげて曲線をひくのではなく、うまく間引いて元の曲線に近似させるアルゴリズム。“iterative end-point fit algorithm” や “split-and-merge algorithm” などとも呼ばれる。 Algorithm アルゴリズムそのものは以下のようにものすごくシンプル。 先頭と最後の点をプロット対象にする。 この2点で線をひく。 線から近似精度(ε)以上離れた点を探し、その中で最も遠い点をプロット対象にする。 プロット対象の各点を線でつなげる。 再帰的に ステップ3とステップ4を繰り返す。 この流れをまとめると下図のようになる。(wikipedia より) Smoo
15 Sorting Algorithms in 6 Minutes
Visualization and "audibilization" of 15 Sorting Algorithms in 6 Minutes. Sorts random shuffles of integers, with both speed and the number of items adapted to each algorithm's complexity. The algorithms are: selection sort, insertion sort, quick sort, merge sort, heap sort, radix sort (LSD), radix sort (MSD), std::sort (intro sort), std::stable_sort (adaptive merge sort), shell sort, bubble sort,
Daftar Serta Masuk Saat ini Di Situs Slots Online Terpilih Ojekslot
Daftar Serta Masuk Saat ini Di Situs Slots Online Terpilih Ojekslot Seperti yang kita pahami waktu ini ada sangat banyak permainan slot online paling sederhana yang dapat dimainkan dalam sekejap hanya cukup masuk di sana saja ojekslot terunggul. Di sini dapat ada sangat banyak bermacam permainan luar biasa yang pastinya dapat anda temukan dengan ringan. Beraneka permainan terbaik di sini dapat and
経路探索アルゴリズムA*をRubyで実装してみた - gan2 の Ruby 勉強日記
前回書いた経路探索アルゴリズムA* - gan2 の Ruby 勉強日記が たくさんブクマされててちょっとびっくりです(；ﾟДﾟ) 実装はFlash(Action Script)でやろうと思っていたのですが、 その前にRubyで書いてみることにしました。 途中、アルゴリズムの理解が不十分だったせいもあり、 多少てこづりましたがとりえず完成しました！ ソースはあんまり整理してないけども、 あまり気にせずに貼り付けておきます(ﾉ∀｀) =begin **** 経路探索アルゴリズムA*(エースター) a-star.rb **** アルゴリズムの概要 スタートノードから、あるノード n を通って、 ゴールまで辿り着くときの最短路経路を考える。 このとき、最短経路のコスト f(n) を次の式で表す。 f(n) = g(n) + h(n) ここで、g(n) はスタートノードから n までの最小コスト。
A* - Wikipedia
A*探索アルゴリズム A*（A-star、エースター）探索アルゴリズム（エースターたんさくアルゴリズム）は、グラフ探索アルゴリズムの一つ。 最良優先探索を拡張したZ*に、さらにf値として「現時点までの距離」g と「ゴールまでの推定値」h の和を採用したもの[1]。h は ヒューリスティック関数と呼ばれる。 概要[編集] A* アルゴリズムは、「グラフ上でスタートからゴールまでの道を見つける」というグラフ探索問題において、 ヒューリスティック関数 h(n) という探索の道標となる関数を用いて探索を行うアルゴリズムである。h は各頂点 n からゴールまでの距離のある妥当な推定値を返す関数で、解くグラフ探索問題の種類に応じてさまざまな h を設計することが出来る。 例えば、カーナビなどで用いられる単純な二次元の地図での探索では、h としてユークリッド距離 を使うことができ、この値は道に沿った実際
A*（A-star：エースター）探索アルゴリズムの原理 – piyajk.com
当サイトは、興味のあること、疑問に思って調べたこと、作業したことなどを、忘れないように書き留めたノートです。 いただいたコメントはすべて、有難く拝見しております。すごく喜んでおります。 その他のお問い合わせは、自己紹介ページからお願いします。 最近よくご覧いただいているページはこちらです。 経路探索アルゴリズムのひとつに、A*（A-star：エースター）探索アルゴリズムと呼ばれるものがあります。 今、迷路の中でスタート地点からゴール地点まで歩くことを考えます。早くゴールへたどり着くために、A*探索アルゴリズムを用いて、最短経路を計算してみます。 A*探索アルゴリズムにはコストという概念があります。今、単純に「コスト」＝「距離」と置き換えて考えると、迷路が一様の場合はコストの一番小さな経路が最短経路といえます。つまり、コストが小さくなるような経路を探していくと、最短経路が見つかるわけです。
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
画素の補間（Nearest neighbor,Bilinear,Bicubic） 画像処理ソリューション
ニックネーム:Akira 東京都の町田事業所に勤務 画像処理ソフトの開発を行っています。リンクフリーです！ 詳細プロフィールは こちら お問い合わせは、こちら↓ 【補助HP】 画像処理ソリューションWeb版 【Newブログ】 イメージングソリューション
貧乏人のためのＣＧ講座 画像の変形・拡大・縮小方式
最も原始的なアルゴリズムで、D-Pixedの「拡大・縮小」機能はこれを採用しています。この方法では、まず変形後のあるピクセルが変形前にどこの座標に位置していたかを計算します。そして得られた座標を四捨五入または小数点以下切り捨てし、その座標にあるピクセルの色を変形後の色として採用します。 変形後のピクセルの色は変形前の画像から単純に拾ってくるだけですから、この方法では変形前と変形後で色数が変化しないという特徴があります。２５６色専用ソフトのD-Pixedで採用されているのはこのためです。しかし、結果的に元画像のピクセルを間引いただけということになりますので、できあがってくる画像の質は上の例を見てのとおり最低です。よほど特別な場合以外、使い道はないと思います。 いわゆる「線形補間」というヤツで、直感的で非常に分かりやすいアルゴリズムです。この方法では、変形後のあるピクセルが変形前のどの領域に相
Dictionary of Algorithms and Data Structures
absolute performance guarantee abstract data type (a,b)-tree accepting state Ackermann's function active data structure acyclic directed graph: see directed acyclic graph acyclic graph adaptive heap sort adaptive Huffman coding adaptive k-d tree adaptive sort address-calculation sort adjacency-list representation adjacency-matrix representation adjacent admissible vertex ADT: see abstract data typ
Wu Anti-aliased Lines
Your average Breshenham line drawing algorithm draws lines quickly, but not that nicely. Your average integer line renderer produces nasty jaggedy lines that can only be drawn between integer coordinates. I saw a nice anti-aliased line drawer in one of Michael Abrash's books, and decided to improve it to handle non-integer coordinates. A wu-line is not only better looking than a normal line, it
当たり判定 - Wikipedia
衝突判定（しょうとつはんてい、Collision Detection）とは、「2つ以上のオブジェクトの交差を検出する」という計算機科学上の問題であり、具体的には「ある物体が別の物体に当たったか（衝突したか）どうか」を判定するプログラム処理のことを指す。ロボット工学、計算物理学、コンピュータゲーム、コンピュータシミュレーション、計算幾何学など、さまざまなコンピューティング分野で応用されている。 衝突判定のアルゴリズムは、2Dオブジェクト同士の衝突判定と3Dオブジェクト同士の衝突判定に分けることができる[1]。 概要[編集] 古典的な例だが、衝突判定を科学的に考える上で、ビリヤードの球同士がどのように当たるのかを考えてみるのもよい ビリヤードの物理シミュレーションをする場合を考えて欲しい。剛体運動と弾性衝突と言う両軸に従って跳ね回るビリヤードの球の物理学は、おそらく読者諸君もよく理解しているだ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
The Douglas-peucker algorithm: sufficiency conditions for non-self-intersections
http://objectmix.com/graphics/132987-draw-parallel-polyline-algorithm-needed.html
Murphy's Modified Bresenham Line Algorithm
Amazon.co.jp: Parallel and Distributed Computer Graphics: Fairen, Marta, Pueyo, Xavier: 本
Parallel and Distributed Computer Graphics
http://ja.doukaku.org/23/nested/
Java 暗号化拡張機能 JDK5.0