Jump to content

View more

Image of the Day

Inventory ! Va falloir trouver une autre couleur pour le cadre D: #AzTroScreenshot #screenshotsaturday https://t.co/PvxhGL7cOH
IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.


Sign up now

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

4: Adsense

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   

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!

#2 ApochPiQ   Moderators   

22551
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.
Wielder of the Sacred Wands
[Work - ArenaNet] [Epoch Language] [Scribblings]

#3 daedalic   Members   

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.