时间戳

首页 > 解决方案 > 在没有交叉的顶点之间生成随机边

algorithm - 在没有交叉的顶点之间生成随机边

问题描述

我在二维空间中有任意一组顶点。我想在这些顶点之间几乎随机地生成边缘，以使以下三个条件成立：

  1. 每个顶点至少有一条边。
  2. 没有两条边彼此相交，除非可能在一个公共顶点处。
  3. 除了初始集合之外，不需要添加新的顶点。

一般来说，我不太清楚如何解决这个问题。我最初试图将我的顶点强制构造成整齐的列（尽管同一列中的顶点之间具有任意垂直间距），然后一次形成一列的边缘，顶点仅连接到下一列中的顶点。我想我可以检查当前行中较高的顶点是否连接到下一行中较低的顶点，如果是，则阻止任何符合该条件的边。（换句话说，如果 V[j,k] 是“从 j 列顶部开始的第 k 个顶点”，那么我会阻止 V[j,k1] 和 V[j+1,k2] 之间的任何边，如果在任意顶点 V[j,k3] 和 V[j+1,k4] 之间存在一条边，其中 k4>k2 且 k3<k1。）

但它似乎不起作用，更糟糕的是，它留下了一些没有任何边的顶点。我怎样才能解决这个问题？（如果可能的话，完全没有那种强制的列结构；我希望它能够尽可能地处理一组顶点。）

标签： algorithmgraph

解决方案

从极坐标和区间操作的角度来解决这个问题。列出未连接的顶点；应用随机洗牌。

对于每个未连接的点P：

  • 列出所有“可见”点的列表P：那些未被边缘阻挡的点（见下文）。
  • 随机选择一个“可见”点Q；将边 PQ 添加到图中

确定一个点是否“可见”可能很乏味，但在实践中可以大大改善搜索空间。

  • 平移所有坐标，即P原点。
  • 计算每个其他点的极坐标 (r, theta)。
  • 对于每条边 AB，角度范围 (A.theta, B.theta) 与角度 (0, 2*pi) 的环绕描述了一个扇形空间，其顶点位于P。C简单地说，如果 Cr > max(Ar, Br) ，该切片中的任何点都是不可见的——如果它P比任一端点更远。同样，如果它比任一端点更近，它仍在考虑中。对每一点都进行检查C应该会严重减少您的候选人名单。

对于剩余的可能可见点： - 最近的点P 必须是可见的。- 对于任何其他点 C，执行与覆盖其角度 (theta) 的所有边 AB 的相交检查，使得 rA < rC < rB 或反之亦然（C 在半径上“介于”A 和 B 之间）。对于这样的边，检查 PC 是否与 AB 相交（直接检查直角坐标）。

剩下的是所有可见点的列表P（请注意，必须至少有一个，除非P是图中唯一的点；如果图中至少有 2 个点与 不同角度P，则必须至少有两个这样的点）。随机选择一个并添加边缘。

这可能不是计算效率最高的算法。然而，它很容易可视化，可以直接实施每个步骤，并且很容易看出它为给定问题提供了解决方案。

推荐阅读