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.
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.