java - 一组 3D 点的聚类

Question

我有一个大小为 n 的二维数组，代表 3D 空间中的 n 个点，position[][] 代表 XYZ (例如，position[0][0] 是 X，position[0][1] 是 Y，position[0] [2] 为点 0 的 Z 坐标。

我需要做的是对点进行聚类，因此要有 n/k 个大小为 k 的簇，这样每个簇都包含 k 3D 空间中的最近 点。例如，如果 n=100 和 k=5，我想要 20 个 5 个点的簇，它们是空间中最近的邻居。

我怎样才能做到这一点？ (我需要伪代码。最好是 Java 代码片段)

到目前为止，我所做的只是基于每个组件的简单排序。但这并不一定给我最近的邻居。

1. 根据 X (position[0][0]) 排序
2. 然后根据Y排序(position[0][1])
3. 然后根据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 树的最近邻搜索 略有不同，因为每次迭代中的邻居不应与其他邻居重叠。我想我们可能需要将它用作组件，但如何使用，这是个问题。

Answer 1

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

float position[n][3];

因此，为了简化聚类和八叉树的创建，您可以使用 3D 点密度图。它类似于创建直方图:

1. 计算点的边界框 O(n)

   因此处理所有点并确定最小和最大坐标。

2. 创建密度图 O(max(m^3,n))

   所以将使用的空间 (bbox) 划分为一些 3D 体素网格(使用你想要/需要的分辨率)做一个密度图，如:

   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 。单元格中较大的数字 map[x][y][z]其中的点越多，这意味着有一个簇，您也可以将点移动到八叉树中的那个簇。

对于具有足够点的单元格，可以递归地重复此操作。使您的八叉树创建密度图 2x2x2并递归地拆分每个单元格，直到它的计数小于阈值或单元格大小太小。

有关详细信息，请参阅类似的QA

• Finding holes in 2d point sets?对于密度图

• Effective gif/image color quantization?用于聚类