给定一组具有 x、y 和 z 坐标且边界为 0 到 1(含)的点，确定它们是否全部均匀分布(或接近)

Question

我想确定一组点是否均匀分布在1 x 1 x 1立方体中。每个点都有一个x、y和z坐标，对应于它们在立方体中的位置。
我能想到的一个简单的方法是将点集平铺成2个图，并检查它们是如何正态分布的，但我不知道这是否是正确的方法。
还有人知道吗?

Answer 1

我会计算点密度图然后检查其中的异常:

1. 定义

   假设我们有N个点要测试。如果这些点是均匀分布的，那么它们应该形成"均匀网格"。mmm个点:

   m * m * m = N
   m = N^(1/3)
   

   为了考虑来自均匀网格和评估统计的干扰，您需要将立方体划分为立方体网格，每个立方体将包含几个点(因此可以计算统计属性)，假设每个网格立方体有k>=5个点，因此:

   cubes = m/k
   

2. 创建计数器的3D数组

   我们需要每个网格立方体的整数计数器，所以:

   int map[cubes][cubes][cubes];
   

   用0填充

3. 处理所有p(x,y,z)点并更新map[][][]点

   简单地循环遍历所有的点，并计算它们所属的网格立方体位置，并通过递增来更新它们的计数器。

   map[x*(cubes-1)][y*(cubes-1)][z*(cubes-1)]++;
   

4. 计算map[][][]的平均计数

   这样的简单平均数就可以了:

   avg=0;
   for (xx=0;xx<cubes;xx++)
   for (yy=0;yy<cubes;yy++)
   for (zz=0;zz<cubes;zz++)
   avg+=map[xx][yy][zz];
   avg/=cubes*cubes*cubes;
   

5. 现在只需计算abs到这个平均值的距离

   d=0;
   for (xx=0;xx<cubes;xx++)
   for (yy=0;yy<cubes;yy++)
   for (zz=0;zz<cubes;zz++)
   d+=fabs(map[xx][yy][zz]-avg);
   d/=cubes*cubes*cubes;
   

   d将保存一个度量，告诉点离均匀密度有多远。式中0表示均匀分布。所以只要设定阈值。d也取决于点的数量，我的直觉告诉我d>=k意味着完全不均匀，所以如果你想让它更健壮，你可以这样做(阈值可能需要调整):

   d/=k;
   if (d<0.25) uniform;
   else nonuniform;
   

正如你所看到的，所有这些都是O(N)时间，所以它应该足够快。如果不是，你可以通过跳过点来评估每10个点，但这只能在点的顺序是随机的情况下进行。如果不是，你就需要选择N/10个随机点。10可能是任何常数，但你需要记住，你仍然需要足够的点来处理，以便统计结果代表你的集合，所以我不会低于250点(但这取决于你到底需要什么)

这里是我使用密度图技术的一些答案:

• 在2d点集中寻找洞?
• 球体上最高密度的位置