如何在CGAL中提取有序边界环？

CGAL提供了配套工具来生成有序的边界环，针对你这种单边界网格的场景，不需要复杂自定义逻辑，结合现有函数加简单遍历即可实现：

方法1：基于extract_boundary_cycles构建有序环 #

extract_boundary_cycles返回的每个半边对应一个边界环的起始点，你只需从这个起始半边出发，沿着边界的后继半边遍历，直到回到起点，就能得到完整的有序环：

#include <CGAL/Polygon_mesh_processing/border.h>
#include <CGAL/Surface_mesh.h>

typedef CGAL::Surface_mesh<CGAL::Point_3<double>> Mesh;
typedef boost::graph_traits<Mesh>::halfedge_descriptor halfedge_descriptor;

int main() {
  Mesh mesh;
  // 假设已完成网格加载，且仅有一个边界

  std::vector<halfedge_descriptor> boundary_starts;
  CGAL::Polygon_mesh_processing::extract_boundary_cycles(mesh, std::back_inserter(boundary_starts));

  // 单边界场景下取第一个起始半边
  halfedge_descriptor current_he = boundary_starts[0];
  const halfedge_descriptor start_he = current_he;
  std::vector<halfedge_descriptor> ordered_boundary_hes;
  std::vector<Mesh::Vertex_index> ordered_boundary_vertices;

  do {
    ordered_boundary_hes.push_back(current_he);
    ordered_boundary_vertices.push_back(source(current_he, mesh));
    current_he = next(current_he, mesh); // 沿边界后继半边遍历
  } while (current_he != start_he);

  // 此时ordered_boundary_hes和ordered_boundary_vertices即为有序的边界数据
  return 0;
}

方法2：基于border_halfedges构建有序环 #

如果用border_halfedges获取了所有边界半边，只需从中任选一个边界半边作为起点，按同样的后继遍历逻辑即可生成有序环（单边界场景下适用）：

// 承接上面的类型定义
std::vector<halfedge_descriptor> all_border_hes;
CGAL::Polygon_mesh_processing::border_halfedges(mesh.faces(), mesh, std::back_inserter(all_border_hes));

if (!all_border_hes.empty()) {
  halfedge_descriptor current_he = all_border_hes[0];
  const halfedge_descriptor start_he = current_he;
  std::vector<halfedge_descriptor> ordered_hes;

  do {
    ordered_hes.push_back(current_he);
    current_he = next(current_he, mesh);
  } while (current_he != start_he);
}

额外：统一边界环方向 #

若需要确保边界环的方向一致（比如相对于网格表面的逆时针方向），可以使用CGAL::Polygon_mesh_processing::orient_boundary_cycles函数对提取的环进行方向规整：

CGAL::Polygon_mesh_processing::orient_boundary_cycles(mesh, boundary_starts.begin(), boundary_starts.end());

虽然CGAL没有直接返回“完整有序边界环”的单一函数，但结合现有API和简单的遍历逻辑，就能高效完成这个常见任务。

内容的提问来源于stack exchange，提问作者dedowsdi