可以落在矩形中的Java分组点

Question

我正在做一项研究，我坚持以有效的方式解决算法。如果有人帮助我，我会非常有帮助 -

算法-

我有一组点 (x1,y1) , (x2,y2)...(可以是 10000 个点)。我想在一个组中打印点 - 可以用 10x10 的矩形包围。

例子-

p1 (10,10)
p2 (15,15)
p3 (40,100)
p4 (40,50)
p5 (40,90)
p6(200,200)
p7(400,350)

output 

gp1 -> p1 (10,10), p2 (15,15)
gp2 -> p3 (40,100), p5 (40,90)

解释 - 如果一个 10x10 的矩形从点 p1 开始，点 p1 和 p2 将落在一个矩形中。如果矩形从点 p3 开始，则类似的 p3 和 p5 将落在 10x10 的矩形中。如果我们能找出包围它们的每个矩形的坐标，也会很有帮助。

注意:单个点可以属于 2 个不同的组。在这种情况下，所有点都将被视为一个组，然后矩形的大小会增长

我试过的 -

我尝试取点 p1 坐标并将其 x 和 y 与其他点进行比较。如果我在它附近找到 p2 点。我将它们添加到一个组中，然后跳过 p2 比较其他人。我用 p3 再次开始处理。

这似乎不是一个有效的解决方案，因为在最坏的情况下它可能具有 nxn 的复杂性，这非常糟糕。

注意:请大家不要将此视为作业，因为它不是。

Answer 1

为了从聚类问题中获得任何合理的性能，您首先需要将数据组织成符合算法要求的数据结构。您尝试解决的问题可能非常适合“k-d 树”http://en.wikipedia.org/wiki/K-d_tree

将数据组织成 k-d 树后，您就可以更有效地询问有关各个节点之间距离关系的问题。

这里有一个关于 k-d 树的 java 实现的 stackoverflow 问题。 KDTree Implementation in Java