I am glad to be here.
First off, please excuse my almost saddening lack of knowledge. Math (in general) isn't my strong point. I might ask some really basic questions, you have been warned 🙂
The background:
I am building a (so-to-speak) galaxy simulator. I have generated an eliptical galaxy with a large number of "stars"; currently staying at 10.000 but the final number will be around 2 million. They are represented as dots in a 3D space, generated using spherical coordinates which are also transformed and available as cartesian coordinates.
The work:
There are two things I'm working on right now:
-
Let Sphere A with radius 10000 containing 10000 dots with known spherical/cartesian coordinates. Within sphere A let Sphere B with radius R, centered around coordinates X, Y, Z. Find out all dots located both within Sphere A and Sphere B.
This one I solved by using a cube with size 2R, centered at X, Y, Z, then finding all dots located between x-r and x+r, y-r and y+r, z-r and z+r. Then I calculated the distance between the center of the cube and each of the dots. If the distance is greater than R, then they are ignored, leaving only the dots which are located within the sphere inscribed in the cube. I am, however, interested to find whether there is a more elegant solution which wouldn't involve the "cube" middle step. -
Let Sphere A with radius 10000 containing 10000 dots with known spherical/cartesian coordinates. Within sphere A let a dot with known cartesian coordinates X, Y, Z. From this dot we generate a spherical sector B with radius R and cone angle phi (which is between 30 and 90 degrees). Find out all known dots which are located both within sphere A and spherical sector B.
This one I couldn't solve. It is further complicated by the fact that it doesn't necessarily start from the center of sphere A, and its angle relative to sphere A could point pretty much anywhere.
To make an analogy, imagine you're located on Earth and you look at the sky through a telescope. You could point the telescope anywhere. You need to find only stars which are within your field of view, given the fact that you know all star coordinates relative to the center of the galaxy.
How I approached this second problem:
I generated a "virtual" sphere (S1) centered on coordinates X, Y, Z and found all dots located within this sphere using solution outlined at point 1. Then I converted all the cartesian coordinates to "local" coordinates. But then I kind of got stuck… I can't figure a reliable way to limit the volume to only cover the spherical sector.
Please let me know if that makes sense… I'll try to give more details if needed.
Additional information
Thank you for your answer, however…
The way to find the stars in some region is to loop through the stars
and for each one evaluate a formula and do a test to see if it is in
the region or not.
I can't evaluate two million points every time I want to find what's in a region that might find 5 of them. Combined with the fact that such a query needs to finish really fast (under 500 ms worst case scenario, preferably within 100 ms), it becomes obvious that evaluating 2 million entries every time is really out of the question.
My "sphere within a sphere" PL/SQL procedure gives an answer in about 60 ms for "maximum" thresholds of r (which is about 5% of maximum radius) so I'm good there.
As for the spherical sector, I understand most of the formulas presented, however they all gravitate around comparing all those 2 million points, which puts a lot of strain on the queries. Isn't there a way to reduce the number of checks?
The spherical sector (which is a bit more than a cone) will have the following inputs:
– cone axis (theta, phi, r)
– cone angle width (in degrees): 30, 45, 60, 75 or 90 degrees.
That is, the user will enter, for example: Find_stars(10, 10, 1000, 45) which means "Find all stars located in the spherical sector with axis at theta=10, phi=10, length of 1000 and width of 45 degrees", and he will be presented with a list of entries showing all stars located within those bounds.
Best Answer
The way to find the stars in some region is to loop through the stars and for each one evaluate a formula and do a test to see if it is in the region or not. There's not much point in using a cube first; on modern computers multiplications are cheaper than "if" statements!
So the important step is to find the formula for the shapes you are interested in.
The interior of a sphere centred on the origin with radius $r$ satisfies this inequality:
$$x^2+y^2+z^2 \leq r^2$$
This is just Pythagoras's theorem, applied to find the distance from the origin to the point $(x, y, z)$.
If you want the sphere centred elsewhere or with a different radius, you can just substitute for $x$, $y$, $z$:
$$x = x' - x_0$$ $$y = y' - y_0$$ $$z = z' - z_0$$
This gives:
$$(x'-x_0)^2 + (y'-y_0)^2 + (z'-z_0)^2 \leq r^2$$
In this formula, $(x_0, y_0, z_0)$ is the centre of the sphere.
The formula for the interior of a double cone with its point at the origin and its axis along the z-axis and a half-angle of 45 degrees is:
$$x^2 + y^2 \leq z^2$$
Again, this is just Pythagoras's theorem. The left-hand side is the squared distance from $(x, y, z)$ to the point on the z-axis at $(0, 0, z)$.
Note that this gives a double cone; if we want just one of the cones we need in addition something like:
$$z \geq 0$$
You can change the half-angle of the cone to $\phi$ by scaling $z$:
$$x^2 + y^2 \leq (z \tan(\phi))^2$$
If you want to change the axis of the cone, you can do it as follows. First, rewrite the equation as follows:
$$x^2 + y^2 + z^2 \leq z^2 (\tan^2(\phi) + 1)$$
Now the left-hand side looks like the formula for a sphere, and does not depend on the orientation of the cone. The right-hand side does. We need to replace $z$ on the right-hand side with a quantity $d$ that measures the distance along the desired axis of the cone.
Suppose you want the cone to point towards $(u, v, w)$. Then a measure of the distance in that direction is the dot-product:
$$d = \frac{u}{l}x + \frac{v}{l}y + \frac{w}{l}z$$
Where $l$ is the length of the vector $(u, v, w)$, which can be computed (again) using Pythagoras's theorem:
$$l = \sqrt{u^2 + v^2 + w^2}$$
So, putting this all together:
$$(x^2 + y^2 + z^2)(u^2 + v^2 + w^2) \leq (wx + vy + wz)^2 (\tan^2(\phi) + 1)$$ $$ux + vy + wz \geq 0$$
Finally, you can move the point of the cone around using a coordinate transform, just as for the sphere.