Java库用于（最远点）沃罗诺伊图

Question

4

我已经在谷歌上搜了几个小时，但是找不到一个Java库来计算（最远点）泰森多边形。

有一些小应用程序可以愉快地绘制Voronoi图，但我没有看过其中任何一个的源代码。

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

如果有好的解释如何编写自己的（最远点）Voronoi Diagram算法的方法，我也会接受建议。请注意，我并不真正关心效率，我只是试图证明使用这两个Voronoi图可以解决我的问题。

请注意，我需要同时使用FPVD和VD :)

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

- Roy T.

可能是Furthest-point Voronoi diagram in Java的重复问题。 - Alessandro Jacopson

3个回答

2

你可能想看一下 Tektosyne 库。

它可以生成 Voronoi 图和 Delaunay 三角剖分，转换为 DCEL 子图，并支持 A* 寻路、路径覆盖、泛洪、视线算法等图形算法。

- Zounadire

1

有很多免费的库可以创建各种输入数据的 Voronoi 图。

- azraelAT

我已经玩了一个小时，它似乎工作得很好，但是数据需要大量处理（因为它只输出边缘）。不过有一个问题，它没有计算最远点 Voronoi 图，但这只是重复 n-1 次算法吗？ - Roy T.

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alessandro Jacopson · Accepted Answer

有关算法的指针，请参见：

SKYUM，Sven。用于计算最小包含圆的简单算法。 Information Processing Letters，1991年，37.3：121-125。

摘要声称：

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

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

编辑：

Shamos在他的博士论文中写道（第201页）：

根据定理6.31，这个图[FPVD]仅由凸包上的点确定，这些点都是暴露的，因此没有有界区域。

Michael Ian Shamos。 1978年。 计算几何。博士论文。美国康涅狄格州纽黑文市，耶鲁大学。 AAI7819047。

我看到你正在寻找Java解决方案，但这里可以找到一个用C编写的解决方案，在qvoronoi Qu -- 最远点Voronoi图中有详细说明。