0

I have a dictionary like this :

Dictionary<Data, Vector2>;

Data is a 2D position (x, y). I want to have a function that gets all Data within a position and radius. Like this:

Data[] DataWithinDistance(Vector2 position, float radius){}

Is there any way to do this faster than O(n)?

filipot
  • 176
  • 2
  • 10
  • 3
    Have you considered other data structures to store this? Quadtree for example. – stephen.vakil Apr 13 '16 at 14:26
  • 3
    Possible duplicate of http://stackoverflow.com/questions/12412869/efficiently-find-nearest-dictionary-key – Wjdavis5 Apr 13 '16 at 14:28
  • 2
    A dictionary matches keys while you want to calculate distances. You need to use a spatial construct like a QuadTree, R-tree etc – Panagiotis Kanavos Apr 13 '16 at 14:29
  • 1
    @Wjdavis5 not a duplicate. You *can't* use a sorted collection for spatial queries without some very, very complex mappings (using space-filling curves). For example, sorted according to *which* dimension? And how would that sorting translate to *distance* from an arbitrary point. – Panagiotis Kanavos Apr 13 '16 at 14:32
  • @stephen.vakil Yes i have, thought did not know where to look. I will look into Quadtree. Thank you. – filipot Apr 13 '16 at 14:32
  • @PanagiotisKanavos - Ok - but the answers on that question solve this specific problem. – Wjdavis5 Apr 13 '16 at 14:35
  • 2
    @Wjdavis5 no it doesn't. SortedList sorts according to *one* value only. Distance is calculated using *two or more* coordinates. SortedList could sort points on a line but not points on a surface. – Panagiotis Kanavos Apr 13 '16 at 14:39
  • You can use a sorteddictionary. The x value would then be in the range of x would be x-range to x+range which would reduce the number of points you would need to verify. – jdweng Apr 13 '16 at 14:44
  • @PanagiotisKanavos I'm guessing you just arent reading all the answers. If the key is a type you could easily implement IComparable and IEquatable make the list sortable by the type. But i'm not even talking about SortedList. I was referring to the BTree implementation specifcally. You could also use a SortedList if your 'coordinates' are indeed spatial (lat /long) if you generate a geohash. For example the Redis GEO impl. In fact uses a SortedSet to order items by relative location. – Wjdavis5 Apr 13 '16 at 14:44
  • @Wjdavis5 did you link to the wrong question then? There are no mentions of geohashes in the question you linked. And that *is* an application of space-filling curves, which I did mention – Panagiotis Kanavos Apr 13 '16 at 14:51
  • @PanagiotisKanavos The second and third answers relate directly to finding the neighbors of a specified key in a sorted dictionary. http://stackoverflow.com/a/27653053/1387186 http://stackoverflow.com/a/17813916/1387186 – Wjdavis5 Apr 13 '16 at 14:53
  • @WJdavis - but the difference here is you don't have a single linear range of values, you have a range in _two_ dimensions. – D Stanley Apr 13 '16 at 15:21
  • @DStanley This is where the geohash concept I mentioned would apply. It takes an x,y coordinate and generates an integer hash that is sortable. But yes I agree its probably not a duplicate. – Wjdavis5 Apr 13 '16 at 15:25
  • @DStanley - I have adapted the answers on that page to a kNN search using distance (2d) and time (3d). To do so required multiple dictionaries to key off of though. – Wjdavis5 Apr 13 '16 at 15:26

1 Answers1

2

if it is possible to do this without going through all the entries in the dictionary?

No - Dictionaries store keys as single values. Your values are points. You want to find all items that have a position within a certain distance relative to another value. Since you can't do that without performing some calculation on the key value (and that value is dependent on two properties of the key), there's no way around a dictionary scan.

You could try a structure that enables you to "filter" based on x and y values independently, since you could find all possible x and y values within that distance, and search the collection from there.

Something like a SortedDictionary<int, SortedDictionary<int, Vector2>>? It may not be as effective for other searches but it would let you easily get values within a certain range of x and y values.

Or use a SortedDictionary that keys off of one of the coordinates. You'd still have to scan the values to filter by the other coordinate but it would cut your complexity from O(N) to O(sqrt(N)) I believe (I'm not great on Big-O notation so I could be wrong there)

D Stanley
  • 149,601
  • 11
  • 178
  • 240
  • I tried this but ran into similar problems while doing this part: "but it would let you easily get values within a certain range of x and y values." – filipot Apr 13 '16 at 15:11
  • @Vermacian55 Can you be more specific about the problems you had? Was it coming up with the ranges of x and y values or accessing the nested dictionary? – D Stanley Apr 13 '16 at 15:23
  • @D Stanley The ranges. Lets say, you want to get all the entries between x = 5 and x = 15. How would you do that without going through the whole Dictionary. – filipot Apr 13 '16 at 15:39
  • `.SkipWhile(kvp => kvp.Key < min).TakeWhile (kvp => kvp.Key <= max)` would be one way. it's not perfect but it stops iterating once it reaches the max value. – D Stanley Apr 13 '16 at 15:46
  • "would cut your complexity from O(N) to O(sqrt(N))" This would be true if both dimensions were equal or of comparable size. If one is much bigger than the other then you do even better than that if you key off of the bigger dimension, and you do worse than that if you key off of the smaller dimension. If you wanted to be technical, a scan is O(N *M) where N and M are the two dimensions, and keying off of one dimension turns that into O(M). – Servy Sep 30 '20 at 19:03