CODEWITHSUNDEEP
c++data-structures3dbinary-search-treecgal
Yoko
Yoko

Reputation: 59

Efficient data structure for storing 3d points

I'm looking for efficient data structures for storing 3d points (x,y,z). The effect of storing in at the points in a data structure should generate a more memory efficient structure and a faster search for a specific set of coordinates. The 3d points is mapping to a specific ID so it should be able to keep track of each set of coordinates I'm looking for any implementation which is available.

x, y, z gives the cartesian coordinates of each node.

id x y z

1 14.566132 34.873772 7.857000

2 16.022520 33.760513 7.047000

3 17.542000 32.604973 6.885001

4 19.163984 32.022469 5.913000

5 20.448090 30.822802 4.860000

6 21.897903 28.881084 3.402000

7 18.461960 30.289471 8.586000

8 19.420759 28.730757 9.558000

The number of coordinates will be huge maybe around 1 000 000.

Thanks in advance!

Upvotes: 4

Views: 5517

Answers (3)

Rajeev Singh
Rajeev Singh

Reputation: 3332

You can use a struct:

struct coordinate
{
   double x;
   double y;
   double z;
} points[1000000];

Upvotes: 0

Aiken Drum
Aiken Drum

Reputation: 593

I'm hearing that the coords you're looking up will be exact matches for those in the structure already. Depending perhaps on your spatial distribution, you could create a hash function that takes the coord and attempts to produce something fairly unique, then just use a standard hash map. Most modern languages provide some kind of hash map implementation, so all you'd need to do is provide those appropriate hash values for your coords.

If you need to look up coords near the test coord, then a balltree or octree or something, but it doesn't sound like that's what you need.

Upvotes: 2

o9000
o9000

Reputation: 1676

a more memory efficient structure

More memory efficient than what? A list? You'd need compression for that.

a faster search for a specific set of coordinates

If you want to find the k closest points from a set of coordinates, a ball tree is a good option.

If you want to search a volume, a quad tree (or octree) works better.

Upvotes: 2

Related Questions