第11回 ボロノイ図の作成（前編） | gihyo.jp
はじめに 本連載では、ごく単純な直線の式からスタートし、線分、多角形とステップアップしながら計算幾何を学習してきました。その最後の締めくくりとして、今回からは、ボロノイ図の作成方法を見ていくことにします。 ボロノイ図とは まず、第1回でも簡単に触れたボロノイ図について、改めて説明します。 平面上に複数の母点が配置されているとき、それぞれの母点に最も近くなる点を集めると、母点ごとに「勢力図」のような領域が形成されます。この領域分割図をボロノイ図（voronoi diagram）といいます（図1）。 図1 ボロノイ図 ボロノイ図の各領域をボロノイ領域（voronoi region）と呼び、ボロノイ領域の境界線をボロノイ辺（voronoi edge）と呼びます。 ボロノイ辺の性質 ボロノイ図において、ボロノイ辺が持つ性質を考えてみましょう（図2）。 図2 2つの母点とボロノイ辺 母点aと
第10回 凸多角形の交差計算（後編） | gihyo.jp
はじめに 前回に引き続き、平面走査法のアプローチを用いて、2つの凸多角形の交差部分を求める方法を解説します。今回は、まずWeb上で実行可能なデモプログラムを示した上で、プログラムを実際に操作しながら、その動きを追うかたちで説明を行います。 前回の復習 最初に、前回のポイントを押さえておきましょう。 2つの凸多角形の交差部分は、同じく凸多角形になる 2つの凸多角形の交差計算には、第3回～第5回で解説した平面走査法を応用できる 走査線と交わる線分は、left_edge_c1, right_edge_c1, left_edge_c2, right_edge_c2のたかだか4個である（図1） イベント点となるのは、入力の凸多角形の頂点のみである left_edge_c1, right_edge_c1, left_edge_c2, right_edge_c2の4辺の各終点のうち、もっとも上にある点が
第9回 凸多角形の交差計算（前編） | gihyo.jp
はじめに 今回からは、2つの凸多角形を重ね合わせて、その共通部分を切り出す交差計算を見ていきます。以前に学んだ平面走査法をうまく応用することで、高速な交差計算が可能になります。また、この凸多角形の交差計算は、本連載の最後で取り上げるボロノイ図の作成にも深く関係します。 図形のブーリアン演算 Adobe Illustratorなどのドローツールでは、2つの図形を結合して新しい図形を作り出す操作が良く行われます。これはブーリアン演算（boolean operation）と呼ばれ、領域を併合するunion演算、共通部分を切り出すintersection演算、差分を求めるdifference演算といったバリエーションがあります（図1）。 図1 ブーリアン演算 一般に、図形のブーリアン演算は複雑な処理になります。多角形同士の演算を考えてみても、図2に示すように、演算結果が「穴」を含む領域になった
第8回 多角形の幾何（後編） | gihyo.jp
はじめに 前々回は凸多角形を取り上げましたが、今回はその凸多角形に対する演算として、点の包含判定方法と面積の計算方法を学習します。 Blogopolisにおける多角形の点包含判定と面積計算 Blogopolisでは、多角形の土地にマウスカーソルを合わせると、その土地がハイライト表示され、さらにクリックすることで土地の詳細情報が表示されるようになっています（図1）。内部的には、マウスカーソルが移動するたびに、その座標が画面上の各多角形の内部にあるか、外部にあるかを判定しているわけです。 図1 Blogopolisにおけるマウスヒット領域のハイライト また、Blogopolisでは、1つ1つのブログ記事を表す土地の面積が、その記事へのはてなブックマーク数に応じて決められており、多くのブックマークを集めた記事ほど大きな土地を獲得するようになっています。これは内部的には、土地の区画を生成する過
第7回 （臨時回）線分の交差判定再訪 | gihyo.jp
はじめに 今回は臨時回として、第2回で取り上げた線分の交差判定について再度考えます。第2回の実装には、ある特別な状況下で正しく動作しないという問題がありました（筆者が執筆時点で問題を見落としていました。申し訳ありません）。 この問題を解決するために、前回学んだばかりのCCW関数を活用し、線分の交差判定を別のアプローチから実装することができます。ちょうど良い機会ですので、今回はその再実装を行ってみたいと思います。 何が問題なのか 第2回では、線分の交差判定を行うLineSegment#intersects()メソッドを以下のように作成しました。 リスト LineSegment#intersects()メソッド（Java） public boolean intersects(LineSegment s) { return intersects(s.toLine()) && s.inters
第6回 多角形の幾何（前編） | gihyo.jp
はじめに 今回は、凸性を持つ多角形について考察していきます。多角形は辺として線分を持ちますので、前回までに学習した線分の知識は、そのまま多角形の幾何にも活かすことができます。 凸多角形とは 図形に凹みが存在しないとき、その図形は凸であるといいます。もっと厳密に述べると、図形の内部のどんな2点をとっても、その2点を結ぶ線分が図形に含まれるとき、図形は凸になります。図1の場合、左の図形は凸ですが、右の図形は凸ではありません。 図1 凸性 さて、凸性のある多角形を凸多角形（convex polygon）と呼びます。 Blogopolisでは、島の外郭が凸多角形になっています（図2）。そして、島の内部のあらゆる土地の区画もまた、例外なく凸多角形になっています（図3）。これは、凸多角形が計算処理上、便利な性質を多く備えているため、凸多角形を意図的に採用しているのです。 図2 Blogopol
第5回 平面走査法による線分の交差検出（後編） | gihyo.jp
平面走査法の実装 それでは、ここまで解説してきたアルゴリズムをコーディングしてみましょう。IntersectionDetectorインターフェースを実装するPlaneSweepIntersectionDetectorクラスを、以下のように作成します。 リスト1 PlaneSweepIntersectionDetectorクラス（Java） public class PlaneSweepIntersectionDetector implements IntersectionDetector { public Collection<Intersection> execute(List<LineSegment> segments) { // イベントキューを作成 TreeSet<Event> eventQueue = new TreeSet<Event>(); for (LineSegment
第4回 平面走査法による線分の交差検出（中編） | gihyo.jp
はじめに 今回は、平面走査法による線分交差検出のデータ構造を実装していきます。内容がかなり難しくなってきますが、説明とソースコードを納得できるまで読み返していただければと思います。 平面走査法と水平方向 前回は、多数の線分から交差を検出する方法として、平面走査法（plane sweep algorithm）の考え方を紹介しました。これは、x軸に平行な走査線を上から下へと動かしていき、走査線と交わる線分のみを計算対象とすることで、交差検出の計算量を減らすというものでした（図1）。 図1 平面走査法 実は、これだけでは考え方としてまだ不足なのです。図2を見てください。図2では図1と違い、すべての線分が同じくらいのy座標範囲にまとまって存在しています。こうした場合、走査線が多数の線分と交わる時間が大半を占めるため、計算量をほとんど削減できないことになってしまいます。 図2 走査線と多数の線分
第3回 平面走査法による線分の交差検出（前編） | gihyo.jp
今回から平面走査法という手法による、線分の交差検出について解説します。この手法を使うことで、多数の線分の中から交点を高速に見つけ出すことができます。 はじめに 計算幾何学では、巨大な入力データを扱う可能性を想定して、計算量の少ない効率的なアルゴリズムの追求が行われます。今回からは、線分の集合から交差を検出する問題を取り上げます。平面走査法と呼ばれるアルゴリズムを使用することで、総当たり式の実装に比べ、計算量を大きく削減できることを見ていきます。 多数の線分から交差を見つける 前回、線分を表すLineSegmentクラスを作成し、2つの線分が交差するかどうかを調べるintersects()メソッドや、交点座標を求めるgetIntersectionPoint()メソッドを実装しました。 さて今後、プログラムの扱う線分が100個、1,000個、あるいはそれ以上に増えたときのことを考えてみましょう
第1回 直線の幾何 | gihyo.jp
計算幾何学とは 小学生や中学生の頃、算数や数学の授業で、台形の面積を求めたり、直線の方程式を解いたりした記憶が誰にでもあることでしょう。計算幾何学とは、コンピュータサイエンスの立場から、こうした「図形」に関するアルゴリズムを研究する学問です。計算幾何学は、今日のコンピュータグラフィックスやCADの発展においてきわめて重要な役割を担っているほか、地理情報システム（GIS）やロボット工学といった数多くの分野に応用されています。 本連載では、ブログ可視化サイトの「Blogopolis」で採用されている計算幾何的アプローチを引き合いに出しつつ、Javaプログラムでアルゴリズムを実装しながら、計算幾何学の初歩を学びます。 Blogopolisとボロノイ図 Blogopolisは筆者の開発したWebサイトで、主に日本国内で開設された25万件以上のブログを解析し、「仮想都市景観」として視覚化したサービ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
