連載
Blogopolisから学ぶ計算幾何
計算幾何学は,図形に関するアルゴリズムを研究するコンピュータサイエンスの一分野です。本連載では,ビジュアルブログ検索エンジン「Blogopolis」で採用されている計算幾何のアプローチを例に取り上げながら,計算幾何の初歩を実践的に学習します。
- 第12回 ボロノイ図の作成(後編)
- はじめに
- 凸多角形による疑似半平面表現
- ボロノイ領域の計算
- デモプログラム
- 最後に
2010年4月12日
- 第11回 ボロノイ図の作成(前編)
- はじめに
- ボロノイ図とは
- ボロノイ辺の性質
- ボロノイ図と最近傍探索
- ボロノイ図とBlogopolis
- 半平面交差にもとづくボロノイ図の作成
- 垂直二等分線の計算
- まとめと次回予告
2010年3月29日
- 第10回 凸多角形の交差計算(後編)
- はじめに
- 前回の復習
- 交差計算のデモプログラム
- 走査線の開始位置
- イベントの処理(開始辺がleft_edge_c1の場合)
- イベントの処理(開始辺がその他の場合)
- 走査完了時の処理
- まとめと次回予告
2010年3月17日
- 第9回 凸多角形の交差計算(前編)
- はじめに
- 図形のブーリアン演算
- 解説の方針
- 平面走査法の応用
- 凸多角形の交差計算におけるステータス
- 凸多角形の交差計算におけるイベントキュー
- まとめと次回予告
2010年2月26日
- 第8回 多角形の幾何(後編)
- はじめに
- Blogopolisにおける多角形の点包含判定と面積計算
- 多角形の点包含判定
- 多角形の面積計算
- まとめと次回予告
2010年2月11日
- 第7回 (臨時回)線分の交差判定再訪
- はじめに
- 何が問題なのか
- CCW関数による交差判定
- ベクトルの内積
- 交差判定の再実装
- 動作確認
- まとめと次回予告
2010年2月5日
- 第6回 多角形の幾何(前編)
- はじめに
- 凸多角形とは
- 凸多角形クラスの作成
- 凸性の判定
- ベクトルの外積
- 外積の計算
- CCW関数
- まとめと次回予告
2010年1月25日
- 第5回 平面走査法による線分の交差検出(後編)
- はじめに
- 前回の復習
- イベントの処理
- 平面走査法の実装
- 平面走査法の計算量
- デモプログラム
- まとめと次回予告
2010年1月20日
- 第4回 平面走査法による線分の交差検出(中編)
- はじめに
- 平面走査法と水平方向
- 平面走査法のデータ構造
- イベント
- イベントキュー
- ステータス
- 順序付き集合:TreeSetクラス
- イベントクラス
- 走査線ベースの線分コンパレータ
- まとめと次回予告
2010年1月12日
- 第3回 平面走査法による線分の交差検出(前編)
- はじめに
- 多数の線分から交差を見つける
- 線分の交差を示すクラス
- 交差検出のインターフェース
- 総当たり法による交差検出
- 平面走査法
- まとめと次回予告
2010年1月4日
- 第2回 線分の幾何
- はじめに
- 線分クラス
- 線分と直線の交差判定
- 線分同士の交差判定
- 線分と直線,線分同士の交点座標
- 動作確認
- まとめと次回予告
2009年12月21日
- 第1回 直線の幾何
- 計算幾何学とは
- Blogopolisとボロノイ図
- 幾何ライブラリ
- 本連載のロードマップ
- Javaの開発環境について
- 直線クラスの作成
- 2点を通る直線のパラメータ
- 2直線の交点
- 動作確認
- まとめと次回予告
2009年12月14日