Two objects are interacting (Object Alpha, Object Beta)
Each contain a point (x,y) which will be used to make comparisons, among other things.
Object Alpha’s point (x,y) attribute is dynamic and will change.
Object Beta’s point (x,y) attribute is final.
I need to construct a data structure that contains all Object Beta’s.
I was thinking of some sort of multidirectional arraylist with an index corresponding to the values of the point attribute so I can simply iterate backward and forwards to find the closest Beta’s within a given range, however, how would I construct a datastructure like this?
Perhaps a linked multidimensional array? Although this would be incredibly complex when one adds or removes elements.
Any other thoughts?
Use case – Object Beta essentially is an object occupying an object in real space. Ie, it’s point attribute corresponds to it’s GPS location. Object Alpha is another object in real space and it’s point attribute also corresponds to a GPS location. I want to quickly find the closest x amount of Beta’s to Alpha’s present location. Also add and remove Beta from this structure without completely redefining the entire structure. There could potentially be 1000+ object Beta’s in this data structure.
2
I recommend using an R-tree (link to Wikipedia). This is the standard data structure that most use for doing this sort of spatial indexing.
R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons. The R-tree was proposed by Antonin Guttman in 1984[1] and has found significant use in both theoretical and applied contexts.[2] A common real-world usage for an R-tree might be to store spatial objects such as restaurant locations or the polygons that typical maps are made of: streets, buildings, outlines of lakes, coastlines, etc. and then find answers quickly to queries such as “Find all museums within 2 km of my current location”, “retrieve all road segments within 2 km of my location” (to display them in a navigation system) or “find the nearest gas station” (although not taking roads into account). The R-tree can also accelerate nearest neighbor search[3] for various distance metrics, including great-circle distance.[4]
This is a pretty thoroughly explored topic, I recommend reading the entire Wikipedia article linked at the top of the answer.
Implementations in a few different languages:
- Java R-Tree
- Python R-Tree
- C# R-Tree
1