Wednesday, May 26, 2010

2次元三角形のトラバース



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: