# Space partitioning on spheres?

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

## 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 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 on other sites
a bsp (on your cartesian coordiantes) with the split planes all passing through 0,0,0 will definitely do the job

##### Share on other sites
Quote:
 Original post by superpigI 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 janosa 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 on other sites
You could project onto the faces of a cube and use a 2d solution for each face.

##### 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 on other sites
Quote:
Original post by Lutz
Quote:
 Original post by superpigI 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 on other sites
Quote:
Original post by Lutz
Quote:
 Original post by janosa 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 on other sites
That sounds easy. I'll try that.

Thanks again.

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

1. 1
Rutin
36
2. 2
3. 3
4. 4
5. 5

• 12
• 14
• 9
• 9
• 14
• ### Forum Statistics

• Total Topics
633344
• Total Posts
3011435
• ### Who's Online (See full list)

There are no registered users currently online

×