我想在二维空间中生成随机点，这些点将是平面图的节点（使用Gabriel graph算法或RNG构建）。
我编写了java代码来完成这项工作，但我有两个难题要解决。
1）我需要图的所有边都不超过给定的阈值
2）在我想知道图的面之后，面是由边连接的节点的集合。面中不包含其他节点。在图像中，下面的面由标签（F1，F2…）签名
这两件事怎么办？一些算法有什么方法已经知道了？
下面是一个我必须创建的图表示例
http://imageshack.us/photo/my-images/688/immagineps.png/
最佳答案
如果你能容忍点的数量上的一些变化，那么你可以修改你的Gabriel图算法为增量（大部分的努力将使你的Delaunay算法增量），然后当一条边太长时，在圆中插入一个随机点，该边作为直径。
平面图最方便的数据结构是以边为中心的：例如doubly-connected edge list和quad-edge表示。如果你还没有在delaunay步骤中使用这种类型的数据结构（我无法想象你为什么不这样做），你可以按角度对每个顶点的输出连接进行排序。从这里开始，很容易实现一个函数，该函数接受一个半边并以逆时针顺序返回同一个面上的下一个半边。现在遍历所有的半边，对于每个尚未访问的半边，遍历面，直到返回到开始的位置。将内部迭代中的所有半边标记为一个面。