I\'m trying to implement a method of searching trough a large amount of 2D point
ID: 639411 • Letter: I
Question
I'm trying to implement a method of searching trough a large amount of 2D points for those that match a certain range. I'm thinking of creating HashMaps for <X, Point> and <Y, Point> but I'm wondering is HashMap good for doing this, because I will be taking points in a range, based on values from x_min to x_max and y_min to y_max.
So I will basically take all points from <X,Point> searching from x_min to x_max and compare them to points taken from <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 type of data structure?
For example, if range = 200, select all points that match the range from x-200 to x+200 and from y-200 to y+200
I'm trying to avoid iteration through all of the points, but also I want to avoid making a huge 2D matrix, because the points in question are scattered around a large area.
After some testing and based on MichaelT's answer, I've written this code:
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 values of points in range...
}
}
Explanation / Answer
What you are describing is a sparse matrix upon which you wish to do a range select.
I'm going to start out with no, neither a HashMap nor a LinkedHashMap will do what you want optimally. The reason for this to find the elements in a range HashMap is effectively walking an unordered list - O(n). The LinkedHashMap may be slightly more optimal than awful if the elements are put into the LinkedHashMap in sorted order and no new ones are added afterwards. Its still not an optimal approach because instead of O(n) you're getting O(n/m) (because you stop walking the list once you get past the range) which is still effectively O(n). You can't do a binary search on the LinkedHashMap list.
So, lets look at some other structures. What you are really after is the SortedMap interface. It allows you to quickly pull out the sub map from one key to another with SortedMap subMap(K fromKey, K toKey) which is what you want to do. Pick one of those classes and you will have what you are after.
You could then get the values for each of the submaps and do a boolean retainAll(Collection c) of one set to the other.
That's the easy answer. It is effectively the lists of lists approach for the sparse matrix. You could, however encode the matrix instead in some other format that gives you a more direct sub range option. This isn't something that is part of the Java standard library and you may find yourself going down this path for writing your own implementation in that case.
If you see the possibility in the future that this may be the case, you should consider writing your own interface for the sparse matrix and then implement a class behind it that does the lookups that you want. This way if you later decide that you need to change the implementation for some reason, its a matter of changing the implementation (a new class that wraps something else) rather than changing all the code to handle a different structure.