我想获取构成多边形的点，以便用一些颜色填充它。我有一组点，然后计算出其Voronoi图。结果如下：
我已经了解了Gift Wrapping Algorithm和Convex Hull，但似乎它们并不符合我的需求。有没有适合这种情况的算法？我正在使用C++进行编程，但任何关于Java或C#的帮助都会有所帮助。
如何获取 Voronoi 单元周围的点？
6
我已经了解了Gift Wrapping Algorithm和Convex Hull，但似乎它们并不符合我的需求。有没有适合这种情况的算法？我正在使用C++进行编程，但任何关于Java或C#的帮助都会有所帮助。
- Andres
9
1我正在使用C++进行编程，因此Matlab不是一个选择，我需要一个算法来在我的程序中编写。 - Andres
1有没有一个平台无关的C++独立库？因为我要分发我的程序，而且我不能在每个地方都安装Matlab。我对Matlab不是很了解，所以我想问一下。 - Andres
如果你想部署它到其他电脑上，这已经不是一个选择了。虽然可行，但非常繁琐，而且会花费你很多时间。放弃它吧。 - David
是的，但我需要将它部署到其他电脑:/ - Andres
@Andres：你是如何计算沃罗诺伊图顶点的？如果你可以访问源代码，你可以修改它以保存这些顶点，并将它们与产生它们的点相关联。 - André Neves
显示剩余4条评论
2个回答
1
礼品包装算法（这是一个凸包算法）用于找到包含平面上一组点的最小凸多边形。但这不是你想要的。
Fortune's algorithm 是寻找 Voronoi 图的实际边界的好方法。它不是一个简单的算法，但在链接的维基百科页面上提供了完整的伪代码。在维基百科页面底部，有链接到几种不同语言的 Fortune 算法实现。
- Timothy Shields
6
1@Ph.T 我已经在我的回答中提供了完全相同的链接。你没有看到吗？ - Timothy Shields
抱歉 Timothy，我刚看到你的信息，实话实说我没有点击链接。干得好！ - Ph.T
@Ph.T 哈哈，没问题 - 我只是有点困惑你为什么要用完全相同的链接进行评论。 :) - Timothy Shields
1我正在使用的算法是幸运算法，它生成了我上传的图像，但它给我的是多边形的点，但我不知道它与哪个网站相关联，这就是我需要的。我已经搜索过这个算法，因为它有点复杂难以实现或者我无法完全理解它:/ - Andres
@Andres Fortune的算法在运行时找到了你所需要的所有信息。这应该是不言自明的：你拥有的图片标记边界线和边界顶点。如果问题是你只得到了这些边界，而没有每个边界段的相关生成点，那么你就需要直接将一些行为注入到你的实现中，在算法运行时保存这些信息。- 这是一个非常棘手的任务 - 需要超过你期望在Stack Overflow上获得的答案。维基百科页面上提到的“边界射线C_pq”是一个起点。 - Timothy Shields
0
你的Fortune算法实现似乎计算了自然嵌入，可以用于提取面的边缘列表。这是关键的数据结构。
struct Halfedge
{
struct Halfedge *ELleft, *ELright;
struct Edge *ELedge;
int ELrefcnt;
char ELpm;
struct Site *vertex;
float ystar;
struct Halfedge *PQnext;
};
ELleft和ELright似乎是一个包含特定顶点或面的入射边缘的双向链表，按角度排序。 如果它是一个面，那么你很幸运；否则，你可以通过将半边e更新为其目标顶点周围逆(顺)时针顺序的下一半边的反转来在面周围迭代（即ELleft的反转）。
- David Eisenstat
1
1很好，我一直在检查源代码并且看到了它。我已经看过其他的Voronoid库，比如http://blog.ivank.net/fortunes-algorithm-and-implementation.html，生成的Voronoi图并不总是正确的，但我有那种信息。看起来我想要的结构体是：`struct Halfedge *PQhash`。 - Andres
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接