Jump to content

  • Log In with Google      Sign In   
  • Create Account

Best data structure for storing pointers with indexing by 3D points


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
2 replies to this topic

#1 daedalic   Members   -  Reputation: 104

Like
0Likes
Like

Posted 29 March 2012 - 05:56 PM

This data structure will have frequent insertions and lookups. In addition, it needs to be able to return a null pointer if it is indexed by a 3D point that has not had an insertion associated with it. Up to millions of pointers will be inserted into this structure.

At first glance some form of associative array seems appropriate, but the 3D component complicates things. So I'm not sure if i need to use spatial partitioning with this or not.

If its any help, the ranges for the x and y components are integers from 1 to 100,000+. For the z component it will range from 1 to 1,000+. The points that index this structure will be near each other. A distance of more than 1000 between any points used here is unlikely.

Memory usage and speed are both important in this case.

If there isn't a clear winner for a data structure to use, feel free to name several candidates.

Thanks for any help!

Sponsor:

#2 ApochPiQ   Moderators   -  Reputation: 15692

Like
1Likes
Like

Posted 29 March 2012 - 07:00 PM

Since your coordinates are well-constrained, you can probably use a spatial hash and a simple hash-map to store the data.

#3 daedalic   Members   -  Reputation: 104

Like
0Likes
Like

Posted 29 March 2012 - 08:12 PM

That's probably a good option. Thanks for the input.

Something I should have mentioned previously is that the points used will form a thin contiguous surface wrapped around 3D terrain and structures.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS