java - 如何使用四叉树对图进行分区？

Question

我有一个程序，允许用户在大小为 1000 x 750 的 JFrame 上绘制顶点和边。现在我需要使用四叉树根据单个象限中有多少个顶点来划分输入图。如果有人能指出如何实现这一目标的正确方向，我将不胜感激？

附加信息：我有一个 Edge 类，它存储：源（顶点）、目标（顶点）和权重。我有一个 Vertex 类，它存储：名称、x 坐标、y 坐标和 Ed​​ge[] 相邻列表。我还有一个 Graph 类，它存储两个 ArrayList：边和顶点。

Answer 1

我最近实现了代码，应该可以解决您的问题。在我最近的博客文章中可以免费下载。空间分解的四叉树，Java 实现http://kirstywilliams.co.uk/blog/2012/08/quadtrees-java-implementation/

Answer 2

更多的四叉树实现都是 apache 许可的：

• Apache SIS - 无需测试，速度很快，但需要进行一些改进
• GraphHopper - 通过测试，内存消耗更少，但可能会慢一些。距离计算是可插拔的。

但是，如果您已经在内存中有一个连通图，您可以创建一个内存效率更高（但也有点复杂）的解决方案。零件在此处实现，更多详细信息可在此处获得。

另一个有趣的 repo（但我认为是 neo4j 本身是 AGPL），其中包含一些空间集合。