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

Question

我想在 2D 空间中生成随机点，这些点将是平面图的节点（使用Gabriel 图算法或 RNG 构建）。

我编写了java代码来做到这一点，但我有两个难题要解决。

1）我需要图的所有边不超过给定的阈值

2）在我想知道图形的面之后，面是由边连接的节点的集合。一个面不包含其他节点。在下图中，面部由标签（F1，F2 ...）签名

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

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

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

Answer 1

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

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