Sign in to follow this  

Space partitioning on spheres?

This topic is 4662 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey! I've got the following problem: I have many points p_n=(x_n,y_n,z_n) on a sphere, i.e. x_n^2+y_n^2+z_n^2 = 1. Now, I want to have a fast scheme that gives me all points within a certain distance around some point p_0 on the sphere. In 2D, one could solve this e.g. by a quad tree. Are there similar data structures on a sphere? Some spherical quad tree?? EDIT: Background: I want to do a space sim and I've got a lot (>20000) of stars (=points on a sphere) and I want to draw only those points that are inside the viewing frustum. So I need a clever data structure that tells me which points are inside and which are outside.

Share this post


Link to post
Share on other sites
I guess you could do something like a quadtree/octree but using polar/spherical coordinates instead of cartesian. Instead of (x, y)-(x, y) regions, you have (rho, theta)-(rho, theta) windows. Add a radius in there to describe a 'box' within the sphere (for full 3D spacefields).

Share this post


Link to post
Share on other sites
Quote:
Original post by superpig
I guess you could do something like a quadtree/octree but using polar/spherical coordinates instead of cartesian. Instead of (x, y)-(x, y) regions, you have (rho, theta)-(rho, theta) windows. Add a radius in there to describe a 'box' within the sphere (for full 3D spacefields).


Hmmm, I'm not sure whether a spherical coordinate quad tree would be a good idea.
The quadtree cells would cluster at the poles. Unless... I could reduce the subdivision level near the poles... That might work.
I guess I'll test it.

Quote:
Original post by janos
a bsp (on your cartesian coordiantes) with the split planes all passing through 0,0,0 will definitely do the job.


I've thought about that also. The only problem I have is: How do I select the split planes properly? I haven't implemented a BSP yet... Can you recommend any resources?

Thanks so far!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You could project onto the faces of a cube and use a 2d solution for each face.

Share this post


Link to post
Share on other sites
I suppose you can consider a certain notion of geodesic polygon (ordered set of vertices, connected by geodesic segments (a geodesic segments belongs to the intesection of the sphere and a plane containing the origin that we will call a geodesic circle or line (meridians are such lines)) along the sphere instead of just standard segments.
Now, know that considering two points on a sphere, there always are two geodesing segments connecting them (one short, and one lon going all around the sphere). We will always consider the shortest.
If you think about is for a bit, the notion of convexity remains on those polygons (using geodesic segments instead of normal segments).
So we basically have somethin similar to 2D convex polygons and 2D bsp, except that the split planes are just splitting geodesic lines that lead to nodes being "geodesic convex polygons"

Now choosing split planes (that match one to one with geodesic lines by considering their intersection with the sphere), can be tricky.
You couls find the largest axis of the current node's content (in this skewed metric), and choose a split geodesic line orthogonal to that, that will ensure proper point cound balancing in its child leaves.

That's how I would do it, but then again, I have not tried it yet.
J

Share this post


Link to post
Share on other sites
Quote:
Original post by Lutz
Quote:
Original post by superpig
I guess you could do something like a quadtree/octree but using polar/spherical coordinates instead of cartesian. Instead of (x, y)-(x, y) regions, you have (rho, theta)-(rho, theta) windows. Add a radius in there to describe a 'box' within the sphere (for full 3D spacefields).


Hmmm, I'm not sure whether a spherical coordinate quad tree would be a good idea.
The quadtree cells would cluster at the poles. Unless... I could reduce the subdivision level near the poles... That might work.
I guess I'll test it.
In general, you want to construct a quadtree such that the objects in each leaf are balanced - not such that the spaces are equal. If you move the splitpoint of each node around such that objects are evenly distributed into each quarter, then the tree should adapt to the layout of your stars - it'll be clustered around the poles if they are clustered around the poles.

Share this post


Link to post
Share on other sites
Quote:
Original post by Lutz
Quote:
Original post by janos
a bsp (on your cartesian coordiantes) with the split planes all passing through 0,0,0 will definitely do the job.


I've thought about that also. The only problem I have is: How do I select the split planes properly? I haven't implemented a BSP yet... Can you recommend any resources?

Thanks so far!

selecting splitplanes wouldnt be that hard. just split each set of stars down the middle, in such a way that its splits along the longest axis.

so first find the centroid of a group of stars, then the star furthers away from that centroid, and then make your plane pass trough these two points and the origin.

Share this post


Link to post
Share on other sites
Eelco:
If I may suggest
you have the sphere center : O
The centroid : C
The furthest point from C : F
the split plane would better be the plane containing OC and the segment CM choosing M such that CM is orthogonal to CF

Share this post


Link to post
Share on other sites
Quote:
Original post by janos
Eelco:
If I may suggest
you have the sphere center : O
The centroid : C
The furthest point from C : F
the split plane would better be the plane containing OC and the segment CM choosing M such that CM is orthogonal to CF

oh, yes, ofcource, thats what i meant to say :). otherwise sets of stars would only keep getting thinner and thinner, which would completely suck.

thanks for noticing that.

Share this post


Link to post
Share on other sites
To note on the quadtree discussion: " A Quadtree For Global Information Storage" by Waldo Tobler and Zitan Chen talks about an equal area quadtree that is easy to implement. it allows that all nodes at the same level cover an equal area on the earth (or any sphere).

Share this post


Link to post
Share on other sites

This topic is 4662 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this