Rechnerisch Effiziente Intervall/Dichte Searching in C

Question

Angenommen, Sie haben einen 2D-Plot haben wie diese (als Liste von Punkten):

Lassen Sie uns jetzt sagen, Sie die Handlung in gleiche Quadrat aufgespalten Bereiche wie so:

Frage 1: Wenn Sie die Dichte eines jeden Blocks (die Anzahl der Punkte pro Fläche), was für die Berechnung finden wollte es könnten auch effiziente Techniken in C verwendet werden (Effizienz in Bezug auf RAM-Nutzung und Verarbeitungszeit)?

(Anstatt jeden Punkt eins nach dem anderen zu vergleichen, um zu sehen, ob es in dem Intervall jedes Quadrates liegt)

Frage 2: Wenn ein neuer Punkt hinzugefügt wurde, was für effiziente Methoden verwendet werden könnten, zu finden, die Blockieren Sie den Punkt, in dem sich der Punkt befindet, und berechnen Sie die neue Dichte des Blocks.

(** Hinweis: Ich bin nicht für die effizienteste Methode zu fragen, wie diese Meinung wäre basiert)

Answer 1

In Java, unter der Annahme, Koordinaten sind nicht-negativ ist und die Anzahl der Behälter ist höchstens 2^31 auf jeder Achse:

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); 
    } 
} 

Jetzt können Sie die Punkte in jedem Fach aufzählen:

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