java - 连接图中最近点的最佳方法

Question

我有一系列点（城市），我正在寻找如何找到 10 个最近点并将它们连接起来以创建图形的最佳方法。每个点必须正好有 10 个连接。

点类：

public class City 
{
    int key;
    public int population;
    Point position;

    City(int key, int population, Point position)
    {
        this.key = key;
        this.population = population;
        this.position = position;
    }

    void setPopulation(int newPopulation)
    {
        this.population = newPopulation;
    }
}

现在我在一个数组中拥有所有点：

City[] cities = new City[3000];

所有点都有坐标（所有坐标都是五的倍数，因为我必须确定，每个点的最近点都在 5（公里）之外。

并且所有城市都是随机生成的，所以第一个城市可以在左上角，第二个城市可以在右下角。

当我绘制它们时，这就是所有点的外观。

现在我需要建议，如何找到最近的点以及如何连接它们以创建图形。

有什么建议吗？谢谢大家的回复。

Answer 1

一个非常简单的方法是为此使用一个库，例如JSI（参见nearestN），您可以确定它的速度很快（实际上，jsi是针对空间查询优化的 RTree 实现。

Answer 2

一个相对快速的解决方案是在每个点上使用经过调整的广度优先搜索，并连接到它遇到的前 10 个点。