Chapter 1 Introduction - DOSEIの日記

この記事は、 CGAL のマニュアルに従って、簡単な紹介を試みるのが目的。

http://www.cgal.org/Manual/last/doc_html/cgal_manual/Introduction/Chapter_main.html

CGAL は、効率的で信頼性のある幾何アルゴリズム (efficient and reliable geometric algorithms) を提供するのが目的のライブラリ。

さて、最初の例。

#include <iostream>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/convex_hull_2.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;

int main()
{
  Point_2 const points[] = 
  { 
    Point_2( 0, 0), 
    Point_2(10, 0), 
    Point_2(10,10), 
    Point_2( 6, 5), 
    Point_2( 4, 1) 
  };
  Point_2 hull[5];

  Point_2 const * hull_end = CGAL::convex_hull_2(points, points+5, hull);
  std::cout <<  (hull_end - hull) << " points on the convex hull" << std::endl;
  return 0;
}

(私好みに改変してあります。)

CGAL のヘッダファイルはすべて CGAL/ 以下にある。で、幾何の基本的な要素である「点」は、 2D の場合 Point_2 型である。この型は、 CGAL::Exact_predicates_inexact_constructions_kernel で定義されているらしい。長い…。長いので、この例では K という短い名前にしている。「点」などを定義しているこれはカーネル (kernel) と呼ばれている。クラスなのか何なのかよくわからないので、 Exact_predicates_inexact_constructions_kernel.h を見てみると、 Filtered_kernel< Simple_cartesian<double> > の typedef なので、クラスらしい。
カーネルは、自分が使いたいアルゴリズムに合わせて選択する。今回の凸包を求めるアルゴリズムでは、座標の比較と方向のテストのみが行われるので、「正確な述語関数」(exact predicates) と「正確ではない幾何構造」 (inexact geometric construction) を選んだらしい。どっちもはっきり意味がわからないけど、そのうちわかるだろう。
で、凸包を求める CGAL::convex_hull_2() (in CGAL/convex_hull_2.h) は、よくある STL のアルゴリズムのごとく、イテレータで計算範囲を指定し、書き込み先のイテレータを与える。この例では、配列のポインタをイテレータとして渡し、凸包の結果を十分入れられる大きさの配列を用意して、そこに書き込んでもらってる。サイズがどれほどだったかは、戻り値の終端の一つ隣 (past-the-end) を表すイテレータによってあらわされている。

STL の vector を使った書き方も乗っていて、

  CGAL::convex_hull_2(points.begin(), points.end(), std::back_inserter(hull));

となる。内部的には書き込み (by operator=()) と、前進 (by operator++()) で行われているようで、 back_insert_iterator を作り出すことで、自動的に vector を拡張しつつ追加が行われる。(この辺りは、 CGAL 固有の話ではない) vector 自信がサイズを知っているので、戻り値は使ってない。