Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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!

like image 228
Yoko Avatar asked Sep 03 '25 13:09

Yoko


1 Answers

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.

like image 61
o9000 Avatar answered Sep 05 '25 02:09

o9000