Discussion What is the most efficient way to crowdsource the 3D system coordinates

You could instead use: new = trunc((old + 1/64) * 32) /32 and you'll also get the correct rounding (assuming we're talking normal 'half-rounding' here). [...]
So, yeah, either way works, assuming you have enough precision.


(x + 1/64) * 32 = 32x + 32/64 = 32x + 1/2

By multiplying first with 32, I only need one fraction (1/2) which is less likely to fail than 1/64.
 
Last edited:

Harbinger

Volunteer Moderator
I concur, 0.5 works perfectly, 1/64 produces failures which are visible when you convert to Sol centric.

I've updated my files:

Here you go:

Elite: Dangerous Beta 3 Systems - CSV (Galaxy Centric) [http://pastebin.com/zi7gSn7W]
Elite: Dangerous Beta 3 Systems - TradeDangerous (Galaxy Centric) [http://pastebin.com/LmnLVdLe]
Elite: Dangerous Beta 3 Systems - RedWizzard (Galaxy Centric) [http://pastebin.com/Q4NZaBqD]


Elite: Dangerous Beta 3 Systems - CSV (Sol Centric) [http://pastebin.com/FRitZ1Kz]
Elite: Dangerous Beta 3 Systems - TradeDangerous (Sol Centric) [http://pastebin.com/JeMUZ1Er]
Elite: Dangerous Beta 3 Systems - RedWizzard (Sol Centric) [http://pastebin.com/HwjuDrJt]

I've generated both Galaxy centric and Sol centric offset by (-49985, -40985, -24105)

@Athan: Any chance you can snip (or edit) your quote from your previous post as the first link was uploaded anonymously and points to a paste I can't edit.
 
@Harbinger:

You forgot to add Sol to the list :)

Sol (Galaxy Centric): (49985, 40985, 24105)
Sol (Sol Centric): (0, 0, 0)

And I don't think it's Galaxy Centric, the offset would need to be Sagittarius A*.
 
Last edited:

Harbinger

Volunteer Moderator
New trilateration test using these systems (taken from my Sol centric list):

  • Ammapa (-115.25, 58.125, -43.28125)
  • Wanggu (-132.71875, 30.96875, -39.59375)
  • Piran (-124.40625, 39.5, -13.96875)
  • Yakan (-140.84375, 45.9375, -12.53125)
  • Suraci (-102.53125, 9.34375, -51.625)
  • Gera (-88.8125, 11.6875, -33.59375)
  • Arin (1.0625, 3.875, -9)
  • Pollux (6.71875, 13.71875, -30.125)
  • Amun (51.5625, 32.1875, -27.125)

Results:
Code:
[
    {
        "name": "Ross 640",
        "calculated": true,
        "contributor": "Harbinger",
        "contributed": "2014-10-31T01:10:16.000Z",
        "distances": [
            {
                "system": "Ammapa",
                "distance": 106.69
            },
            {
                "system": "Wanggu",
                "distance": 116.84
            },
            {
                "system": "Piran",
                "distance": 98.48
            },
            {
                "system": "Yakan",
                "distance": 114.12
            },
            {
                "system": "Suraci",
                "distance": 103.26
            },
            {
                "system": "Gera",
                "distance": 81.07
            },
            {
                "system": "Arin",
                "distance": 53.19
            },
            {
                "system": "Pollux",
                "distance": 65.88
            },
            {
                "system": "Amun",
                "distance": 95.19
            }
        ],
        "x": -31.6875,
        "y": 35.125,
        "z": 18.9375,
        "region": "Beta3"
    }
]

Original findings from Beta 2 mapping (Taken from RedWizzard's current systems.json):
Code:
{"name": "Ross 640", "x": -31.6875, "y": 35.125, "z": 18.9375, "contributor": "FD", "region": "Beta2", "contributed": "2014-10-21T17:16:31.000Z"},

So I can confirm Ross 640 is indeed still there and what's more it's at the same coordinates as it was previously.

- - - - - Additional Content Posted / Auto Merge - - - - -

@Harbinger:

You forgot to add Sol to the list :)

Sol (Galaxy Centric): (49985, 40985, 24105)
Sol (Sol Centric): (0, 0, 0)

And I don't think it's Galaxy Centric, the offset would need to be Sagittarius A*.

It was generated from Michael Brookes' list. Sol and the other stars that were outside the pill were not on it, hence they were not in the output.
 
Last edited:
Jata and Chara are rather a long way from the main pill; it's extremely unlikely that we'll be able to visit them, but we can use them as reliable external references.

Someone at FD has made a mistake. There are currently two systems called Chara in the map. One at the co-ordinates MB provided, -130.468750,-21.687500,-124.781250, and another where we know and love it around -4.80, 26.41, -4.99 (my beta 1 eyeballed co-ords).

There's a Jata at around -67.78125, 58.3125, -28.8125 (from systems.json), and indeed another out around -28.375, -112.5, 98.4375 from the b3 data.

I'd wonder if they've managed to re-use any other system names.
 
(x + 1/64) * 32 = 32x + 32/64 = 32x + 1/2

By multiplying first with 32, I only need one fraction (1/2) which is less likely to fail than 1/64.

I think either way is as likely to fail once you're using floating point with some limited precision; either you trip up on needing another binary digit after the point, or needing more before the point due to the multiplication. The way to truly avoid any issues would be to use a large enough integer type, multiply by 320, add 5, truncate (to nearest 10), then divide by 320. Of course then you may as well just do custom truncation at the 1/64 level....

But if you're working in double-precision anyway then either method works (as you demonstrated, they're equivalent) because this whole 1/32 thing is due to single precision's format (24 bits of significand, 8 bits of exponent) resulting in only 5 bits after the binary point.
 
Last edited:

Harbinger

Volunteer Moderator
Here is the current systems.json I'm working with:

https://drive.google.com/file/d/0B_GOSqs6Iq2McTc1Yml6TExkOGM/view?usp=sharing

I have:

  • Reverted the region and submission dates back to the original values in RedWizzard's last systems.json (where applicable)
  • Readded the "Outside the Pill" systems
  • Added Ross 640 as it's now confirmed as also being in Beta 3
  • Added a few stations along with their distances (LS) to the system entry point. See i Bootis, Eranin, Styx, Asellus Primus etc. for more on this.
  • Checked a few Beta 2 systems.

I started working on space stations whilst we were waiting on an updated systems list. ;)
 
Last edited:
As I pointed out earlier, single-precision retains 1/32 precision all the way up to 262,000 or so. The positions we're dealing with now are in the 50,000 range, so there's plenty of headroom.

Raw position *differences* using Cartesian coordinates will have exactly the same precision as the source positions, unless the two systems are wildly opposite sides of the origin. I don't think this will be a practical problem even for systems on opposite edges of the galactic disc.

Accurately calculating the *distance* from those coordinate differences requires that the squared distance can be stored to 1/1024 precision, which stops being true for single-precision at about 90 ly. This is *regardless* of where, relative to the global origin, the two systems are. However, the errors don't become intolerable (as long as they are accounted for) for determining positions until the systems are about a thousand ly apart. Distances can also still be calculated accurately using double-precision.

As also pointed out elsewhere, 2dp is entirely sufficient in itself to determine 1/32 ly positions. However, the geometry of the reference systems relative to the target is now far more important than it was when we could rely on 3dp distances; ideally three of the references would be perpendicular to each other relative to the target, with the fourth reference being used for disambiguation. We can no longer determine the position of stars far outside the bubble to sufficient precision to allow using them as references, but we should still be able to fill in the gaps within the bubble reasonably well. I'll try to have a think about how to reliably identify good additional references to prompt surveyors with, using that prependicularity heuristic.
 
I've spent a few hours over the past few weekends working on this tool:

<snip>

This takes the data from B2 and applies it to the map.

It still is a far way from being functional...

But there may be some convergence that can be done, where people can log the system they are in and then have some way of calculating, exporting, sharing the data.

I'm not sure exactly where I'm going with this tool, and it was partly to prove I could make it...

But I'm willing to put in some time and effort to make this work as a combination routing and mapping tool.

Heck, even for one person with a local database of new stars it might prove useful.

This is a wip, but it's compatible with modern tablets, phones, desktops, web, etc.

The prototype requires the Unity 4.6 BETA webplayer, which will be installed if you grab a copy of the Unity 4.6 beta editor (free) at: http://unity3d.com/unity/beta/4.6

The map can be found at https://dl.dropboxusercontent.com/u/9597058/EDGalaxyMap/EDGalaxyMap.html

Nice! I have also been working on something with unity3d...but nothing to show really yet. (basically trying to make some sort of logbook app)
 
Here you go:

Elite: Dangerous Beta 3 Systems - CSV (Galaxy Centric) [http://pastebin.com/zi7gSn7W]
Elite: Dangerous Beta 3 Systems - TradeDangerous (Galaxy Centric) [http://pastebin.com/LmnLVdLe]
Elite: Dangerous Beta 3 Systems - RedWizzard (Galaxy Centric) [http://pastebin.com/Q4NZaBqD]


Elite: Dangerous Beta 3 Systems - CSV (Sol Centric) [http://pastebin.com/FRitZ1Kz]
Elite: Dangerous Beta 3 Systems - TradeDangerous (Sol Centric) [http://pastebin.com/JeMUZ1Er]
Elite: Dangerous Beta 3 Systems - RedWizzard (Sol Centric) [http://pastebin.com/HwjuDrJt]

I've generated both Galaxy centric and Sol centric offset by (-49985, -40985, -24105)

The galaxy centric coords don't appear to match the dump.

e.g. mizar:
From the dump: 49950.78 41053.84 24090.91
From your systems.json: 49950.75, 41053.8125, 24090.90625

The correct coordinates should be 49950.78125 41053.84375 24090.90625
 
Victim to british humor? Maybe data released to fry some brains? I'm a advocate of good enough works for me. If its off 0.0125 I can work with that. Thanks for the coords, think I'll continue the good enough coords and leave the hard work to someone else :D
 
Someone at FD has made a mistake. There are currently two systems called Chara in the map. One at the co-ordinates MB provided, -130.468750,-21.687500,-124.781250, and another where we know and love it around -4.80, 26.41, -4.99 (my beta 1 eyeballed co-ords).

I've posted a list in #978 of new positions with old names (it's inside the spoiler). I just thought they moved position.

The first nameless entry in the list from FD is actually the old Chara: FDEmpyt1 (-4.84375, 26.65625, -4.78125)
 
Accurately calculating the *distance* from those coordinate differences requires that the squared distance can be stored to 1/1024 precision, which stops being true for single-precision at about 90 ly. This is *regardless* of where, relative to the global origin, the two systems are. However, the errors don't become intolerable (as long as they are accounted for) for determining positions until the systems are about a thousand ly apart. Distances can also still be calculated accurately using double-precision.

Or you could just use 64-bit integer arithmetic to calculate the squared distances. I do just that and compare them to the minimum and maximum possible value for any on-screen distance.

As also pointed out elsewhere, 2dp is entirely sufficient in itself to determine 1/32 ly positions. However, the geometry of the reference systems relative to the target is now far more important than it was when we could rely on 3dp distances; ideally three of the references would be perpendicular to each other relative to the target, with the fourth reference being used for disambiguation. We can no longer determine the position of stars far outside the bubble to sufficient precision to allow using them as references, but we should still be able to fill in the gaps within the bubble reasonably well. I'll try to have a think about how to reliably identify good additional references to prompt surveyors with, using that prependicularity heuristic.

I can't really explain the reasons, but my test on the old beta 2 systems.json with coords truncated to 2dp worked well (using the integer precision method), there is always a single most likely candidate for all systems within the bubble. Some of them have many reference distances, so it may work because there is a good reference as you have suggested. I just can't tell because my finder works a bit like JesusFreke's, checking all possible 3D coordinates, and recording the ones valid for at least two reference systems. (In the first version I recorded all coords valid for at least one reference system. This was completely pointless and required at least 3 orders of magniture more memory to store.)
 
Another random idea to throw out there:

Once we have an approximate location for a star (i.e. there are multiple grid points in the candidate region), I think it should be possible to search through the set of known stars to find a "decider" star that will help rule out some of the candidate locations. So it would end up being an iterative process - you enter 4 distances in order to get an approximate location, and then the tool tells you which star to get the distance to next, in order to rule out as many candidates as possible. And continue like that until all candidates but 1 are ruled out.

e.g. if you have 2 candidate locations that differ only by the x coordinate, then you would want to find a star that's near the line that connects the 2 candidate points. And furthermore, you could calculate the distance from that reference star to each candidate location, and see if the rounded distance would be different to each candidate, so that knowing that distance would be able to rule out one of the candidates.

I wrote a little proof-of-concept utility this evening to try out this idea, along with a couple of related ideas, and it ended up working surprisingly well.


Below is a session log with some added annotations to help explain what it's doing. I manually chose the first 3 systems so that they would be poor references (somewhat far away, and all in the same general direction), to see how well it worked in that case.

New star name? Ross 690

Distance to Jula Oh? 159.78
Distance to Igororai? 156.88
Distance to Markanomovoy? 144.21
Evaluated 2202 locations

----- After exhaustively searching around the candidate regions resulting from trilateration, it evaluted a total of 2202 locations, and found 7 matching locations. So it then searched through all the known stars and determined that Eme was the best choice for the next distance, because knowing that distance would eliminate the most candidates (in this case, each of the 7 matching locations had a different rounded "display" distance to eme, so it was guaranteed to eliminate all but 1 candidate).

Found 7 candidate locations
Enter distance for Eme: 70.72
Evaluated 550 locations
Found single correct location: [ 49956.59375 41032.8125 24083.03125]

------- After taking the distance to Eme into account, it was able to find a single matching location. Next, it evaluates the data again, by removing each connection in turn, and re-evaluating. This is to ensure there is enough redundancy in the data to detect if any single distance is incorrect.

Testing with connections: Eme, Markanomovoy, Igororai
Evaluated 730 locations
Found 2 candidate locations

------ In this case, after removing the Jula Oh connection, it wasn't able to find a single location, so it does the "search through all the known stars to find the next best reference" thing, and determines that knowing the distance to Pan will eliminate one of the 2 candidate locations

Enter distance for Pan: 62.49
Evaluated 104 locations
Found single correct location: [ 49956.59375 41032.8125 24083.03125]

------- Yep, once the distance to Pan was taken into account, it was able to narrow it down to a single location.

----- Next, It removes Igororai and tries again with the remaining connections, and then continues with the remaining combinations of connections.

Testing with connections: Jula Oh, Pan, Markanomovoy, Eme
Evaluated 116 locations
Found single correct location: [ 49956.59375 41032.8125 24083.03125]

Testing with connections: Jula Oh, Pan, Eme, Igororai
Evaluated 112 locations
Found single correct location: [ 49956.59375 41032.8125 24083.03125]

Testing with connections: Jula Oh, Pan, Markanomovoy, Igororai
Evaluated 260 locations
Found single correct location: [ 49956.59375 41032.8125 24083.03125]

--- It was able to determine the correct location in each case, with no additional data. So we know we have n+1 redundancy now

Ross 690 location: [ 49956.59375 41032.8125 24083.03125]
Ross 690, Eme, 70.720000
Ross 690, Igororai, 156.880000
Ross 690, Jula Oh, 159.780000
Ross 690, Markanomovoy, 144.210000
Ross 690, Pan, 62.490000

I found out that sometimes you actually only need 3 distances to determine a coordinate, although that's without any redundancy of course. The trick is that you explore the candidate region around both of the points that result from trilateration using 3 points. And in some cases, you still only end up with a single grid-aligned matching coordinate, even after looking in the candidate region around both points.


I'll try to get it cleaned up and released, although I might not be able to get it out until after the weekend. Maybe my description will at least spark some ideas that others can use :)

On a related note, I noticed that there is a port of lmfit to java script. Which might be useful if someone is wanting to port some of my logic to a web form or to some of the javascript-based tools. I have no desire to do anything with javascript though :p
 
Last edited:
Back
Top Bottom