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

Question

我正在尝试确定一组点是否均匀分布在 1 x 1 x 1 立方体中。每个点都带有一个 x、y 和 z 坐标，对应于它们在立方体中的位置。
我能想到的一种简单方法是将点集展平成 2 个图形并检查两者的正态分布情况，但是我不知道这是否是正确的方法。
其他人有什么想法吗？

Answer 1

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

定义

假设我们有 N 个点要测试。如果这些点是均匀分布的，那么它们应该形成 mmm 个点的“均匀网格”：
```
m * m * m = N
m = N^(1/3)
```
为了解决来自统一网格的干扰并评估统计数据，您需要将立方体划分为立方体网格，其中每个立方体将包含多个点（因此可以计算统计属性）假设每个网格有 k>=5 个点多维数据集：
```
cubes = m/k
```
创建计数器的 3D 数组

简单地说，我们需要每个网格立方体的整数计数器，所以：
```
int map[cubes][cubes][cubes];
```
用零填充它。
处理所有点p(x,y,z)并更新map[][][]

简单地遍历所有点，计算它们所属的网格立方体位置，并通过递增来更新它们的计数器。
```
map[x*(cubes-1)][y*(cubes-1)][z*(cubes-1)]++;
```

计算 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;

现在只需计算与此平均值的绝对距离
```
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 点（但这取决于你到底需要什么）

以下是我使用密度图技术的一些回答：

Finding holes in 2d point sets?
Location of highest density on a sphere

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

Given a set of points with x, y and z coordinates whose bounds are 0 to 1 (inclusive), determine if they're all uniformly distributed (or close to)

math

geometry