CGALで,2次元三角形による領域分割が必要になったので,2次元ドロネー図の三角形をトラバースできるか実験してみました.
まず,インクルードファイルとtypedefの宣言します.
#include < stdlib.h >
#include < math.h >
#include < CGAL/Exact_predicates_inexact_constructions_kernel.h >
#include < CGAL/Delaunay_triangulation_2.h >
#include < fstream >
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Delaunay_triangulation_2< K > Triangulation;
typedef Triangulation::Finite_faces_iterator Finite_faces_iterator;
typedef Triangulation::Edge_iterator Edge_iterator;
typedef Triangulation::Point Point;
以上で二次元ドロネー図を構成する準備ができました.
次にコードですが,簡単にいうと,ドロネー図に点を追加していって,できたグラフをトラバースするという手続きです.
点を追加する時点で,図を構成していますので,構成の関数を呼ぶことはないです.
Triangulation t;
for(int i=0;i < N;i++){
t.insert(Point((double)x[i][0], (double)x[i][1]));
}
int faceN = t.number_of_faces();
double *face = new double[faceN*3*2];//x 3 vertices x 2D
int i = 0;
for(Finite_faces_iterator ffi = t.finite_faces_begin (); ffi!=t.finite_faces_end(); ffi++)
{
face[i*3*2+0] = ffi->vertex(0)->point().x();
face[i*3*2+1] = ffi->vertex(0)->point().y();
face[i*3*2+2] = ffi->vertex(1)->point().x();
face[i*3*2+3] = ffi->vertex(1)->point().y();
face[i*3*2+4] = ffi->vertex(2)->point().x();
face[i*3*2+5] = ffi->vertex(2)->point().y();
i++;
}
xはランダムに配置した点です.
トラバースは三角形ごとに見ているので,faceのイタレーターで参照しています.
No comments:
Post a Comment