我设法使用 CGAL 手册中的示例将 CGAL:Polyhedron_3 的所有边插入到 CGAL:AABB_tree 中。但是，当尝试插入 Halfedges 的子集时，代码无法编译（在 MacOS 上使用 clang 13.0.1）。我尝试了几个CGAL版本。 5.6是最新的。
// Adapted from CGAL Manual
#include <iostream>
#include <vector>
//#include <CGAL/Simple_cartesian.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/AABB_tree.h>
#include <CGAL/AABB_traits.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/AABB_halfedge_graph_segment_primitive.h>
//typedef CGAL::Simple_cartesian<double> K;
typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef K::FT FT;
typedef K::Point_3 Point;
typedef K::Triangle_3 Triangle;
typedef CGAL::Polyhedron_3<K> Polyhedron;
typedef CGAL::AABB_halfedge_graph_segment_primitive<Polyhedron> Primitive;
typedef CGAL::AABB_traits<K, Primitive> Traits;
typedef CGAL::AABB_tree<Traits> Tree;
template <class Kernel, class HalfedgeGraph>
void run(const HalfedgeGraph& graph){
typename Kernel::Point_3 p(1.0, 0.0, 0.0);
typename Kernel::Point_3 q(0.0, 1.0, 0.0);
typename Kernel::Point_3 r(0.0, 0.0, 1.0);
// constructs the AABB tree
Tree tree;
#define INSERT_MODE 2
#if INSERT_MODE==0
// This compiles, but I don't want to insert all edges in the aabb tree
std::cout << "\nInserting all edges using CGAL::edges" << std::endl;
tree.insert( CGAL::edges(graph).first,
CGAL::edges(graph).second, graph);
#elif INSERT_MODE==2
std::cout << "\nInserting subset of edges using vector iterators" << std::endl;
// How to insert a subset of Halfedges of a CGAL:Polyhedron_3 into a CGAL:AABB_tree?
#if 1
// This does not compile:
std::vector<const Polyhedron::Halfedge_handle> half_edges;
Polyhedron::Halfedge_const_iterator edge_pos = graph.halfedges_begin();
#else
// This compiles with with CGAL 4.13.2, 4.14.3, and 5.6
// but I would like to store Polyhedron::Halfedge_handle instead of iterators
std::vector<Polyhedron::Halfedge_const_iterator> half_edges;
Polyhedron::Halfedge_const_iterator edge_pos = graph.halfedges_begin();
#endif
half_edges.push_back( &(*edge_pos) );
++edge_pos;
half_edges.push_back( &(*edge_pos) );
// This does NOT compile with with CGAL 4.13.2, 4.14.3 or 5.6
// tree.insert( half_edges.begin(), half_edges.end(),
// graph);
#endif
tree.accelerate_distance_queries();
// counts #intersections with a triangle query
Triangle triangle_query(p,q,r);
std::cout << tree.number_of_intersected_primitives(triangle_query)
<< " intersections(s) with triangle" << std::endl;
assert( tree.number_of_intersected_primitives(triangle_query )== 6);
// computes the closest point from a query point
typename Kernel::Point_3 point_query(2.0, 2.0, 2.0);
typename Kernel::Point_3 closest = tree.closest_point(point_query);
std::cerr << "closest point is: " << closest << std::endl;
}
int main()
{
Point p(1.0, 0.0, 0.0);
Point q(0.0, 1.0, 0.0);
Point r(0.0, 0.0, 1.0);
Point s(0.0, 0.0, 0.0);
Polyhedron polyhedron;
polyhedron.make_tetrahedron(p, q, r, s);
run<K>(polyhedron);
return EXIT_SUCCESS;
}
我尝试了此示例代码的几种变体。有些是通过预处理器变量显示的。
这是来自 clang 的错误消息。我检查了很多次但无法弄清楚问题出在哪里。
[ 0%] 构建 CXX 对象项目/helperprograms/test_AABB_tree/CMakeFiles/test_AABB_tree.dir/test_AABB_tree.C.o 在 /Users/armando/SetSolver_git/SetSolver/projects/helperprograms/test_AABB_tree/test_AABB_tree.C:9 包含的文件中： /Users/armando/SetSolver_hg/CGAL-5.6/include/CGAL/AABB_halfedge_graph_segment_primitive.h:178:17：错误：没有匹配的成员函数用于调用“make_id” : Base( Id_(make_id(*it, graph, OneHalfedgeGraphPerTree())), ^~~~~~~
/Users/armando/SetSolver_hg/CGAL-5.6/include/CGAL/AABB_tree.h:741:30：注意：在函数模板专门化 'CGAL::AABB_halfedge_graph_segment_primitiveCGAL::Polyhedron_3
/Users/armando/SetSolver_git/SetSolver/projects/helperprograms/test_AABB_tree/test_AABB_tree.C:62:8：注意：在函数模板专门化'CGAL::AABB_tree
/Users/armando/SetSolver_git/SetSolver/projects/helperprograms/test_AABB_tree/test_AABB_tree.C:87:3：注意：在此处请求的函数模板专门化“run
/Users/armando/SetSolver_hg/CGAL-5.6/include/CGAL/AABB_halfedge_graph_segment_primitive.h:102:6：注意：候选函数不可行：没有来自 'CGAL::internal::In_place_list_const_iterator
/Users/armando/SetSolver_hg/CGAL-5.6/include/CGAL/AABB_halfedge_graph_segment_primitive.h:107:39：注意：候选函数不可行：没有来自 'CGAL::internal::In_place_list_const_iterator
我可以使用向量来完成我想要的 boost::graph_traits< HalfedgeGraph >::edge_descriptor 代码如下，有兴趣的可以看看。
#include <iostream>
#include <vector>
#include <boost/graph/graph_traits.hpp>
//#include <CGAL/Simple_cartesian.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/AABB_tree.h>
#include <CGAL/AABB_traits.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/AABB_halfedge_graph_segment_primitive.h>
//typedef CGAL::Simple_cartesian<double> K;
typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef K::FT FT;
typedef K::Point_3 Point;
typedef K::Triangle_3 Triangle;
typedef CGAL::Polyhedron_3<K> Polyhedron;
typedef CGAL::AABB_halfedge_graph_segment_primitive<Polyhedron, /*VertexPointPMap*/ CGAL::Default,
/* OneHalfedgeGraphPerTree*/ CGAL::Tag_true > Primitive;
typedef CGAL::AABB_traits<K, Primitive> Traits;
typedef CGAL::AABB_tree<Traits> Tree;
template <class Kernel, class HalfedgeGraph>
void run(HalfedgeGraph& graph){
typename Kernel::Point_3 p(1.0, 0.0, 0.0);
typename Kernel::Point_3 q(0.0, 1.0, 0.0);
typename Kernel::Point_3 r(0.0, 0.0, 1.0);
// Construct an AABB tree with edges of a Polyhedron_3
Tree tree;
std::cout << "\nInserting subset of edges using vector iterators" << std::endl;
// This compiles with CGAL 4.13.2, 4.14, 5.6 and likely others
// vector to store in AABB tree the edges we want to use.
// Type used comes from CGAL header AABB_halfedge_graph_segment_primitive.h
std::vector< typename boost::graph_traits< HalfedgeGraph >::edge_descriptor > my_edges;
// Use this to pick edges from HalfedgeGraph graph
typename boost::graph_traits< HalfedgeGraph >::edge_iterator epos_start =
CGAL::edges(graph).first;
typename boost::graph_traits< HalfedgeGraph >::edge_descriptor edge =
*epos_start;
my_edges.push_back( edge );
epos_start++;
edge = *epos_start;
my_edges.push_back( edge );
// Type of first two arguments to this method are iterators
// boost::graph_traits< EdgeListGraph >::edge_iterator
// Their value is boost::graph_traits< HalfedgeGraph >::edge_descriptor
// Rebuild aabb tree with boost::graph_traits< HalfedgeGraph >::edge_descriptor stored in vector
tree.rebuild( my_edges.begin(), my_edges.end(),
graph);
// counts #intersections with a triangle query
Triangle triangle_query(p,q,r);
std::cout << tree.number_of_intersected_primitives(triangle_query)
<< " intersections(s) with triangle" << std::endl;
// assert( tree.number_of_intersected_primitives(triangle_query )== 6);
// computes the closest point from a query point
typename Kernel::Point_3 point_query(2.0, 2.0, 2.0);
typename Kernel::Point_3 closest = tree.closest_point(point_query);
std::cerr << "closest point is: " << closest << std::endl;
}
int main()
{
Point p(1.0, 0.0, 0.0);
Point q(0.0, 1.0, 0.0);
Point r(0.0, 0.0, 1.0);
Point s(0.0, 0.0, 0.0);
Polyhedron polyhedron;
polyhedron.make_tetrahedron(p, q, r, s);
run<K>(polyhedron);
return EXIT_SUCCESS;
}