java - 最佳搜索给定区域中的 2D 点(网络服务)

Question

我有一种算法和性能问题需要用 Java 解决。我收集了大量二维点(假设大约有 100 000 个)。我想得到一组在搜索点 SP(X_sp, Y_sp) 周围的给定区域中的它们，这样我就想得到满足条件的点 P(x y):

x 在 X_sp - constValue 和 X_sp + constValue 之间并且 y 在 Y_sp - constValue 和 Y_sp + constValue 之间

为了让您了解数字关系，constValue 将类似于 2、5 或 10，而 x、y 将介于 0 和 1000 之间。它意味着是一个网络服务，因此可以搜索许多不同的点同时必须考虑在内。

由于这些是固定点(不会因计算或其他原因而改变)，我认为最好提供一个按 X 排序的对象列表和另一个按 Y 排序的对象列表。然后，我将首先获取 X 范围内的点，并使用引用从另一个列表(按 Y 排序)中获取这些点的集合。然后我将通过 Y 缩小此选择范围，结果得到给定区域中的点。

我对Java不是很了解，想请教一下最优化的方法。我应该使用哪些对象来存储排序点，以便快速搜索范围内的对象？或者，也许我必须为此任务实现我的自定义算法？此外，当谈到将点存储在数据库中时，SQL 查询是否足够快以提供结果？或者也许 NoSQL 数据库更适合这个？

我将进行自己的测试，但我正在寻找起始候选人。

Answer 1

我可能会使用 TreeMap<Integer, TreeSet<Integer>> ，其中 map 的关键是 x坐标和每个x坐标，你有一个列表 y坐标。然后您可以使用 floorEntry 和 ceilingEntry 找到 x在您的范围内的坐标。然后对于每个 TreeSet<Integer>设置你得到的，你可以使用 ceiling 和 floor 获取适当的条目。

当然，这只会为您提供框边界(四个角)的坐标。但是TreeSet还有一个 subset 这会给你一系列的值(value)。你将不得不使用它两次；一次用于 x 的列表坐标(您可以使用 map 的 keySet 方法获取键集)在您的范围内，然后对于每个 x坐标，y范围内的坐标。所以伪代码有点像这样:

List<Point> result = new ArrayList<>();
int lowerX = points.ceilingKey(x - c);
int upperX = points.floorKey(x + c);
for each x coordinate in points.entrySet().subset(lowerX, upperX)
    TreeSet<Integer> yCoordinates = points.get(x);
    lowerY = yCoordinates.ceiling(y - c);
    upperY = yCoordinates.ceiling(y + c);

    for each y coordinate in yCoordinates.subset(lowerY, upperY)
       result.add(new Point(x, y))

我还没有对此进行测试，因此可能存在一些错误或我遗漏了什么。让我知道，我会更正答案。

floor和 ceiling电话是log(n)我相信——这是您获得性能优势的地方，因为如果您使用列表，它将是 O(n)查一下。

注意:我不知道这是否是性能最高的。 SO 通常不适合提出此类开放式问题，因此您在其他地方可能会有更多运气。