C 语言中计算高效的区间/密度搜索

Question

假设您有一个像这样的二维图(作为点列表):

现在假设您将绘图分成相等的正方形区域，如下所示:

问题 1:如果您想找到每个 block 的密度(每个区域的点数)，可以使用 C 语言中的哪些计算高效的技术(RAM 使用和处理方面的效率)时间)？

(而不是逐一比较每个点，看是否在每个方格的区间内)

问题2:如果添加一个新的点，可以用什么有效的方法找到该点所在的 block ，并计算该 block 的新密度。

(**注意:我并不是要求最有效的方法，因为那是基于意见的)

Answer 1

在 Java 中，假设坐标为非负且每个轴上的 bin 数量最多为 2^31:

Map<Pair<Integer, Integer>, List<Point>> binMap = new HashMap<>();
for (Point point : points) {
  Pair binXy = new Pair((int) (point.x / BIN_SIZE), (int) (point.y / BIN_SIZE));
  if (binMap.containsKey(binXy)) {
    binMap.get(binXy).add(point);
  } else {
    List<Point> pointList = new ArrayList<>();
    pointList.add(point);
    binMap.put(binXy, pointList);
  }
}

现在您可以枚举每个 bin 中的点:

for (Entry<Pair<Integer, Integer>, List<Point>> entry : binMap.entrySet()) {
  System.out.println("Bin: " + entry.getKey() + " Points: " + entry.getValue());
}