NEF多角形
NEFなんて聞いたこともありませんが，このあたりによると
← これがNEF らしいぞ．2013年に死んだ
半空間 (z>0 とか 2x-y+3z+5 > 0 とか）の論理和によって表される多面体のことだそうだ．なるほど面白い考え方だな．役に立つ図形って，だいたいほとんどがそれだしなあ．で, CGALはNEF-Polyhedraをサポートしているのである．
多面体を記述するのに，頂点と辺と・・・で記述するのではなく，平面の不等式と論理演算子のリストで記述するのね・・・・変わってるわ．でも演算が得意という特徴が予想できるな．
例えば下の図形は
h1: y > 0 h2: x > y h3: x < -y + 3 h4: x > y + 1 h5: x < y + 2
とすると, ( h1 ⋂ h2 ⋂ h3 ) - ( h4 ⋂ h5) で表現できる. 論理演算だから凸集合というわけではない
NEF図形を表現するのに2つの流儀
- CSGチーム
- B-repチーム
があり一長一短であるそうだ．なんだかしらんがCGALはB-repチームに属している．
さいしょの一歩
とりあえず作ってみる．制限がないのは整数型のNef_polyhedraである：
using Kernel=CGAL::Extended_homogeneous<CGAL::Exact_integer>;
using Nef_polyhedron=CGAL::Nef_polyhedron_3<Kernel>;
using Plane_3=Nef_polyhedron::Plane_3;
Nef_polyhedron N1(Nef_polyhedron::EMPTY); //空集合
Nef_polyhedron N2(Nef_polyhedron::COMPLETE); //全集合
std::cout << "N1はN2の補集合ですか? " << (N1 == N2.complement())
<< "では, N1はN1の補集合ですか? " << (N1 == N1.complement()) << std::endl;
//整数カーネルでは, 集合の包含関係も計算できる
Nef_polyhedron N3(Plane_3( 1.0, 2.0, 5.0,-1.0)); //整数の場合に限る
Nef_polyhedron N4(Plane_3( 1.0, 2.0, 5.0,-1.0), Nef_polyhedron::INCLUDED);
Nef_polyhedron N5(Plane_3( 1.0, 2.0, 5.0,-1.0), Nef_polyhedron::EXCLUDED);
std::cout << "N3はN4ですか? " << (N3 == N4) << " では, N3はN5ですか? " << (N3==N5) << std::endl;
std::cout << "N5はN4の部分集合ですね: " << (N5<N4) << std::endl;
こんな感じで作成できる.
通常の多面体との変換
以下のように, 通常の多面体と変換が可能である:
Kernel::Point_3 p( 1.0, 0.0, 0.0);
Kernel::Point_3 q( 0.0, 0.0, 1.0);
Kernel::Point_3 r( 0.0, 0.0, 0.0);
Kernel::Point_3 s( 0.0, 1.0, 0.0);
CGAL::Polyhedron_3<Kernel> P;
auto halfedge=P.make_tetrahedron( p, q, r, s);
print_vertex(P);
print_facet(P);
if (P.is_closed()) {
//Polyhedron -> Nef_polyhedron
Nef_polyhedron N(P);
if(N.is_simple()) {
//Nef_polyhedron -> Polyhedron
N.convert_to_polyhedron(P);
print_vertex(P);
print_facet(P);
}
}
実行してみると,
Vertex 1 = 1 0 0
Vertex 2 = 0 0 1
Vertex 3 = 0 0 0
Vertex 4 = 0 1 0
Facet 1 is triangle area normal to -0 -1 -0
Facet 2 is triangle area normal to -0 -0 -1
Facet 3 is triangle area normal to 1 1 1
Facet 4 is triangle area normal to -1 -0 -0
Vertex 1 = 1 0 0
Vertex 2 = 0 0 1
Vertex 3 = 0 0 0
Vertex 4 = 0 1 0
Facet 1 is triangle area normal to -0 -1 -0
Facet 2 is triangle area normal to 1 1 1
Facet 3 is triangle area normal to -0 -0 -1
Facet 4 is triangle area normal to -1 -0 -0
面や頂点の順番は変わってしまったりすることに注意せよ.