Найдите все грани между исходным и целевым лицами

Question

Я использовал CGAL::Surface_mesh_shortest_path раньше, чтобы найти точный кратчайший путь топологическим способом. Но теперь мне нужно что-то попроще, чего, кажется, не хватает в библиотеке, которая находит логический путь от одного лица к другому, возвращая список лиц между ними.

Есть ли какие-нибудь способ сделать это без необходимости выполнять поиск по дереву с нуля?

Answer 1

CGAL предлагает класс Dual в качестве оболочки для me sh. Как следует из названия, вы получаете двойной график . Если у вашего me sh есть границы, вы должны отфильтровать их с помощью boost::filtered_graph. Теперь вы можете запустить boost::dijkstra_shortest_paths. Теперь для любой вершины карта-предшественник приведет вас к исходной вершине.

Вы можете найти самодостаточный пример здесь .

Вероятно, вы можете добавить посетителя, чтобы вы остановились, выбрасывая исключение, как только алгоритм кратчайшего пути достигнет вашей цели вершина.