我有浮点坐标的 2d 点 (x,y)，当我绘制它们时，如果它们彼此靠近，我需要对点进行分组，并且应该在固定大小的矩形的帮助下将它们分组。问题是这些矩形不应该相交，所有的点-邻居应该被分组。
如果附近有纸，可以画一个大矩形，例如 4*5cm - 所有点所在的区域。现在随机放置点，比方说，如果有距离为 1 厘米的点 - 它们应该分组在 2*3 的矩形中。
我找不到如何制作它的算法，性能也很重要...我寻找嵌套、聚类，但我需要的有点不同。顺便说一句，如果某些分组矩形必须超出公共(public)区域以适应条件，那就这样吧，这不是问题。例如。你有 4*5 的面积，还有点
(1,0), (2,1), (4,1), (4,3), (2,4)
那么结果应该像 矩形 (0,0 - 3,2) & (3,1 - 6,3) 和一个点左 (2,4) 因为所有其他点都被分组并且此点现在没有任何邻居。
我的点的坐标不是整数而是 float ，点数可以是几百(最多 500)。而且我不想在相同的矩形上打断区域而只是计算那里有多少点，我的意思是例如上面我可以制作 react 角(0,0 - 3,2)，(3,0 - 6,2) , (0,3 - 3,6), (3,3 - 6,6) 并且只总结第一个矩形的点 2，第二个矩形的 1(!) 是什么意思保持原样，第三个为 1，第四个为 1 => 将绘制一个矩形，所有其他点 => 根据任务得出错误的结果。
有任何想法吗？至少哪些算法可以提供帮助，在哪里寻找...
附言目前结果中的组数/点数并不重要，e.i.上面示例的另一个允许的结果可能是 (1,0-4,2) 和 (2,2-5,4) 矩形，并且没有剩余点
最佳答案
一般问题是“nearest neighbor”搜索。解决方案在计算上是困难的(时间复杂度)。这对人类来说是一项相当容易的任务，但在计算上却并不那么容易。
关于algorithm - 当它们彼此靠近时分组点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2373932/