java - 一组3D点的聚类

我有一个大小为n的二维数组，表示3d空间中的n点数，position[][]表示xyz（例如，position[0][0]是X，position[0][1]是y，position[0][2]是点0的z坐标）。
我需要做的是对这些点进行聚类，这样就有了n/k个大小为k的簇，这样每个簇都由3D空间中最近的k点组成例如，如果n=100和k=5，我希望有20个由5个点组成的簇，它们是空间中最近的邻居。
我怎样才能做到（我需要伪代码对于代码片段，最好使用Java）
到目前为止，我所做的是基于每个组件的简单排序。但这不一定给我最亲密的邻居。
基于X排序（position[0][0]）
然后根据y（position[0][1]）排序
然后根据Z（position[0][2]）排序

for (int i=0; i<position.length; i++){
  for (int j=i+1; j<position.length; j++){
    if(position[i][0] > position[i+1][0]){
      swap (position[i+1][0], position[i][0]);
     }
   }
}
// and do this for position[i][1] (i.e. Y) and then position[i+2][2] (i.e. Z)

我相信我的问题与使用kd树的最近邻搜索略有不同，因为每次迭代中的邻居不应该与其他邻居重叠我想我们可能需要把它作为一个组件，但如何，这是个问题。

最佳答案

在开始时，您没有八叉树，而是点列表，例如：

float position[n][3];

因此，为了简化聚类和八叉树的创建，可以使用三维点密度图它类似于创建直方图：
计算点的边界框O(n)
所以处理所有点，确定最小和最大坐标。
创建密度图O(max(m^3,n))
因此，将已用空间（bbox）划分为一些三维体素网格（使用所需的分辨率）进行密度贴图，如下所示：

int map[m][m][m]`

用零清除它。

for (int x=0;x<m;x++)
 for (int y=0;y<m;y++)
  for (int z=0;z<m;z++)
   map[x][y][z]=0;

然后处理所有点，从x,y,z中确定其单元位置并递增。

for (int i=0;i<n;i++)
 {
 int x=(m-1)*(position[i][0]-xmin)/(xmax-xmin);
 int y=(m-1)*(position[i][1]-ymin)/(ymax-ymin);
 int z=(m-1)*(position[i][2]-zmin)/(zmax-zmin);
 map[x][y][z]++;
 // here you can add point i into octree belonging to leaf representing this cell
 }

这将给你低分辨率密度地图单元格中的数字越大，其中的点就越多，这意味着存在一个簇，您还可以将点移动到八叉树中的该簇。
对于具有足够点数的单元格，可以递归地重复此操作要使八叉树创建密度映射map[x][y][z]并递归地拆分每个单元格，直到其计数小于阈值或单元格大小太小。
有关更多信息，请参见类似的QAS
Finding holes in 2d point sets?密度图
Effective gif/image color quantization?对于集群

关于java - 一组3D点的聚类，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45670393/