If the task is to store objects consisting of four numbers (x, y, z, m) and as quickly as possible to search for all objects whose mass to square ratio is greater than a certain number, which structure is best for storage to use? I have so far found kd-tree, r-tree and octree on this topic on Wikipedia, which one is better to use?

  • How many such objects do you have? Square distance to what? Up to some arbitrary point (x0, y0, z0)? And how arbitrary is it? - Anton Shchyrov
  • Objects are planned for about 2 million, the distance to each object. That is, it is necessary to find for each object those that significantly influence it, but you don’t want to carry out 4 * 10 ^ 12 operations - Georgy
  • So miracles do not happen. If objects move and you need to find all distances, then you need to calculate them stupidly. - Anton Shchyrov
  • No, I mean, for example, the interaction force of the Moon and each satellite of Jupiter is not necessary to count, because it is small. And I would like to choose for each object those that influence it strongly, thereby reducing the number of calculations to real-time - George
  • Orbiter somehow works in real time - George

2 answers 2

There is such an option, when you add a new object, you calculate this ratio (judging by the description, this is not a very difficult computational task), and identify the result with the key. Thus, it will be possible to store a key-value pair (the value is this object, depending on how it is represented) in the associative container, the access time is O (log N), in most tasks it is an acceptable search time. About the applicability of trees is not clear, describe the problem in more detail.

  • The problem is that objects move relative to each other - George

Here you have no storage problem, but a non-sick design task. And the whole question is how to optimize these calculations.

One of the optimization options. You need to find all the objects belonging to a certain sphere (the center of the sphere is the current object, the radius is your boundary value of the distance).

Enter this sphere in the cube. Then for the object to belong to the cube, you need to perform a total of 12 linear comparisons (or less, if at least one of them fails). If it turns out that the object belongs to a cube, then already check the more stringent condition for belonging to a sphere.

Further, it is possible to calculate once for each pair the maximum possible force of attraction. And then 90% of the objects simply will not participate in the calculations.