如何获得voronoi细胞周围的点数？

Question

我试图获得形成多边形的点,以填充一些颜色.我有一组点,然后我为它计算Voronoi图.结果是这样的:

绿点是我定义的点,蓝点是Voronoi图的计算顶点.我想填充由特定绿点生成的多边形,所以我需要知道它周围的哪些点形成多边形并填充它.

我读过有关礼品包装算法和凸包的内容,但它似乎并不是我需要的.有没有适合这种需求的算法？我使用C++编程,但Java或C#中的任何帮助都会有所帮助.

Answer 1

Gift Wrapping 算法（凸包算法）用于查找包含平面中一组点的最小凸多边形。这不是你想要的。

Fortune 算法是查找 Voronoi 图实际边界的良好解决方案。这不是一个简单的算法，但链接的维基百科页面上提供了完整的伪代码。在维基百科页面的底部，有一些不同语言的财富算法实现的链接。