Chapter 1 Introduction
この記事は、 CGAL のマニュアルに従って、簡単な紹介を試みるのが目的。
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
自信がサイズを知っているので、戻り値は使ってない。