有没有办法让这种最短路径算法更快？

Question

使用CGAL lib,我正在尝试实现最短路径方法.

我已经取得了一定的成功,但是映射路径所需的时间几乎不可接受,在Release中运行最多需要1.5秒.

我知道输入可能非常大,有50000个面孔,但这是我必须要处理的.

更详细地说明我正在尝试做的是能够通过单击两个不同的位置并沿着网格的表面绘制样条曲线,并从它们生成路径,就像在图像中一样:

我的类型定义是:

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef CGAL::Surface_mesh<Kernel::Point_3> Triangle_mesh;
typedef CGAL::Surface_mesh_shortest_path_traits<Kernel, Triangle_mesh> Traits;
// default property maps
typedef boost::property_map<Triangle_mesh,
    boost::vertex_external_index_t>::type  Vertex_index_map;
typedef boost::property_map<Triangle_mesh,
    CGAL::halfedge_external_index_t>::type Halfedge_index_map;
typedef boost::property_map<Triangle_mesh,
    CGAL::face_external_index_t>::type     Face_index_map;
typedef CGAL::Surface_mesh_shortest_path<Traits> Surface_mesh_shortest_path;
typedef boost::graph_traits<Triangle_mesh> Graph_traits;
typedef Graph_traits::vertex_iterator vertex_iterator;
typedef Graph_traits::halfedge_iterator halfedge_iterator;
typedef Graph_traits::face_iterator face_iterator;

我的代码如下所示:

Traits::Barycentric_coordinates src_face_location = { { p1.barycentric[2], p1.barycentric[0], p1.barycentric[1] } };
face_iterator src_face_it = faces(map->m_cgal_mesh).first;
std::advance(src_face_it, src_faceIndex);

map->m_shortest_paths->remove_all_source_points();
map->m_shortest_paths->add_source_point(*src_face_it, src_face_location);

Traits::Barycentric_coordinates dest_face_location = { { p2.barycentric[2], p2.barycentric[0], p2.barycentric[1] } };
face_iterator dest_face_it = faces(map->m_cgal_mesh).first;
std::advance(dest_face_it, dest_faceIndex);

std::vector<Traits::Point_3> cgal_points;
auto r = map->m_shortest_paths->shortest_path_points_to_source_points(*dest_face_it, dest_face_location, std::back_inserter(cgal_points));

points.resize(cgal_points.size(), 3);

for (int i = 0; i < cgal_points.size(); ++i) {
    auto const& p = cgal_points[i];
    points.row(i) = RowVector3d(p.x(), p.y(), p.z());
}

占用总时间99%的过程就在这条线上:

auto r = map->m_shortest_paths->shortest_path_points_to_source_points(*dest_face_it, dest_face_location, std::back_inserter(cgal_points));

有关如何提高性能的任何想法？

Answer 1

CGAL文档指出,当您在2D平面上展开网格时,最短路径始终是直线.最短路径算法的输入是具有重心坐标的顶点或平面.您可以将这些输入坐标映射到在网格上映射的2D纹理.在纹理的起点和终点之间画一条红线.您将不得不深入研究如何将顶点输入坐标转换为纹理中的绝对XY坐标.还要记住,最短路径可能会在网格背面运行.根据纹理的映射方式,您可能需要绘制多于1行.