具有固定最大边长度的平面图
我想在 2D 空间中生成随机点，这些点将是平面图的节点（使用 Gabriel graph 构建 算法或 RNG ）。
我写了java代码来做到这一点，但我有两个难题需要解决。
1）我需要图的所有边都不超过给定的阈值
2）在我想知道图的面之后，面是由边连接的节点的集合。面中不包含其他节点。在下图中，面孔由标签签名（F1，F2...）
如何做这两件事？一些算法？有一些已知的方法吗？
下面是我必须创建的图表示例
I want to generate random points in a 2D space, this points will be nodes of a planar graph (built using Gabriel graph algorithm or RNG ).
I wrote java code to do this, but I have two hard problem to solve.
1) I need that all edges of the graph are not longer than a given threshold
2) After I want know faces of graph, a face is a collection of nodes connected by edge. A face does not contain within it other nodes. In image below faces are signed by label (F1, F2...)
How to do these two thing ? some algorithms ? There is some way already known?
Below there is an example of the graph that I must to create
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果您可以容忍点数上的一些差异，那么您可以将您的 Gabriel 图算法修改为增量式（大部分工作将让您的 Delaunay 算法增量式），然后每当边太长时，插入一个以该边为直径的圆中的随机点。
平面图最方便的数据结构是以边为中心的：例如，双连接边列表 和 四边 表示形式。如果您尚未在 Delaunay 步骤中使用这种类型的数据结构（我无法想象您为什么不这样做），您可以按角度对每个顶点的传出连接进行排序。从这里开始，很容易实现一个函数，该函数采用半边并按逆时针顺序返回同一面上的下一个半边。现在迭代所有半边，并且对于尚未访问的每个半边，围绕面迭代，直到返回到开始的位置。将内部迭代中的所有半边标记为一个面。
If you can tolerate some variance in the number of points, then you could modify your Gabriel graph algorithm to be incremental (most of the effort would be making your Delaunay algorithm incremental) and then whenever an edge is too long, insert a random point in the circle having that edge as a diameter.
The most convenient data structures for plane graphs are edge-centric: for example, the doubly-connected edge list and the quad-edge representations. If you're not already using a data structure of this type for the Delaunay step (and I can't imagine why you wouldn't be), you can sort each vertex's outgoing connections by angle. From there, it's easy to implement a function that takes a half-edge and returns the next half-edge on the same face in counterclockwise order. Now iterate through all of the half-edges, and for each half-edge not already visited, iterate around the face until you return to where you started. Label all of the half-edges in the inner iteration as one face.