2

I'm having trouble coming up with a suitable way to navigate through a set of star coordinates in the Equatorial Coordinate System. My goal is to display those which are within a given range of horizontal coordinates. The display is square with about 10 degrees "length" in each direction.

I thought about binning the stars in clusters of sufficiently large (but small enough) equal right ascension and declination, so I can display one or more bins at a time on the display (one if the display is showing the center of a bin, four if the display is showing the point connecting adjacent bins). The binning is simple, but how can I navigate between bins in order to select the right ones for the display? This appears to be a problem around the poles, where many bins touch each other.

The application is being written in C++ and will have to run on a microcontroller, so resources (memory and CPU time) are very limited. Coordinates can be read from an SD card and the format may be custom, so if the algorithm imposes any constraints on that, that's fine.

Additional thoughts:

  • The tiles that divide the celestial sphere into bins also have constant (not necessarily equal) size and are generated together with the lookup structure.
  • insertion time is not important. The structure used for finding the right bin does not change during runtime and can be loaded from the SD card to RAM at startup.
  • The word I was missing was "tiles". Gamedev SX has a [tiles] tag and there are some questions and answers there; I'll have a look at those.

And another one:

Digging through the Gamedev [tiles] tag didn't reveal a lot that I could use for spherical coordinates. It also looks like I'm not familiar enough with the underlying theory to come up with a suitable solution. Another idea I had was to add information about all adjacent bins to each bin, so that when the display's view is moved I can just scan through all neighbours to find the next one that the display is "centered" on. I think this is similar to a graph, but decentralized.

Improve this question
8
  • A 2D-Tree might be useful. A “bin” would correspond to a leaf node of the tree. To find all objects inside a certain circle, merge all bins that overlap with this circle, then do an exact filter through the remaining objects.
    – amon
    Commented Jan 28, 2014 at 23:25
  • Thanks for that suggestion, but I'm not sure how such a tree might help me at the boundary between a bin that ends at 180° and one that starts at -180° (right ascension), and those at the poles. I could probably create a single bin around each pole, which then wouldn't be a major problem any more.
    – Christoph
    Commented Jan 28, 2014 at 23:47
  • That doesn't matter. Actually, I misinterpreted K-D-Trees in my earlier comment and it doesn't have any bins – data is stored in each node. Finding the objects in a certain area is actually easier, as you just fetch the appropriate subtree, pruning irrelevant branches as you go. The advantage of these trees is their concept of “neighborhood”. Spherical coordinates do have their difficulties here, but you can work around them by applying the idea behind K-D-Trees to create a more complex graph which then solves your problem.
    – amon
    Commented Jan 28, 2014 at 23:55
  • 1
    How about a VP-Tree? The example on that page is about finding the city closest to a given location on earth - the same as I do.
    – Christoph
    Commented Jan 31, 2014 at 10:47
  • 1
    I've tried the city search examples with different distance functions. The first thing I discovered was that the example code indeed uses euclidean distance, which is not appropriate on a sphere, but serves the purpose of demonstrating the VP-Tree. I then changed the distance function to the spherical law of cosines and then to the haversine formula, which gave slightly different (compared to euclidean) but sensible results.
    – Christoph
    Commented Jan 31, 2014 at 13:48

1 Answer 1

Reset to default
2

Map the stars onto an Isocahedron(https://en.wikipedia.org/wiki/Icosahedron) and if you need more fine binning, then just subdivide the triangles.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.