c++ - 有没有办法让这个最短路径算法更快？

Question

使用 CGAL 库，我正在尝试实现 Shortest Path方法。

我已经有点成功了，但是映射路径所花费的时间几乎不能接受，在 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 条线。