Есть ли способ сделать этот алгоритм кратчайшего пути быстрее?

Question

Используя CGAL lib, я пытаюсь реализовать методы 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

Это довольно ясно из документации.Вы должны сначала позвонить build_sequence_tree. Мое предложение заключается в том, что вы добавили этот показатель производительности где-то до того, как пользователь щелкнет по месту назначения - это может быть при первом выборе источника, чтобы он не ощущался, когда пользователь начинает нажимать вокруг.Еще лучше, если вы сможете найти способ безопасного выполнения этого в фоновом режиме.

2.1.3 Построение внутреннего дерева последовательностей

Операция, требующая много времени для запросов кратчайшего пути, состоит в построениивнутренняя структура данных, используемая для выполнения запросов.Эта структура данных называется деревом последовательности.Он будет построен автоматически, когда будет выполнен первый запрос по кратчайшему пути, и будет использоваться повторно для любого последующего запроса, пока набор исходных точек не изменится.Каждый раз, когда набор исходных точек изменяется, дерево последовательности необходимо перестраивать (если оно уже построено).Обратите внимание, что он также может быть построен вручную с помощью вызова Surface_mesh_shortest_path :: build_sequence_tree ().

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

Дополнительно, похоже, что алгоритм работает в наихудшем полиномиальном времени,Как отмечали другие, это может быть оптимизировано, если вы знаете, что ваша проблема является выпуклой во всех случаях.

Answer 2

В документах CGAL указано, что самый короткий маршрут - это всегда прямая линия, когда вы разворачиваете сетку на 2D-плоскости.Вход для алгоритма кратчайшего пути - вершина или плоскость с барицентрическими координатами.Вы можете отобразить эти входные координаты в 2D текстуру, которая была отображена на вашей сетке.Нарисуйте красную линию между начальной и конечной точкой на вашей текстуре.Вам придется глубже изучить, как преобразовать входные координаты вершин в абсолютные координаты XY в текстуре.Также имейте в виду, что кратчайший путь может проходить через заднюю часть сетки.В зависимости от того, как отображается текстура, может потребоваться нарисовать более 1 линии.