Java库(最远点) Voronoi图

Question

我已经在Google上搜索了几个小时了，但是我找不到一个Java库来计算Voronoi图(最远点)。

有一些小程序很高兴地绘制了Voronoi图，但我还没有看到它的源代码可用。

我想回答的问题是，“这个Voronoi顶点的定义点是什么”，“离Voronoi顶点最近的点是什么”，以及“离Voronoi顶点最远的点是什么”。

我还将接受一个指针，说明如何编写我自己的(最远的) Voronoi图算法。请注意，我并不真正关心效率，我只是想证明使用这两个Voronoi图可以解决我的问题。

请注意，我需要FPVD和VDs :)

azraelAT帮我找到了一个普通Voronoi图的库，但我仍然没有找到能计算最远的Voronoi图的库！

Answer 1

对于指向算法的指针，您可以在以下位置看到：

天宇斯文。求最小围圆的一种简单算法。信息处理信函，1991年，37.3: 121-125。

抽象主张

..。计算算法..。点集的最远点Voronoi图

但是解释(在第3节)指定了一个凸点集。我不知道一组点的FPVD与例如S的凸包的FPVD之间的关系。

编辑：

Shamos博士论文写道(第201页)：

根据定理6.31，图FPVD仅由凸包上的点决定，这些点都是暴露的，因此不存在有界区域。

迈克尔·伊恩·沙莫斯。1978年。http://euro.ecom.cmu.edu/people/faculty/mshamos/1978ShamosThesis.pdf。博士论文。耶鲁大学，纽黑文，CT，美国。AAI7819047。

我读到您正在寻找java解决方案，但是这里您可以找到在qvoronoi Qu -最远-地点Voronoi图中解释的C解决方案

Answer 2

您可能想看看特克托芬库。

它可以生成Voronoi图和Delaunay三角剖分，并将其转换为DCEL细分，并支持A*路径查找、路径覆盖、洪水填充、叹息线等图形算法。

Answer 3

有那么多免费的库，它们创建Voronoi图，vrom各种类型的输入数据。

查看simplevoronoi，例如：http://sourceforge.net/projects/simplevoronoi/