C++ 几何计算库
代码
#include <iostream>
#include <list>
#include <CGAL/Simple_cartesian.h>
#include <CGAL/AABB_tree.h>
#include <CGAL/AABB_traits.h>
#include <CGAL/AABB_segment_primitive.h>
#include <CGAL/Polygon_2.h>typedef CGAL::Simple_cartesian<double> K;// custom point type
struct My_point {double m_x;double m_y;double m_z;My_point(const double x,const double y,const double z): m_x(x), m_y(y), m_z(z) {}
};// custom triangle type with
// three pointers to points
struct My_triangle {My_point* m_pa;My_point* m_pb;My_point* m_pc;My_triangle(My_point* pa,My_point* pb,My_point* pc): m_pa(pa), m_pb(pb), m_pc(pc) {}
};// the custom triangles are stored into a vector
typedef std::vector<My_triangle>::const_iterator Iterator;// The following primitive provides the conversion facilities between
// the custom triangle and point types and the CGAL ones
struct My_triangle_primitive {
public:// this is the type of data that the queries returns. For this example// we imagine that, for some reasons, we do not want to store the iterators// of the vector, but raw pointers. This is to show that the Id type// does not have to be the same as the one of the input parameter of the// constructor.typedef const My_triangle* Id;// CGAL types returnedtypedef K::Point_3 Point; // CGAL 3D point typetypedef K::Triangle_3 Datum; // CGAL 3D triangle typeprivate:Id m_pt; // this is what the AABB tree stores internallypublic:My_triangle_primitive() {} // default constructor needed// the following constructor is the one that receives the iterators from the// iterator range given as input to the AABB_treeMy_triangle_primitive(Iterator it): m_pt(&(*it)) {}const Id& id() const { return m_pt; }// utility function to convert a custom// point type to CGAL point type.Point convert(const My_point* p) const{return Point(p->m_x, p->m_y, p->m_z);}// on the fly conversion from the internal data to the CGAL typesDatum datum() const{return Datum(convert(m_pt->m_pa),convert(m_pt->m_pb),convert(m_pt->m_pc));}// returns a reference point which must be on the primitivePoint reference_point() const{return convert(m_pt->m_pa);}
};/*
自定义KDTree测试，点相交
*/
int testKDTree()
{typedef CGAL::AABB_traits<K, My_triangle_primitive> My_AABB_traits;typedef CGAL::AABB_tree<My_AABB_traits> MyTree;typedef K::FT FT;My_point a(1.0, 0.0, 0.0);My_point b(0.0, 1.0, 0.0);My_point c(0.0, 0.0, 1.0);My_point d(0.0, 0.0, 0.0);std::vector<My_triangle> triangles;triangles.push_back(My_triangle(&a, &b, &c));triangles.push_back(My_triangle(&a, &b, &d));triangles.push_back(My_triangle(&a, &d, &c));// constructs AABB treeMyTree tree(triangles.begin(), triangles.end());// counts #intersectionsK::Ray_3 ray_query(K::Point_3(1.0, 0.0, 0.0), K::Point_3(0.0, 1.0, 0.0));std::cout << tree.number_of_intersected_primitives(ray_query)<< " intersections(s) with ray query" << std::endl;// computes closest pointK::Point_3 point_query(2.0, 2.0, 2.0);K::Point_3 closest_point = tree.closest_point(point_query);std::cerr << "closest point is: " << closest_point << std::endl;FT sqd = tree.squared_distance(point_query);std::cout << "squared distance: " << sqd << std::endl;return EXIT_SUCCESS;/* 输出
3 intersections(s) with ray query
closest point is: 0.333333 0.333333 0.333333
*/
}/*
光线追踪，面相交
*/
void testGlyph() {typedef K::FT FT;typedef K::Segment_3 Segment;typedef K::Point_3 Point;typedef std::list<Segment> SegmentRange;typedef SegmentRange::const_iterator Iterator;typedef CGAL::AABB_segment_primitive<K, Iterator> Primitive;typedef CGAL::AABB_traits<K, Primitive> Traits;typedef CGAL::AABB_tree<Traits> Tree;typedef Tree::Point_and_primitive_id Point_and_primitive_id;Point a(0.0, 0.0, 1);Point b(2.0, 1.0, 1);Point c(3.0, 4.0, 1);Point d(1.0, 6.0, 1);Point e(-1.0, 3.0, 1);std::list<Segment> seg;seg.push_back(Segment(a, b));seg.push_back(Segment(b, c));seg.push_back(Segment(c, d));seg.push_back(Segment(d, e));seg.push_back(Segment(e, a));// constructs the AABB tree and the internal search tree for// efficient distance computations.Tree tree(seg.begin(), seg.end());tree.build();tree.accelerate_distance_queries();// counts #intersections with a segment querySegment segment_query(Point(1.0, 0.0, 1), Point(0.0, 7.0, 1));std::cout << tree.number_of_intersected_primitives(segment_query)<< " intersections(s) with segment" << std::endl;// computes the closest point from a point queryPoint point_query(1.5, 3.0, 1);Point closest = tree.closest_point(point_query);std::cerr << "closest point is: " << closest << std::endl;Point_and_primitive_id id = tree.closest_point_and_primitive(point_query);std::cout << id.second->source() << " " << id.second->target() << std::endl;
}/*
测试布尔运算
*/#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_with_holes_2.h>
#include <CGAL/Polygon_set_2.h>
#include <CGAL/Boolean_set_operations_2.h>
#include <CGAL/Intersections_3/Line_3_Line_3.h>
//-----------------------------------------------------------------------------
// Pretty-print a CGAL polygon.
//
template<class Kernel, class Container>
void print_polygon(const CGAL::Polygon_2<Kernel, Container>& P)
{typename CGAL::Polygon_2<Kernel, Container>::Vertex_const_iterator vit;std::cout << "[ " << P.size() << " vertices:";for (vit = P.vertices_begin(); vit != P.vertices_end(); ++vit)std::cout << " (" << *vit << ')';std::cout << " ]" << std::endl;return;
}//-----------------------------------------------------------------------------
// Pretty-print a polygon with holes.
//
template<class Kernel, class Container>
void print_polygon_with_holes
(const CGAL::Polygon_with_holes_2<Kernel, Container>& pwh)
{if (!pwh.is_unbounded()){std::cout << "{ Outer boundary = ";print_polygon(pwh.outer_boundary());}elsestd::cout << "{ Unbounded polygon." << std::endl;typename CGAL::Polygon_with_holes_2<Kernel, Container>::Hole_const_iterator hit;unsigned int k = 1;std::cout << " " << pwh.number_of_holes() << " holes:" << std::endl;for (hit = pwh.holes_begin(); hit != pwh.holes_end(); ++hit, ++k){std::cout << " Hole #" << k << " = ";print_polygon(*hit);}std::cout << " }" << std::endl;return;
}void testBoolOpeation() {typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;typedef Kernel::Point_2 Point_2;typedef CGAL::Polygon_2<Kernel> Polygon_2;typedef CGAL::Polygon_with_holes_2<Kernel> Polygon_with_holes_2;typedef CGAL::Polygon_set_2<Kernel> Polygon_set_2;typedef std::list<Polygon_with_holes_2> Pwh_list_2;typedef CGAL::Line_3<K> Line;typedef CGAL::Point_3<K> Point;// Construct the two initial polygons and the clipping rectangle.Polygon_2 P;P.push_back(Point_2(0, 1));P.push_back(Point_2(2, 0));P.push_back(Point_2(1, 1));P.push_back(Point_2(2, 2));Polygon_2 Q;Q.push_back(Point_2(3, 1));Q.push_back(Point_2(1, 2));Q.push_back(Point_2(2, 1));Q.push_back(Point_2(1, 0));Polygon_2 rect;rect.push_back(Point_2(0, 0));rect.push_back(Point_2(3, 0));rect.push_back(Point_2(3, 2));rect.push_back(Point_2(0, 2));// Perform a sequence of operations.Polygon_set_2 S;S.insert(P);S.join(Q); // Compute the union of P and Q.S.complement(); // Compute the complement.S.intersection(rect); // Intersect with the clipping rectangle.// Print the result.std::list<Polygon_with_holes_2> res;std::list<Polygon_with_holes_2>::const_iterator it;std::cout << "The result contains " << S.number_of_polygons_with_holes()<< " components:" << std::endl;S.polygons_with_holes(std::back_inserter(res));for (it = res.begin(); it != res.end(); ++it) {std::cout << "--> ";print_polygon_with_holes(*it);}// 交集if ((CGAL::do_intersect(P, Q)))std::cout << "The two polygons intersect in their interior." << std::endl;elsestd::cout << "The two polygons do not intersect." << std::endl;// union// Compute the union of P and Q.Polygon_with_holes_2 unionR;if (CGAL::join(P, Q, unionR)) {std::cout << "The union: ";print_polygon_with_holes(unionR);}elsestd::cout << "P and Q are disjoint and their union is trivial."<< std::endl;// Compute the intersection of P and Q.CGAL::intersection(P, Q, std::back_inserter(res));// Compute the symmetric difference of P and Q.CGAL::symmetric_difference(P, Q, std::back_inserter(res));// 直线相交const Line l = Line(Point(0, 0, 0), Point(1, 2, 3));const Line l_1 = Line(Point(0, 0, 0), Point(-3, -2, -1));const CGAL::Object obj1 = CGAL::intersection(l, l_1);
}/*
凸包检测
*/
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/point_generators_3.h>
#include <CGAL/Delaunay_triangulation_3.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/algorithm.h>
#include <CGAL/convex_hull_3_to_face_graph.h>
void testConvexHull() {typedef CGAL::Exact_predicates_inexact_constructions_kernel K;typedef K::Point_3 Point_3;typedef CGAL::Delaunay_triangulation_3<K> Delaunay;typedef Delaunay::Vertex_handle Vertex_handle;typedef CGAL::Surface_mesh<Point_3> Surface_mesh;CGAL::Random_points_in_sphere_3<Point_3> gen(100.0);std::list<Point_3> points;// generate 250 points randomly in a sphere of radius 100.0// and insert them into the triangulationstd::copy_n(gen, 250, std::back_inserter(points));Delaunay T;T.insert(points.begin(), points.end());std::list<Vertex_handle> vertices;T.incident_vertices(T.infinite_vertex(), std::back_inserter(vertices));std::cout << "This convex hull of the 250 points has "<< vertices.size() << " points on it." << std::endl;// remove 25 of the input pointsstd::list<Vertex_handle>::iterator v_set_it = vertices.begin();for (int i = 0; i < 25; i++){T.remove(*v_set_it);v_set_it++;}//copy the convex hull of points into a polyhedron and use it//to get the number of points on the convex hullSurface_mesh chull;CGAL::convex_hull_3_to_face_graph(T, chull);std::cout << "After removal of 25 points, there are "<< num_vertices(chull) << " points on the convex hull." << std::endl;
}void test() {testKDTree();testGlyph();testBoolOpeation();testConvexHull();
}
输出
3 intersections(s) with ray query
closest point is: 0.333333 0.333333 0.333333
squared distance: 8.33333
2 intersections(s) with segment
closest point is: 2.55 2.65 1
2 1 1 3 4 1
The result contains 2 components:
--> { Outer boundary = [ 10 vertices: (2 2) (1 2) (0 2) (0 1) (0 0) (1 0) (2 0) (3 0) (3 1) (3 2) ]1 holes:Hole #1 = [ 12 vertices: (3 1) (1.66667 0.333333) (2 0) (1.5 0.25) (1 0) (1.33333 0.333333) (0 1) (1.33333 1.66667) (1 2) (1.5 1.75) (2 2) (1.66667 1.66667) ]}
--> { Outer boundary = [ 4 vertices: (1 1) (1.5 0.5) (2 1) (1.5 1.5) ]0 holes:}
The two polygons intersect in their interior.
The union: { Outer boundary = [ 12 vertices: (1.33333 0.333333) (1 0) (1.5 0.25) (2 0) (1.66667 0.333333) (3 1) (1.66667 1.66667) (2 2) (1.5 1.75) (1 2) (1.33333 1.66667) (0 1) ]1 holes:Hole #1 = [ 4 vertices: (1.5 1.5) (2 1) (1.5 0.5) (1 1) ]}
This convex hull of the 250 points has 88 points on it.
After removal of 25 points, there are 84 points on the convex hull.GitHub - CGAL/cgal: The public CGAL repository, see the README below
创作不易，小小的支持一下吧！
