我试图让形成多边形的点用一些颜色填充它。我有一组点，然后我为它计算 Voronoi 图。结果是这样的：
绿点是我定义的点，蓝点是 Voronoi 图的计算顶点。我想填充由特定绿点生成的多边形，所以我需要知道它周围的哪些点来形成多边形并填充它。
我已经阅读了有关礼品包装算法和凸壳的信息，但它似乎不是我所需要的。有没有适合这种需求的算法？我正在使用 C++ 进行编程，但对 Java 或 C# 的任何帮助都会有所帮助。
问问题
2782 次
2 回答
1
Gift Wrapping 算法（这是一种凸包算法）用于找到包含平面中一组点的最小凸多边形。这不是你想要的。
Fortune 的算法是寻找 Voronoi 图的实际边界的一个很好的解决方案。这不是一个简单的算法，但链接的 Wikipedia 页面上提供了完整的伪代码。在 Wikipedia 页面的底部，有几个不同语言的 Fortune 算法实现的链接。
于 2013-05-28T17:25:15.297 回答
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）来迭代面。
于 2013-05-29T22:49:47.137 回答