有没有一种有效的方法来计算细胞中的点？

Question

我有各种各样的点图： -

每个图表上最多有100万个点。您可以看到这些点分散在一个单元格网格上，每个单元格大小为200 x 100单位。所以显示了35个单元格。

有没有一种有效的方法来计算每个细胞中有多少个点？蛮力方法似乎是将数据解析35次，整个负载组合小于或大于语句。

Answer 1

下面的一些步骤可以进行优化，因为您可以在构建数据集时执行其中的一些步骤。但是我会假设你只是给了一系列点，你必须找到它们适合的细胞。如果您可以将自己的代码注入到构建图形的步骤中，那么您可以在构建图形的过程中执行下面编写的内容，而不是在事实之后。

在刚刚获得数据的情况下你会被蛮力所困，除非你必须至少访问每个点以找出它所在的单元格，否则你无法知道其他情况。因此我们坚持使用O（ N）。如果你有其他一些你可以利用的知识，那将由你来利用 - 但由于OP中没有提及，我会假设我们陷入了蛮力。

高级别战略如下：

// 1) Set rectangle bounds to have minX/Y at +inf, and maxX/Y to be -inf
// or initialize it with the first point

// 2) For each point:
//       Set the set the min with min(point.x, bounds.min.x)
//       Same for the max as well

// 3) Now you have your bounds, you divide it by how many cells fit onto each
// axis while taking into account that you might need to round up with division
// truncating the results, unless you cast to float and ceil()
int cols = ceil(float(bounds.max.x - bounds.min.x) / CELL_WIDTH);
int rows = ceil(float(bounds.max.y - bounds.min.y) / CELL_HEIGHT);

// 4) You have the # of cells for the width and height, so make a 2D array of
// some sort that is w * h cells (each cell contains 32-bit int at least) and
// initialize to zero if this is C or C++

// 5) Figure out the cell number by subtracting the bottom left corner of our
// bounds (which should be the min point on the x/y axis that we found from (1))
for (Point p in points):
    int col = (p.x - minX) / cellWidth;
    int row = (p.y - minY) / cellHeight;
    data[row][col]++;

优化：

我们有一些方法可以加快速度：

• 如果你有两个单元宽度/高度的幂，你可以做一些位移。如果它是10的倍数，this might possibly speed things up if you aren't using C or C++，但我还没有对此进行分析，所以也许Java中的热点等都会为你做这件事（而且不知道Python）。然后再一百万点应该相当快。
• 我们不需要在开始时查看整个范围，如果我们找到更大的值，我们可以继续调整表格的大小并添加新的行和列。这样我们只对所有点进行一次迭代而不是两次。
• 如果你不关心额外的空间使用而且你的数字只是正数，你可以通过假设一切都已经相对于原点而不是相减来避免“转换为原点”减法步骤。你可以通过修改代码的步骤（1）来使min从0开始而不是inf（或者如果你选择那个第一点）。这可能是坏的，但是如果你的点在轴上非常远，你最终会产生大量的空槽。您知道您的数据以及这是否可行。

可能还有一些事情可以做，但这会让你走上正确的道路来提高效率。你也可以回到它的哪个细胞。

编辑：这假设与网格大小相比，您将不会有一些非常小的单元格宽度（例如您的宽度为100个单位，但您的图表可能跨越200万个单位）。如果是这样，那么你需要查看可能稀疏的矩阵。