使用Boost Graph遍历平面树图模拟沿边行走，求边自动排序方法

我在XY平面上有一个带编号顶点的图形，定义了如下代码结构：

struct Point { double x; double y; };
std::vector<Point> points;
std::vector<std::pair<size_t, size_t>> edges;

例如含6个顶点、5条边的图形，选择顶点1开始的遍历序列为：1→3→6→4→6→5→6→3→2→3→1，这等效于沿围栏顺时针行走且右手靠墙。我认为这属于Boost文档中描述的平面面遍历，但Boost Graph需要预计算平面嵌入，要求预先排序每个顶点周围的边，请问Boost库是否有自动完成该排序的方法？

Boost Graph库可以辅助完成平面嵌入所需的顶点邻边排序，核心可通过两种方式实现：

• 基于坐标的邻边极角排序
  利用顶点的XY坐标，对每个顶点的邻接边按顺时针方向排序是最直接的方案。Boost Geometry库提供了cross_product等工具，可快速判断两个邻接顶点相对于当前顶点的方位关系，以此为依据排序边；你也可以手动计算邻接顶点相对于当前顶点的极角，按角度值对边进行排序。这种方式完全适配你“右手靠墙顺时针行走”的遍历需求。

• 结合Boost Graph的平面嵌入工具
  若你的图已确认是平面图，可先通过boyer_myrvold_planarity_test验证平面性，再使用compute_embedding函数生成平面嵌入。不过compute_embedding通常需要结合坐标信息来保证排序方向符合预期，所以仍需配合上述的坐标排序逻辑，确保邻边序列是顺时针方向的。

具体实现步骤参考：

1. 用boyer_myrvold_planarity_test验证图的平面性；
2. 遍历每个顶点，对其邻接边按邻接顶点的极角（顺时针）排序；
3. 将排序后的邻边序列作为平面嵌入，传入planar_face_traversal算法，即可生成目标遍历序列。

如果你的图是多边形网格或带边界的平面图，基于坐标的极角排序是最高效且易控制的方案，Boost的几何工具能大幅简化坐标计算的复杂度。

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