将非方向图转换为网格

Question

声明:

我正在创建一个程序,让用户可以布置自己的非方向图(节点和边).一旦按下特定按钮,我想在图形中的每个"间隙"中创建一个三角形网格.这里有两张图片可以让你知道我在追求的是什么:

有几点需要注意:

• 由于用户可以完全控制,我可以获得3,4,5 ... n个侧面空间
• 用户可以创建凸形或凹形
• 该应用程序正在使用C#在Unity中完成

到目前为止,我自己的尝试效率非常低,并且在非常不寻常的图形布局中可能会失败.我的总体计划是抓住一个节点并沿着一个周期的最锐角,直到我回到第一个节点.这部分工作,但我无法知道我是否已经获得了所有空间.另外,我最终会得到两个覆盖相同空间的相同网格(虽然节点顺序不同).

我很感激你能给我这个帮助的任何帮助.为了帮助解决问题,我已经熟悉凸包算法和三角剖分.

更新:

我不能发布任何代码,因为我在这个项目的NDA下,但数据结构非常简单.

节点具有位置(向量3,但y始终为0)和连接边的列表.

边缘具有第一节点,第二节点和位置(中点).

我想为每个间隙生成一个Mesh对象.此网格对象具有静态顶点数组(向量3s)和静态三角形数组(它们是整数并与顶点索引相关).

Answer 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.

同样的方法适用于具有一阶顶点的图，但面将具有“切口”（一个方向的边而不是相反方向的边。）

如果您不想要外表面，则不要“双”外边缘，而是仅从每个外边缘制作一个正方向边缘。

更新

由于每个多边形和多边形边仅通过一次，我认为这是相当最佳的解决方案。只是可能性很小。

算法的主要步骤是从上次访问的节点中选择下一条边。简单的实现是计算出边缘的角度并取下一个。可以一次计算角度，而不是每次边访问节点时都进行角度计算，甚至可以对节点进行入边->出边的映射。

不需要创建新的有向图，存储每条边的方向数据就足够了。两个布尔变量就足够了，每个方向一个。通过第一步，选择未访问过的边来开始新的多边形，变得更加复杂。如果通过从地图中删除访问过的角度来使用上角度计算，并且如果地图中不再有角度则将节点标记为可见，则可以覆盖这一点。