algorithm - 具有固定最大边长的平面图

Question

我想在二维空间中生成随机点，这些点将是平面图的节点(使用 Gabriel graph 算法或 RNG 构建)。

我编写了 java 代码来执行此操作，但我有两个难题需要解决。

1) 我需要图的所有边都不长于给定的阈值

2) 在我想知道图的面之后，面是由边连接的节点的集合。面中不包含其他节点。在下图中，面孔由标签(F1、F2...)签名

这两件事怎么做？一些算法？有一些已知的方法吗？

下面是我必须创建的图表示例

http://imageshack.us/photo/my-images/688/immagineps.png/

Answer 1

1. 如果您可以容忍点数的一些差异，那么您可以将 Gabriel 图算法修改为增量算法(大部分工作将是使您的 Delaunay 算法增量)，然后每当边太长时, 在以该边为直径的圆中插入一个随机点。

2. 平面图最方便的数据结构是以边为中心的:例如，doubly-connected edge list和 quad-edge交涉。如果您还没有在 Delaunay 步骤中使用这种类型的数据结构(我无法想象您为什么不这样做)，您可以按角度对每个顶点的传出连接进行排序。从那里开始，很容易实现一个函数，该函数采用半边并以逆时针顺序返回同一面上的下一个半边。现在遍历所有半边，对于每个尚未访问的半边，围绕面部进行迭代，直到返回到开始的位置。将内部迭代中的所有半边标记为一个面。