将无向图转换为网格
Converting a Non-Directional Graph to a Mesh
声明：
我正在创建一个程序，让用户可以布置他们自己的非方向图（节点和边）。一旦他们按下特定按钮，我想从图中的每个 'gap' 创建一个三角网格。这里有两张图片，应该可以让您了解我所追求的目标：
有几点注意事项：
- 由于用户拥有完全控制权，我可以获得 3、4、5...n 面 spaces
- 用户可以创建凸形或凹形
- 正在使用 C# 在 Unity 中制作应用程序
到目前为止，我自己的尝试效率非常低，并且在非常不寻常的图形布局中可能会失败。我的总体计划是抓住一个节点并沿着一个周期的最锐角，直到我回到第一个节点。这部分有效，但我无法知道我是否得到了所有 space。此外，我最终可以得到两个相同的网格，它们覆盖相同的 space（尽管节点顺序不同）。
如果你能给我解决这个问题，我将不胜感激。为了帮助解决问题，我已经熟悉凸包算法和三角剖分。
更新：
我不能post任何代码，因为我在这个项目的保密协议下，但数据结构非常简单。
节点有一个位置（向量 3，但 y 始终为 0）和一个连接边列表。
边有第一个节点、第二个节点和一个位置（中点）。
我想为每个间隙生成一个 Mesh 对象。这个网格对象有一个静态的顶点数组（向量 3s）和一个静态的三角形数组（它们是整数并且与顶点索引相关）。
你的方法很好。有几点需要细化。
假设图形是平面的（如果不是，则很难定义面）并且没有度数为 1 的顶点。度数为 1 的顶点不是问题，但没有它们更容易描述解决方案:-)
请注意，每条边将在两个面上。因此，如果您以最锐角跟随面部，那么您仅在一侧跟随这些边缘。解决方案是创建具有相同节点的有向图，并为每条边在两个方向上创建两条边。通常与初始图相同的图但有边
加倍。算法是：
take one (directed) edge
follow it in same way by smallest angle
make faces of that cycle
remove face (directed) edges from graph
repeat procedure until there are edges.
相同的方法适用于顶点为 1 的图，但面将具有 'cut'（一个方向的边比相反方向的边。）
如果你不想要外面而不是 'double' 外边缘，但只从每个外边缘制作一个正方向边缘。
更新
由于每个多边形和多边形边仅通过一次，我认为这是非常理想的解决方案。只有几种可能性。
算法的主要步骤是从上次访问的节点中选择下一条边。简单的实现是计算出边的角度并取下一个。角度计算可以做一次，不是每次边访问节点时，甚至可以为一个节点做in-edge -> out-edge的映射。
不需要创建新的有向图，为每条边存储方向数据就足够了。两个布尔变量就足够了，每个方向一个。通过这第一步，选择未访问的边来开始新的多边形，变得更加复杂。如果通过从地图中删除已访问的角度并在地图中没有更多角度时将节点标记为可见来使用上角计算，则可以覆盖这一点。
声明：
我正在创建一个程序，让用户可以布置他们自己的非方向图（节点和边）。一旦他们按下特定按钮，我想从图中的每个 'gap' 创建一个三角网格。这里有两张图片，应该可以让您了解我所追求的目标：
有几点注意事项：
- 由于用户拥有完全控制权，我可以获得 3、4、5...n 面 spaces
- 用户可以创建凸形或凹形
- 正在使用 C# 在 Unity 中制作应用程序
到目前为止，我自己的尝试效率非常低，并且在非常不寻常的图形布局中可能会失败。我的总体计划是抓住一个节点并沿着一个周期的最锐角，直到我回到第一个节点。这部分有效，但我无法知道我是否得到了所有 space。此外，我最终可以得到两个相同的网格，它们覆盖相同的 space（尽管节点顺序不同）。
如果你能给我解决这个问题，我将不胜感激。为了帮助解决问题，我已经熟悉凸包算法和三角剖分。
更新：
我不能post任何代码，因为我在这个项目的保密协议下，但数据结构非常简单。
节点有一个位置（向量 3，但 y 始终为 0）和一个连接边列表。
边有第一个节点、第二个节点和一个位置（中点）。
我想为每个间隙生成一个 Mesh 对象。这个网格对象有一个静态的顶点数组（向量 3s）和一个静态的三角形数组（它们是整数并且与顶点索引相关）。
你的方法很好。有几点需要细化。
假设图形是平面的（如果不是，则很难定义面）并且没有度数为 1 的顶点。度数为 1 的顶点不是问题，但没有它们更容易描述解决方案:-)
请注意，每条边将在两个面上。因此，如果您以最锐角跟随面部，那么您仅在一侧跟随这些边缘。解决方案是创建具有相同节点的有向图，并为每条边在两个方向上创建两条边。通常与初始图相同的图但有边 加倍。算法是：
take one (directed) edge
follow it in same way by smallest angle
make faces of that cycle
remove face (directed) edges from graph
repeat procedure until there are edges.
相同的方法适用于顶点为 1 的图，但面将具有 'cut'（一个方向的边比相反方向的边。）
如果你不想要外面而不是 'double' 外边缘，但只从每个外边缘制作一个正方向边缘。
更新
由于每个多边形和多边形边仅通过一次，我认为这是非常理想的解决方案。只有几种可能性。
算法的主要步骤是从上次访问的节点中选择下一条边。简单的实现是计算出边的角度并取下一个。角度计算可以做一次，不是每次边访问节点时，甚至可以为一个节点做in-edge -> out-edge的映射。
不需要创建新的有向图，为每条边存储方向数据就足够了。两个布尔变量就足够了，每个方向一个。通过这第一步，选择未访问的边来开始新的多边形，变得更加复杂。如果通过从地图中删除已访问的角度并在地图中没有更多角度时将节点标记为可见来使用上角计算，则可以覆盖这一点。