Release EDSM - Elite Dangerous Star Map

AnthorNet

Volunteer Moderator
Yes, an enddatetime would work. That's the solution I thought up too. But you can probably make it a low priority as I shouldn't need to do this sort of full request again. Once my code has a cached copy it will just request incremental data.
The parameter was added into the APIs. You can look at the docs.

Be aware that the startdatetime is inclusive whereas the enddatetime is exclusive.
So if you batch, the next startdatetime should be equal to the precedent enddatetime.

Apart from that we are moving some calls to memcached so APIs and other parts of the FrontEnd should work faster.
 
Hi do you have any example?

And where did you enter your distances?

EDIT: Here the latest distances we have received from you: http://www.edsm.net/show-system/index/id/68683/name/Iorady+QJ-I+d9-2
And we have the coordinates calculated
Sorry for the slow reply - I stupidly did not note down the systems, but will try a few tonight and make notes. Interesting, as the systems don't show up in "black" on EDDiscovery.

Just seemed a bit strange as it seemed to be working really well about 3 weeks ago, and now that I am actually closer to Sol, I am having trouble.

I tried to use the in-EDDiscover trilateration, and also the web site (linked from "add new star" drop down).

I've used over 20 distances in each case, but will make accurate counts and detailed notes with my attempts and post them tomorrow. Perhaps it's an EDDiscovery issue, in this case, though...

Z...

Edit - just tried to enter Nuwie AL-R c7-2 on the EDSM link from original post - I think I broke the page (went to a white screen after submitting ~10 distances).
 
Last edited:

AnthorNet

Volunteer Moderator
Anyone know if EDSM is down? Failing to submit distances :-(
That might have been my fault ^^
Should be up and working!


@Zeeman: The website linked on "Add new star dropdown" is a little obsolete and the API was not working anymore. I put a new redirection to our new API and it should work.
I also merged your new account with the old (Guest) one, and all your distances should have been attributed to you.
 
Last edited:
That might have been my fault ^^
Should be up and working!


@Zeeman: The website linked on "Add new star dropdown" is a little obsolete and the API was not working anymore. I put a new redirection to our new API and it should work.
I also merged your new account with the old (Guest) one, and all your distances should have been attributed to you.
Oh nice - that's awesome, thank you very much!

Z...
 

AnthorNet

Volunteer Moderator
Seems down, have sent an email to Inhumierer but I can't really say what happened!

EDIT: The main server database is still online, so I moved the DNS to another server so it can work in the meantime.
Expect it to be online pretty soon. Once the main server is back we will switch back.
 
Last edited:
While eddiscovery can't seem to be able to submit right now, is it safe to submit via the website? It seems to be working, I just want to make sure the data won't be lost that I'm submitting right now.

Should my web and eddiscovery submissions eventually merge, or do I have to explicitly request it (in which case... my cmdr name: Backer #469732, and do future entries stay merged?)

As a technically minded person, I'm curious about the details/inner workings:

Questions: What format are the distances stored in? (single precision, double, decimal/numeric) and what format are the calculations done in? (I'd also like to ask this question of Frontier).

Is there an API to get all systems (and/or distances) submitted by a particular CMDR? (perhaps along with the ability to restrict to only systems with insufficient distances, or other criteria)? (I was trying to find all the systems that I've done, but had to do a date-restricted query and then search for my name).

On the website, when I tell it what system I'm in, and it then:

asks for "we need more distances": Is it picking some additional systems (ones with only a few distances?), and then calculating what it thinks the distances to those systems should be and asking me to confirm (or dispute)? When additional systems are added to a system, does that allow its position to be more precisely determined? (It seems with enough relationships it should be possible to more precisely determine (beyond 1/100 of an LY that ED shows in the galaxy map) where a system is; is it doing this? Hm, I guess so ("It is located at -103.375 / -138.3125 / -339.8125"), but this ties into my next questions.

How many distances does a system need before its considered correct?

Are distances bidirectional (If I say Maia is X from Polaris, I'm also saying Polaris is X from Maia). Do both systems get adjusted if necessary (and what then happens to systems that have distances to those?, when a system "moves" how is this propagated throughout the database?) I presume (for efficiency/speed reasons) that systems are stored with their coordinates, and not just as distances from other systems, but then these coordinates have to be updated when necessary.

Asks for "We need more distances to calculate coordinates", Its picking systems with too few distances currently, and asking me to add a distance from where I am to it (and it to where I am)?

I can only "hide distance" for values I've provided; and this means it will no longer consider that distance when doing calculations?

Also, curious what method(s) are being used to calculate the coordinates of systems, and how are minor discrepancies resolved (such as might arise if using binary floating formats).

On at least two submissions now, Polaris is 1/100 of an LY off (according to eddiscovery), but I submitted it anyway with the value that the galaxy map told me (perhaps polaris is right in the middle of where the galaxy map says it was, and where it was calculated to be (at least by eddiscovery))? One of the systems with the discrepancy is Wredguia WK-X b28-0. Unfortunately, I didn't note the other one, but when Polaris was "off" for a second time, I started to get suspicious.
 

RedWizzard

Volunteer Moderator
As a technically minded person, I'm curious about the details/inner workings:
I can't speak for EDSM's specifics, but I can answer some of your questions...

Questions: What format are the distances stored in? (single precision, double, decimal/numeric) and what format are the calculations done in? (I'd also like to ask this question of Frontier).
Coordinates in ED are multiples of 1/32 Ly, i.e. 1.5 and 1.53125 are valid values but 1.5307 is not. Calculations in ED are done using single precision floating point. We know this because there are cases where rounding results in different values if double precision or decimal/numeric calculations are used. As far as storing the values, it doesn't really matter provided the correct rounding is applied when performing the calculations (this is a feature of the IEEE formats). In fact you can even perform the calculations in double precision provided you round to single precision after each operation. You can find more details in the original thread: https://forums.frontier.co.uk/showthread.php?t=43362

When additional systems are added to a system, does that allow its position to be more precisely determined? (It seems with enough relationships it should be possible to more precisely determine (beyond 1/100 of an LY that ED shows in the galaxy map) where a system is; is it doing this? Hm, I guess so ("It is located at -103.375 / -138.3125 / -339.8125"), but this ties into my next questions.

How many distances does a system need before its considered correct?
Additional distances don't help with precision; the algorithm either produces a single answer the works or it doesn't. The minimum number of distances required to produce an answer is generally 4, though because of the 1/32 Ly resolution it can sometimes be done with 3. Three distances typically results in two sets of coordinates and a fourth distance is required to determine which one is correct, but if one of those answers falls on the 1/32 Ly grid and the other doesn't then we know which candidate point is correct. However if one or more of those distances is incorrect then the algorithm might produce a valid-looking but incorrect result. This is where additional distances help; if they are consistent with the answer then our confidence in the correctness of that answer increases.

Also, curious what method(s) are being used to calculate the coordinates of systems, and how are minor discrepancies resolved (such as might arise if using binary floating formats).
The basic method is called trilateration. If we had precise distances from ED, and people didn't make mistakes entering them, then we could just use those equations with 4 distances and get the right answer every time. Unfortunately ED only gives us distances to two decimal places and people make mistakes often. The lack of precision from ED means that instead of three distances specifying two points exactly they instead specify two small volumes of space. It's possible to precisely calculate those volumes and determine which 1/32 Ly grid points are inside, but it's complex and not generally worthwhile. Instead what my implementation does is to search valid points on the 1/32 Ly grid around the coordinates calculated assuming the distances are exact. For each candidate I check each of the 8 grid points around the candidate (can check further out but it's almost never worthwhile). Checking is done by calculating the distances from the candidate to each supplied system using single precision and rounding to 2 decimal places and comparing the resulting distance to the supplied distance. The candidate with the most matching distances is considered correct. My data entry page requires that the leading candidate matches at least 2 more distance than any other candidate.

To handle user errors my implementation doesn't assume any distances are correct. So instead of using say the first three supplied distances to calculate two candidates, instead I generate candidate coordinates from each combination of three distances chosen from all those supplied. This can result in large numbers of candidates if there are a lot of distances but it makes the system very resistant to bad data. The data entry page highlights distances which aren't consistent with the leading candidate so those distances can be corrected before submission.

On at least two submissions now, Polaris is 1/100 of an LY off (according to eddiscovery), but I submitted it anyway with the value that the galaxy map told me (perhaps polaris is right in the middle of where the galaxy map says it was, and where it was calculated to be (at least by eddiscovery))? One of the systems with the discrepancy is Wredguia WK-X b28-0. Unfortunately, I didn't note the other one, but when Polaris was "off" for a second time, I started to get suspicious.
Polaris is definitely correctly located at (-322.6875, 194.59375, -212.4375). Using the first 25 distances my algorithm has that location matching 17 distances more than the next best choice.

My code and EDSM both calculate the distance from Wredguia WK-X b28-0 to Polaris as 323.41, which is what was submitted. I suspect you've found a bug in how EDDiscovery calculates the distance (will be rounding slightly differently to ED).
 
Last edited:

RedWizzard

Volunteer Moderator
Seems down, have sent an email to Inhumierer but I can't really say what happened!

EDIT: The main server database is still online, so I moved the DNS to another server so it can work in the meantime.
Expect it to be online pretty soon. Once the main server is back we will switch back.
I'm getting "500 internal server errors" on a lot of api calls, even for (what should be) pretty small resultsets, e.g. http://www.edsm.net/api-v1/distances?submitted=1&startdatetime=2015-09-09+12:21:33

I can successfully get about one day worth of distance data and two days worth of systems.
 
Last edited:
www.edsm.net seems to be down. Or is it just me?
Yea sorry folks, was my fault. Tnx to AnthorNet, he brought up a testing machine so we had a backup during the downtime. I assume he will merge the data into the production DB, since we also have few new registered users...
Anyone who had some issues may visit me and get a ton of Palladium ;-)
 

AnthorNet

Volunteer Moderator
I'm getting "500 internal server errors" on a lot of api calls, even for (what should be) pretty small resultsets, e.g. http://www.edsm.net/api-v1/distances?submitted=1&startdatetime=2015-09-09+12:21:33

I can successfully get about one day worth of distance data and two days worth of systems.
Main server is back, so everything should be back to normal as long as the DNS are up to date which should now be the case.
No problem with database as we have use the main database who was not offline.

As we used an external database requests could take a little longer than expected and the secondary server might not have been configured like the main server so some calls might get a 500, I'm sorry about that.


@xxiii; i'll answer later ^^
 

AnthorNet

Volunteer Moderator
Hi xxiii,
Lots of questions! I'll try to answer them the best I can.

While eddiscovery can't seem to be able to submit right now, is it safe to submit via the website? It seems to be working, I just want to make sure the data won't be lost that I'm submitting right now.
We had an issue over the week-end but as long as the frontedn is working and your are using it, no problem all things are saved!

Should my web and eddiscovery submissions eventually merge, or do I have to explicitly request it (in which case... my cmdr name: Backer #469732, and do future entries stay merged?)
We can merge old guest accounts with your EDSM account, I have done it for you already. As long as your CMDR name stays the same, we should be able to merge them.

What format are the distances stored in? (single precision, double, decimal/numeric) and what format are the calculations done in? (I'd also like to ask this question of Frontier).
All our distances are stored as INT, we multiply the submitted one by 100 so calculus are easier and faster.

Is there an API to get all systems (and/or distances) submitted by a particular CMDR? (perhaps along with the ability to restrict to only systems with insufficient distances, or other criteria)? (I was trying to find all the systems that I've done, but had to do a date-restricted query and then search for my name).
Not for now, but that can be something we add on our TODOLIST.

asks for "we need more distances": Is it picking some additional systems (ones with only a few distances?), and then calculating what it thinks the distances to those systems should be and asking me to confirm (or dispute)? When additional systems are added to a system, does that allow its position to be more precisely determined? (It seems with enough relationships it should be possible to more precisely determine (beyond 1/100 of an LY that ED shows in the galaxy map) where a system is; is it doing this? Hm, I guess so ("It is located at -103.375 / -138.3125 / -339.8125"), but this ties into my next questions.
Positions are not more precise. We start calculating with 5 distances, it works or not ;)
The suspicious tabs works only when we have the coordinates, it is mainly used to help us see what distances are wrong by checking them in game.

How many distances does a system need before its considered correct?
Systems are considered correct as soon as their coordinates are calculated. We may ask more distances to verify when we have less than 8 distances.
That is mainly to help us when we double checks the coordinates, we need a little more to process bad distances. But it does not change the coordinates.

Are distances bidirectional (If I say Maia is X from Polaris, I'm also saying Polaris is X from Maia). Do both systems get adjusted if necessary (and what then happens to systems that have distances to those?, when a system "moves" how is this propagated throughout the database?) I presume (for efficiency/speed reasons) that systems are stored with their coordinates, and not just as distances from other systems, but then these coordinates have to be updated when necessary.
Yes they are bidirectional. We only store them once, with the system with lower ID as ref_system1. But they are used for both system. Once calculated, coordinates are stored so we don't have to check each time.
If the lists contains systems with no coordinates we try to calculate them on the fly.

We have internal tools that check all systems to compare every coordinates with the stored ones so it helps us catching bad coordinates/distances sometimes, but so far all coordinates are correct.
We may have some coordinates we cannot recalculate because some bad distances where submitted after the first calculation.
Some we cannot calculate because they come from EDSC, most of the time, we cannot calculate them because we found alternative possibilities.
On all the database, they are only 360 of these cases over 38000 calculated coordinates, so it does not happen much ^^

Asks for "We need more distances to calculate coordinates", Its picking systems with too few distances currently, and asking me to add a distance from where I am to it (and it to where I am)?
Yes from where you are.

I can only "hide distance" for values I've provided; and this means it will no longer consider that distance when doing calculations?
As we import data from other third party tools, sometimes bad distances came back in the system!
Hiding them prevent that behavior, if we delete them, they would come back eventually over time. They are not used in calculation.

Also, curious what method(s) are being used to calculate the coordinates of systems, and how are minor discrepancies resolved (such as might arise if using binary floating formats).
As pointed out by RedWizzard, we use Trilateration. We should put something to explains better exactly how we handle cases ^^

On at least two submissions now, Polaris is 1/100 of an LY off (according to eddiscovery), but I submitted it anyway with the value that the galaxy map told me (perhaps polaris is right in the middle of where the galaxy map says it was, and where it was calculated to be (at least by eddiscovery))? One of the systems with the discrepancy is Wredguia WK-X b28-0. Unfortunately, I didn't note the other one, but when Polaris was "off" for a second time, I started to get suspicious.
As you can see here (Polaris) we have no rounding problems on Polaris distances.
You can have a better look on how we calculate the coordinates here: http://www.edsm.net/system/check-coordinates/id/25526

1/100 Ly off can happen but not much, we have try to handle them but results over the whole database where not good so we do not handle them for now ^^
They are shown in orange on distances listing.
The only thing we do for now, is that if we have more distances we can remove one distance from the calculation if we think it's wrong. Sometimes it helps the systems to find the coordinates.
 
Ninja'd ;)

method(s) are being used to calculate the coordinates of systems
About 10 or 11 months ago I was thinking about this, and tried a different approach.
One distance to a known system makes sure you are on a bowl or sphere around this system, the radius of the sphere is known.

If you know two distances, those two bowls cut in a circle.

A third bowl cuts the cirle at two points, and the fourth distance shows which of those two points is correct.

To put this in maths, 4 bowl equations for 3D coordinate system are set up, and the unknown factors get eliminated, and there drop out 3 coordinates.

As far as I understood, this is not quite the same as trilateration, but very similar. Anyway, it is quite fast and gives the exact same results as RWs, Finwens or EDSCs trilaterations. Most of the CPU time is needed to get rid of CMDRs & FD rounding errors, so at the end it doesn't matter which tool or program you take, the result is the same.
 

RedWizzard

Volunteer Moderator
Main server is back, so everything should be back to normal as long as the DNS are up to date which should now be the case.
No problem with database as we have use the main database who was not offline.

As we used an external database requests could take a little longer than expected and the secondary server might not have been configured like the main server so some calls might get a 500, I'm sorry about that.
Thanks guys.
 
I can't speak for EDSM's specifics, but I can answer some of your questions...
Coordinates in ED are multiples of 1/32 Ly,
[...]
Additional distances don't help with precision; the algorithm either produces a single answer the works or it doesn't.
uh...

The basic method is called trilateration. If we had precise distances from ED, and people didn't make mistakes entering them, then we could just use those equations with 4 distances and get the right answer every time. Unfortunately ED only gives us distances to two decimal places and people make mistakes often. The lack of precision from ED means that instead of three distances specifying two points exactly they instead specify two small volumes of space.
I figured it would be intersection of shells as the seemingly obvious method, but I was wondering if there were others, as sometimes the obvious method isn't necessarily the best one (speaking generally about any problem and its possible solutions).

Just to clarify though: My question about the additional distances was coming from the possibility that ED reports a distance as X.YZ, but its really X.YZABC, and if you had enough distances, especially from different angles, you could eventually deduce what digits A B and C are (or rather, more precisely what position the star is in for which the distance would actually be X.YZABC). Also, additional distances, from differing angles should reduce the volume that you would have to search in (perhaps that was what you were referring to as the usually not worth it part?)

- - - Updated - - -

Polaris (25526)
Coordinates found for that system: -322.6875 / 194.59375 / -212.4375
The star coordinates themselves though are stored as float?
 

RedWizzard

Volunteer Moderator
I figured it would be intersection of shells as the seemingly obvious method, but I was wondering if there were others, as sometimes the obvious method isn't necessarily the best one (speaking generally about any problem and its possible solutions).

Just to clarify though: My question about the additional distances was coming from the possibility that ED reports a distance as X.YZ, but its really X.YZABC, and if you had enough distances, especially from different angles, you could eventually deduce what digits A B and C are (or rather, more precisely what position the star is in for which the distance would actually be X.YZABC). Also, additional distances, from differing angles should reduce the volume that you would have to search in (perhaps that was what you were referring to as the usually not worth it part?)
I think you're saying that more distances reduces the volume of the intersection of the shells and therefore results in a more precise location for the target system. That's true in the general case. In our case, because of the 1/32 Ly grid we know a system's location exactly as soon as we have enough distances to reduce the volume of the intersection of shells to the point where it only contains one grid location. So a given set of distances either precisely locates a system (in which case we know the distances exactly and have deduced ABC...) or it doesn't. If it doesn't then it means there is more than one grid location that qualifies (reproduces the set of distances we have). We can say that additional distances improves the precision but what's really happening is that additional distances reduce the set of candidate locations.

The "not worth it" comment was referring to precisely calculating the volume of the intersection of the shells. There are cases where doing that can mean that you can confidently locate a system with a set of distances which wouldn't be sufficient using the algorithm I use, but IMO the cost of the extra complexity required far outweighs the benefit when you can instead simply ask the user for another distance (especially since my page can recommend which distances are likely to help most).

I've made some diagrams to try to clarify what I'm talking about. Consider the 2d case where we've got 3 distances (at a certain precision). The general case looks like this:
GeneralCase.png
Each distance defines a ring due to the lack of precision in the distances. The yellow area defined by the intersection of the three rings is the location of the target system, as precisely as we can calculate. If we had more distances the yellow area could possibly be reduced (i.e. we could get a more precise location). The blue/red dots represent ED's 1/32 Ly grid. We know the target system lies on that grid so it must be at one of the two red dots. Since there are two candidates we'd need more distances to determine which is the true location. Additional distances would actually only help if they excluded one of those candidate points. Note that calculating the yellow area is pretty non-trivial, particularly with more distances.

My algorithm is slightly different. Because of the 1/32 Ly grid we can get the same result with less work. What I do looks like this:
MyAlgorithm.png
The distances are treated as exact and define a circle each. For each pair of circles I take the four grid points that surround the intersections (marked in blue; one set is outside the image). The set of all these grid points is the set of candidate locations. I then recalculate the distances for each of these candidates to find the candidate(s) which match the most supplied distances. In this case we should end up with the same two grid locations as with the general case.

One thing to note is that in these examples the precision of the distances is same as the resolution of the grid (i.e. the distances are +/- one grid division). That hurts the algorithms quite a lot and they'd both need more than the minimum of 3 distances quite often. In ED the precision of the distances is about 1/100 Ly compared to 1/32 Ly grid resolution so it's possible to get a single candidate from 4 distances most of the time.

The star coordinates themselves though are stored as float?
In ED? We don't know. The distance calculation is definitely done using single precision floats so they are almost certainly stored as either single precision floats or integers that are converted to floats when used.
 
Yes, keeping in mind I didn't know about the 1/32 grid when I was speculating.

Sorry, that last part about the coordinates was a reply to the next response whch I neglected to quote anything from and the forum merged my two posts together.

Now (this is for Anthornet I think) in check-coordinates, there is a matrix of 1s and 0s which gets longer the more variations there are. I presume this identified which particular "blue dot" and/or combination of distances is under consideration for that particular variation? Also, there is an angle shown? What is the angle (shouldn't there be 3 angles?)

This is one of the angles between the shown system and the system we are trying to locate, for this variation?
 
Top Bottom