グラフィック系アルゴリズムに役立つ「計算幾何学」の入門用ノートPDF （Computational Geometry） - 主に言語とシステム開発に関して
講義ノートの目次へ CGやゲーム開発にも役立つ計算・幾何学（けいさん・きかがく）の教科書。 点・線分などの図形を数値計算する時に必要なアルゴリズムを勉強できる。 プログラミングにすごく役立つ。 複雑な図形どうしの関係を，三角形や木構造を使ってシンプルに考えられるようになり面白い。 たとえば… 平面上に，たくさんの点が存在する。点の分布にしたがって領域を分割し，境界線を描画したい。勢力図やテリトリーを生成したい。（＝ボロノイ図） 複雑な形の部屋で，監視カメラで全体を見渡す。部屋中をもれなく監視するには，どこにいくつカメラを置けばいいか？（＝美術館問題，領域の三角形分割） 地図上で，川が国境をまたぐのはどこ？（＝線分の交差問題） 点とエリアの「当たり判定」をしたい。地図上の１点を選んだとき，その点がどの国に属するのかを高速に求めたい（＝点位置決定問題） 平面上に，たくさんの点が存在する。すべて
Blogopolisから学ぶ計算幾何 記事一覧 | gihyo.jp
運営元のロゴ Copyright © 2007-2024 All Rights Reserved by Gijutsu-Hyoron Co., Ltd. ページ内容の全部あるいは一部を無断で利用することを禁止します。個別にライセンスが設定されている記事等はそのライセンスに従います。
平面充填 - 大人になってからの再学習
平面を隙間なく敷き詰められる正多角形の頂点の数は３，４，６の3種類だけ。 複数の正多角形を使ってよい場合、すべての頂点が同じ形をしている（各頂点に集まる正多角形の種類と順序が同じ）という条件では、次の８種類の敷き詰め方がある。これをアルキメデスの平面充填と呼ぶ。 左上の敷き詰め方は(3,3,3,3,6)または(,6)と表すことができて、これは頂点の周りに正3角形が4つと正6角形が1つ並ぶことを示す。このような表記を頂点形状（Vertex Figure）と呼ぶ。 (3,3,4,3,4)となっていたら、正3角形、正3角形、正4角形、正3角形、正4角形の順番に並ぶことがわかる。頂点の周りに集まる多角形の内角を足し合わせれば360°になる。 多角形Aと多角形Bの境界に位置する稜線を、多角形Aと多角形Bの中心を結ぶ線分に置き換えると、双対な関係にある平面充填を求めることができる。 上記の敷き詰めパタ
Centroidal Voronoi tessellation (重心ボロノイ分割) - 大人になってからの再学習
Centroidal Voronoi tessellation (重心ボロノイ分割) とは、分割後の領域の重心と母点が一致するボロノイ分割のこと。 そもそもボロノイ分割ってなんだっけ？ ボロノイ分割とは、ある領域（例えば2次元平面上の四角形）を、複数の領域に分割する方法の1つ。 複数の点をばらまいて、もっとも近い場所にある2点の中間に境界を定める。 その結果、次のような分割ができる。 入力（母点と呼ぶ） ボロノイ分割 よく見ると次のようなことがわかる。 「どの母点に最も近いか」という観点で領域分けした結果に等しい。 そもそも、これがボロノイ分割の定義。 母点を国の首都としたときの、各国の勢力図のようなものと考えるといい。 「ある地点は、そこから最も近くに首都がある国の領土になる」とすれば、その結果はボロノイ分割となる。 さてここで、もう一度確認。 Centroidal Voronoi te
重心ボロノイ分割 - SourceChord
コルクボード風の壁紙を生成するアプレットを作っているときに， ・平面上に均等にランダムな点を作りたい と思って何かいい方法がないか考えてみました． で，使えるかな，と思った方法が ポワソンディスクサンプリング 各サンプリング点ごとに円盤状の半径を持っていて 新たにサンプリングするときに，それまでに配置されている他のサンプリング点の半径の中に入っていた場合は棄却し，他の点をサンプリングする． というのを繰り返す． 重心ボロノイ分割をして，その重心を用いる 任意の数のサンプル点を適当に生成． その点を用いて，ボロノイ分割をし，各領域の重心を求める． サンプル点の位置をその領域の重心に移動． これを，サンプル点と重心が一致(距離が閾値以内)になるまでくりかえす． 今回はサンプル点がいくつになってもいいようにしたかったので，重心ボロノイ分割を使うことにしました． ポワソンディスクサンプリングでは，
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
