連載
Blogopolisから学ぶ計算幾何
- Twitterリスト
計算幾何学は，図形に関するアルゴリズムを研究するコンピュータサイエンスの一分野です。本連載では，ビジュアルブログ検索エンジン「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日
著者プロフィール
浜本階生（はまもとかいせい）
1981年生まれ。栃木県出身。東京工業大学情報工学科卒業。技術やアイデアの組み合わせから面白いソフトウェアを生み出したいと日々考えている。現在，ブログの解析および視覚化の試みとして「TopHatenar」「Blogopolis」を開発，運用中。