1

Is there a spatial lookup grid or binning system that works on the surface of a (3D) sphere? I have the requirements that

  • The bins must be uniform (so you can look up in constant time if there exists a point r distance away from any spot on the sphere, given constant r.)†

  • The number of bins must be at most linear with the surface area of the sphere. (Alternatively, increasing the surface resolution of the grid shouldn’t make it grow faster than the area it maps.)

I’ve already considered

  • Spherical coordinates: not good because the cells created are extremely nonuniform making it useless for proximity testing.

  • Cube meshes: Less distortion than spherical coordinates, but still very difficult to determine which cells to search for a given query.

  • 3D voxel binning: Wastes the entire interior volume of the sphere with empty bins that will never be used (as well as the empty bins at the 6 corners of the bounding cube). Space requirements grow with O(n sqrt(n)) with increasing sphere surface area.

  • kd-Trees: perform poorly in 3D and are technically logarithmic complexity, not constant per query.

My best idea for a solution involves using the 3D voxel binning method, but somehow excluding the voxels that the sphere will never intersect. However I have no idea how to determine which voxels to exclude, nor how to calculate an index into such a structure given a query location on the sphere.

† For what it’s worth the points have a minimum spacing so a good grid really would guarantee constant lookup.

taylor swift
  • 2,039
  • 1
  • 15
  • 29
  • Maybe a [hexagonal spherical grid](https://math.stackexchange.com/q/2029958) would help, although I'm not sure of how to perform sub-linear queries in the triangular sub-grids. – meowgoesthedog May 10 '18 at 18:47
  • @meowgoesthedog the hexagonal grid is nonuniform and has many of the same problems as the spherized cube mesh. (And yes I’m aware there is *no* uniform grid that can exist on the surface of the sphere, but I don’t care if the grid is strictly confined to the surface, i.e. cubical voxels that envelop the surface are fine. The points are stored as 3D points with the restriction that `x^2 + y^2 + z^2 == 1`) – taylor swift May 10 '18 at 18:49
  • Hexagonal grids, or their dual namely triangular geodesic grids, sound like the best solution overall, even though the cells are not exactly uniform. I found https://stackoverflow.com/a/3033370/1468366 particularly useful in seeing how different subdivisions relate to one another. – MvG May 10 '18 at 18:56
  • @MvG how to determine which grid cells to search if you want to find things `r` distance away from a query? – taylor swift May 10 '18 at 18:59
  • @taylorswift: Dunno, something like breadth first search of neighbours closer than *r* would probably be easiest. I guess you can come up with more fanciful things, but for constant *r* even most dumb algorithms are O(1). If that isn't enough you need a better way of expressing what it is you need in terms of performance / simplicity. But the fact that I don't have an elegant lookup routine is why this is a comment not an answer. – MvG May 10 '18 at 20:01
  • @MvG so, *dynamically search for the grid lattice points themselves* and then search for the actual points inside the returned grid cells? This still seems like a recursive problem, you can’t do a breadth first search for the lattice points without some way of partitioning them on the sphere surface. – taylor swift May 10 '18 at 20:17

2 Answers2

1

My suggestion would be a variant of the spherical coordinates, such that the polar angle is not sampled uniformly but instead the sine of this angle is sampled uniformly. This way, the element of area sinφ dφ dΘ is kept constant, leading to tiles of the same area (though variable aspect ratio).

At the poles, merge all tiles in a single disk-like polygon.

Another possibility is to project a regular icosahedron onto the sphere and to triangulate the spherical triangles so obtained. This takes a little of spherical trigonometry.

  • can you elaborate? – taylor swift May 10 '18 at 21:41
  • @taylorswift: elaborate what ? –  May 10 '18 at 21:44
  • how could this be used to implement constant time proximity testing? it seems even if the tiles are of even area (and you didn’t give enough details to prove that’s even the case) they wouldn’t be of even dimensions which is the relevant factor in proximity testing – taylor swift May 10 '18 at 22:05
  • @taylorswift: by computing the spherical angles, the tile where a point projects is determined in constant time. The mesh is regular. –  May 11 '18 at 07:58
  • how to determine which cells to search to find points within a distance `r`? is it even a constant number? And because if i understand the grid you’re describing, the cells get taller but narrower the closer to the north or south pole meaning many points could potentially be in the same cell. with a regular lattice, if we know the points are no closer than `u` together you can set the grid spacing to `u/sqrt(3)` to guarantee at most 1 point per cell – taylor swift May 11 '18 at 08:54
  • @taylorswift: are you in space or on the surface of a sphere ? –  May 11 '18 at 09:06
  • the coordinates are 3D but constrained to the surface of the sphere. The regular lattice example was for a 3D lattice enclosing the sphere. – taylor swift May 11 '18 at 09:07
  • You have a wide choice of area-preserving projections (https://en.wikipedia.org/wiki/Map_projection#Equal-area). Not all of them are suitable, but for some the anisotropy is tolerable. My suggestion was Gall-Peters. –  May 11 '18 at 09:15
  • You’re not addressing the part of how to determine which surrounding cells need to be checked to do any sort of neighbor lookup on such a structure. As you said with the anisotropy, I don’t think the answer lies in a spherical projection (as I said in the original question), which is why I suggested it might be some kind of 3D voxel shell. – taylor swift May 11 '18 at 09:41
0

I had a similar problem and used "sparse" 3D voxel binning. Basically, my spatial index is a hash map from (x, y, z) coordinates to bins.

Because I also had a minimum distance constraint on my points, I chose the bin size such that a bin can contain at most one point. This is accomplished if the edge of the (cubic) bins is at most d / sqrt(3), where d is the minimum separation of two points on the sphere. The advantage is that you can represent a full bin as a single point, and an empty bin can just be absent from the hash map.

My only query was for points within a radius d (the same d), which then requires scanning the surrounding 125 bins (a 5×5×5 cube). You could technically leave off the 8 corners to get this down to 117, but I didn't bother.

An alternative for the bin size is to optimize it for queries rather than storage size and simplicity, and choose it such that you always have to scan at most 27 bins (a 3×3×3 cube). That would require a bin edge length of d. I think (but haven't thought hard about it) that a bin could contain up to 4 points in that case. You could represent these with a fixed-size array to save one pointer indirection.

In either case, the memory usage of your spatial index will be O(n) for n points, so it doesn't get any better than that.

Thomas
  • 174,939
  • 50
  • 355
  • 478