在我的编码过程中，我遇到了如下问题：在粒子密度最高的 2D 空间中查找固定大小的区域。可以认为粒子通常随机分布在整个空间中，但理论上应该有一些区域具有更高的密度。
例如，100 个粒子随机放置在 500x500 的 2D 网格中，我需要找到粒子最多（密度最高）的 50x50 区域。
除了暴力测试每个可能的区域（在本例中约为 200000 多个区域）之外，还有其他方法可以计算最佳区域吗？对于 n 长度轴，这将在 O（n^2） 处放大。
算法 1
创建一个 500x500 2D 数组，其中每个单元格包含该单元格中粒子数的计数。 然后用 50x50 内核卷积该数组，生成的数组将具有每个单元格中 50x50 区域中的粒子计数。 然后找到具有最大值的单元格。
如果使用 50x50 框作为区域，则可以将内核分解为两个单独的卷积，每个轴一个。 生成的算法是 O（n^2） 空间和时间，其中 n 是您要搜索的 2D 空间的宽度和高度。
提醒一下，带有 boxcar 函数的一维卷积可以在 O（n） 时间和空间内完成，并且可以就地完成。 设 x（t） 作为 t=1..n 的输入，设 y（t） 为输出。 为 t<1 和 t>n 定义 x（t）=0 和 y（t）=0。 将核 f（t） 定义为 1 表示 0..d-1，在其他地方定义为 0。 卷积的定义给了我们以下公式：
y（t） = 总和 i x（t-i） * f（i）= 总和 i=0..d-1 x（t-i）
这看起来需要时间 O（n*d），但我们可以将其重写为重复：
y（t） = y（t-1） + x（t） - x（t-d）
这表明一维卷积是O（n），与d无关。 要执行二维卷积，您只需对每个轴执行一维卷积。 这是有效的，因为 boxcar 内核可以分解：一般来说，大多数内核不能分解。 高斯核是另一个可以分解的核，这就是为什么图像编辑程序中的高斯模糊如此之快的原因。
对于您指定的数字类型，这将非常快。 500x500 是一个非常小的数据集，您的计算机最多可以在几毫秒内检查 202，500 个区域。 您将不得不问自己是否值得花费额外的小时、几天或几周的时间来进一步优化。
这与justhalf的解决方案相同，只是由于分解卷积，区域大小不会影响算法的速度。
算法 2
假设至少有一个点。 在不损失一般性的情况下，将 2D 空间视为整个平面。 设 d 为区域的宽度和高度。 设 N 为点数。
引理：存在一个最大密度区域，其左边缘有一个点。
证明：设 R 为最大密度区域。 设 R' 为同一区域，右平移为 R 的左边缘和 R 中最左边点之间的距离。 R 中的所有点也必须位于 R' 中，因此 R' 也是最大密度的区域。
算法
-
将所有点插入到 K-D 树中。 这可以在 O（N log2 N） 时间内完成。
-
对于每个点，请考虑宽度 d 和高度 2 d 的区域，其中点以该区域的左边缘为中心。 将此区域称为 R。
-
在 K-D 树中查询区域 R 中的点。 将此集合称为 S。 这可以在 O（N1/2+|S|）时间。
-
查找 R 的 d x d 子区域，其中包含 S 中的最大点数。 这可以在 O（|S|日志 |S|）时间通过按 y 坐标对 S 进行排序，然后执行线性扫描。
得到的算法的时间为 O（N3/2 + N |S|日志 |S|）。
比较
当密度较高时，算法 #1 优于算法 #2。 算法 #2 仅在粒子密度非常低时才优越，并且算法 #2 优于的密度随着总电路板尺寸的增加而减小。
请注意，连续情况可以认为具有零密度，此时只有算法 #2 有效。
你使用什么蛮力方法，但最蛮力的方式是O(n^2 d^2)，通过在O(n^2)时间内迭代每个区域，然后在O(d^2)时间内计算该区域中的粒子数量，其中d是您所在区域的大小。
这个问题和这个问题一模一样：老鼠攻击，因为区域面积是固定的，所以密度和计数一样，解决方案O(n^2 + k*d^2) ，其中
-
n是整个区域的大小（边的长度） -
k是粒子的数量 -
d是每个区域的大小（边的长度）
通过此算法：
- 对于每个粒子，更新受此粒子影响的
O(d^2)区域的计数 - 遍历所有可能的
O(n^2)区域，找到最大值
如此代码所示，我在此处复制相关部分供您参考：
using namespace std;
int mat [1024 + 3] [1024 + 3]; // Here n is assumed to be 1024
int main ()
{
int testCases; scanf ("%d", &testCases);
while ( testCases-- ) {
Set(mat, 0);
int d; scanf ("%d", &d); // d is the size of the region
int k; scanf ("%d", &k); // k is the number of particles
int x, y, cost;
for ( int i = 0; i < k; i++ ) {
scanf ("%d %d %d", &x, &y, &cost); // Read each particle position
// Update the count of the d^2 region affected by this particle
for ( int j = max (0, x - d); j <= min (x + d, 1024); j++ ) {
for ( int k = max (0, y - d); k <= min (y + d, 1024); k++ ) mat [j] [k] += cost;
}
}
int resX, resY, maxi = -1;
// Find the maximum count over all regions
for ( int i = 0; i < 1025; i++ ) {
for ( int j = 0; j < 1025; j++ ) {
if ( maxi < mat [i] [j] ) {
maxi = mat [i] [j];
resX = i;
resY = j;
}
}
}
printf ("%d %d %dn", resX, resY, maxi);
}
return 0;
}
我已经把我的注释放在代码中向你解释。
该区域划分为 1000x1000，并计算每个（重叠）2x2 中的粒子数量。只需规范化 0..1、缩放 0..999 并强制转换为整数即可对它们进行分区。计数可以很容易地存储为整数的 2D 数组（ushort、uint 或 ulong...嗯茶）。这相当于宽相位碰撞检测中使用的简单 2D 空间分区。