1

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.

  • 1
    Could you get a little more specific about your use case please? – durron597 Feb 26 '15 at 18:42
  • @durron597 is that any better? – easymoden00b Feb 26 '15 at 18:48
5

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:

  • Sounds almost perfect. Thank you. I'll definitely thoroughly research it to ensure so before implementation. – easymoden00b Feb 26 '15 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.