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

Question

使用CGAL库，我正在尝试实现最短路径方法。

我已经有了一些成功的经验，但是映射路径所需的时间远远不可接受，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));

有什么方法可以提高性能吗？

- Alexandre Severino

---

如果您需要可工作的代码，您可能希望访问https://codereview.stackexchange.com。 - Jesper Juhl

@JesperJuhl：不，这个问题在这里是可以的。从根本上讲，这是一个算法问题。这些都是我们关注的话题。并且其他我们需要的东西也都有：当前代码和问题描述（=慢）。而且这还是一个有趣的问题。你总是有一个凸对象吗？加速通用算法的常见技巧是利用更有限的输入空间，我认为凸性很重要。 - MSalters

@MSalters 请注意，我没有对这个问题进行负评。 - Jesper Juhl

@sloriot 是的。输入始终是凸形的。我没有看到任何替代解决方案来避免重建数据结构，因为源点每次都会改变。 - Alexandre Severino

你是否考虑过自己实现最短路径算法？在这种情况下，重新发明轮子可能正是医生所开的处方，因为CGAL是通用且功能丰富的，而你的情况则相对简单且你拥有特殊知识。此外，最短路径算法通常很容易实现。作为一名C开发者，我想说这可以更简洁地完成。 - user4942583

Answer 1

CGAL文档指出，当您将网格展开到2D平面上时，最短路径始终是一条直线。最短路径算法的输入是具有重心坐标的顶点或平面。您可以将这些输入坐标映射到在网格上映射的2D纹理中。在纹理上从起点到终点画一条红线。您需要深入了解如何将顶点输入坐标转换为纹理中的绝对XY坐标。同时请注意，最短路径可能会穿过网格的背面。根据纹理的映射方式，可能需要绘制多条线。

- Frederik De Ruyck

Answer 2

从文档中可以很清楚地看出，您需要先调用build_sequence_tree。我的建议是在用户点击目标之前，在某个地方放置这个性能损失 - 这可以在选择源点时进行，这样当用户开始点击时就不会感到了。如果您能找到一种安全地在后台运行此操作的方法，那就更好了。

2.1.3 构建内部序列树

对于最短路径查询来说，一个耗时的操作是构建一个内部数据结构，用于进行查询。这个数据结构称为序列树。当第一次进行最短路径查询时，它将自动构建，并且在任何后续查询中都将被重复使用，只要源点集合不改变。每次更改源点集合时，如果已经构建，则需要重新构建序列树。请注意，也可以通过调用Surface_mesh_shortest_path::build_sequence_tree()手动构建它。

https://doc.cgal.org/latest/Surface_mesh_shortest_path/index.html

此外，看起来该算法在最坏情况下运行的时间是多项式级别的。正如其他人指出的那样，如果您知道您的问题在所有情况下都是凸的，则可能会进行优化。

- darune

---

看起来不清楚是否可能，参见上面的评论：我没有看到任何替代方案来避免重建数据结构，因为源点每次都会改变。 - Frederik De Ruyck

@FrederikDeRuyck，实际上很清楚，OP写道：“通过在两个不同的位置单击”。 - darune

我的意思是，海报在一条评论中写道源点每次都会改变。我相信这意味着序列树需要每次重新构建，但这并不清楚，因为海报没有提到这一点。 - Frederik De Ruyck

@FrederikDeRuyck 但即使如此，重点是当选择源时可以承受性能损失-然后用户花费的选择目标的时间实际上被减去了。如果可能在后台运行，那么他可以考虑一种解决方案，只有当用户点击非常快时才会注意到它。 - darune