在 C# 中生成平面图

Question

我正在寻找一种在 C# 中生成随机平面图的方法。我研究了一些算法，如 Voronoi 图、Delaunay 三角剖分和凸包算法。它们非常有用，我设法生成了一个图表，但我面临着一些尚未解决的边缘情况。请记住，我有两个主要约束：最小/最大边长度和最小/最大角度（任意两条边之间），目标顶点/边计数中存在错误是可以的。

我认为有两种方法可以生成该图： 答：有一些来源提供了所有可能的平面图，我需要一个小的平面图，所以这对我有用，但我不知道如何将其绘制在没有交叉点的平面图上。 B. 从几何角度生成它，这是我最理解的。

我发现一些论文旨在非常快速地生成大图，所以这对我来说很复杂。我可以接受经过测试的缓慢算法/库/代码。

Answer 1

您可以通过以下方式创建随机最大平面图：

1. 从一个由三个顶点和三个边组成的三角形开始，该三角形限制了单个内面。
2. 将内心的面孔放入清单中。
3. 从列表中随机选择一个内面，然后：

• 在面的中心创建一个顶点；
• 创建将新顶点连接到面周围的三个顶点的边，将原始面三等分成三个新面。
• 将列表中的原始三等分面替换为新面之一，并将其​​他两个面附加到列表中。

4. 重复第 3 步，直到生成具有足够顶点的图。

如果您不需要最大平面图而只想要随机图，则从图中删除边。

• 如果您想要一个随机图，请删除任何边。
• 如果您想要一个随机连接的图，请删除任何不会断开该图的边（您可以使用深度或广度优先搜索来检查连接性）。
• 如果您想要一个随机双连通图，则删除任何不留下关节点的边（同样，您可以使用深度或广度优先搜索来检查双连通性）

请记住，我有 2 个主要约束：最小/最大边缘长度和最小/最大角度（任意 2 条边缘之间）

这是将图形嵌入到表面上的问题，而不一定是图形结构的问题。移动顶点并更改角度和边长。您可以尝试使用任何平面图绘制算法来生成嵌入，然后使用弹簧嵌入算法之类的算法来尝试修改嵌入以匹配您的约束。