Clever Geek Handbook

Range of values ​​based on key values

I am trying to implement a search method through a large number of 2D points for those that match a specific range. I'm going to create HashMaps for <X, Point>

and <Y, Point>

, but I'm wondering if it's okay for a HashMap because I will accept points in a range based on values ​​from x_min to x_max and y_min to y_max.

So I'll basically take all points <X,Point>

from x_min to x_max and compare them to points taken <Y,Point>

from y_min to y_max ...

HashMap<Integer,Point> x_coordinates = new HashMap<Integer,Point>();
for(int i=x_min;i<=x_max;i++){
    if(x_coordinates.containsKey(i))
        x_coordinates.get(i);
}

HashMap<Integer,Point> y_coordinates = new HashMap<Integer,Point>();
for(int i=y_min;i<=y_max;i++){
    if(y_coordinates.containsKey(i))
         y_coordinates.get(i);
}

Is there a faster way to get a range of values ​​from a HashMap or some other data structure?

+3


source to share


2 answers


I actually found a solution with:



TreeMap<Integer, TreeMap<Integer, Integer>> values;
for (int x : values.subMap(x_min, x_max).keySet()) {
        for (int y : values.get(x).subMap(y_min, y_max).values()) {
            // y here, represents the value of points in range...
        }
    }
+1


source


TreeMap is better as it supports a lot of features like floor, above, below, ceiling, etc. Thanks to this, you can create a single map TreeMap<Integer,Point> coordinates = new TreeMap<Integer,Point>();

and then request it for the coordinates of your interest. Note that the TreeMap is sorted according to natural ordering

its keys, or by the help Comparator

provided when creating the map.



If you are looking for more complex searches take a look at quad-tree

+1


source






More articles:


All Articles