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

[TornSoul]

For the calculation of the Planes 3 points (systems) are involved:
2 Fix Reference System + The unknown System/point that you call P0.

The plane(s) are calulated with xref1,yref1,zref1,xref2,yref2,zref2 and r1 and r2.

Aha! - There's the missing bit

I calculate the plane of this circle.
Instead limiting the possible positions for P0 on this circle I limit it on the plane of this circle. I throw away information for the benefit to convert it into a linear system.
something with planes is mostly linear a circle mostly not.

Ok I can see now how it would work.
And I can see why p0 would be in that plane obviously.

I wonder a bit about the math - Because it will also fail in the case where all refs are co-planar (you'll get a line instead of a point)
I'm curious how the math looks, as it's solution can turn out both a point and a line (if co-planar), which must make the math look a bit "funny".
(unless ofc somewhere it gets short-circuited by a division by zero or something),

And how do you deal with the fact that the distances are not exact (rounding errors) - As the math relies on exact values to work (it's the same for std trilation - But it will always produce a result regardless, it just might not be correct )

 

[TornSoul]

@TornSoul:
.wxm is wxMaxima. A free software clone from mathematica

Sweet! - Been looking for something like that for ages.
Will definitely have to take a look at that (tomorrow...)

And thanks for the legend - Would be impossible to understand without it (still not sure it's possible though )

I'll probably give it try (again - Tomorrow or later....)

 

[JesusFreke]

The actual coordinate calculation - Only includes 3 of the ref systems (p1-p3), so there is nothing to "remove" to do a recalculation to find a pair of candidates.
(and this is done for any combination of 3 refs)

Determining which one from the pair to use, is what involves the rest of the ref systems.

And this is where things could go "wrong" (with bad distances), as each remaining ref is then used as a "p4" to see which candidate is the correct one

And here is where one could "remove" one or more refs (r-refs), to see if all other refs (o-refs) check out when the r-refs are removed - more or less as per your suggestion.

What I'm suggesting is a bit of a shortcut, that covers all your possible combinations in one go.
(some systems have 15+ distances logged - running all combo's for all combos of 3 combos, starts to become a lot of combos )

The shortcut being - Simply assume that there is at least 5 good ones, and if they check out we are good (every other ref can be good/bad we don't care)

With your algo, we would end up in precisely that situation, if you remove enough refs anyhow.

That's as much a question as a statement

I'm not sure exactly what algorithm you're using to calculate the coordinate. My algorithm assumes there is some function that takes a set of distances, and returns, e.g. a set of candidates that match those distances. Or rather, in this specific incarnation, it returns a coordinate if it is the only valid candidate, or null if there are 0 or more than 1 candidates.

I'm pretty sure you had mentioned doing a grid check, so that function could be implemented as: do trilateration on a random 3 distances from the set, then do a grid check around the 2 coordinates from trilateration. The result of the grid check will be a set of 0 or more candidates which match the data. So then, check if there's only result and return that, otherwise return null.

Of course, the grid check itself is somewhat flawed, because you don't know how big of a grid is needed, and it requires doing a lot more reverse distance checks than needed. But with a big enough grid, it should be "good enough", if a bit slow


So, for a system with 15 distances, you would call the function described above 15 times - once for each combination of 14 coordinates. For the 2 distances case, you would need to call the function for each combination of 13 coordinates, which would be a total of combination(15, 13) = 105, which is still reasonable.

Even with 5 distances like you describe, you're not guaranteed to have n+1 redundancy. I would guess it's fairly likely to be true, but not likely enough to always be true.

I guess it mostly depends on how robust you want to make it, or to put it another way, how good is good enough. In any case, even if you don't want to implement something like that yourself, as long as the data is available, others can do so.

I haven't been keeping up with your design of the system - but it would be good if you could expose all distances that have been entered, but have a "invalid" flag on the ones you think are invalid, which will allow others to cross-check the findings.

 

[TornSoul]

do trilateration on a random 3 distances from the set

Ah - But I do it on *all* possible combinations of 3 sets. Not just one randomly picked one.

Exactly to make sure I get at least one "correct" set of distances to work with (assuming there is at least 3)

and C(15,3) = 455 - Which would then have to be multiplied with C(15, 13) = 105 which is 47.775

Of course, the grid check itself is somewhat flawed, because you don't know how big of a grid is needed, and it requires doing a lot more reverse distance checks than needed. But with a big enough grid, it should be "good enough", if a bit slow

Ah but I do (empirically anyhow).
I ran A LOT of test - and posted some numbers earlier as well...

A grid (or cubesearch as I call it) - with a grid/cube of radius of 4 (diameter of 9) catches 99% (or something) of cases - Even radius 3 is about 98%.
Diminishing returns rather quickly.
So to be 99.9999% sure I catch everything, I actually run it with a radius of 8 (which admittedly is a bit )
And yes it hurts timewise... quite a a lot actually (up to about 5 it's imperceptible, but then it starts getting noticeable)

Now - with a radius of 8... we get 17^3 places to check (4913).
Which would have to be multiplied with 47.775.... Ouch

It's a bit of lie though - Because most of the C(15,3) combos returns candidates very close to each other - So the cubes overlap by quite a lot usually.
So I remove the duplicates before doing the reverse distance check

 

[TargetLost]

Added graphics that explains the base of the idea and the Maxima Formulas

https://www.dropbox.com/sh/9g15l3um92vu0x3/AACldLmEAPC_2JzM4K_wtT02a?dl=0

The math will fail if say you have 4 reference systems and 3 of it are exactly in a line and take this as the only reference. However that's unlikely because we can choose the reference and you can take more than 4. (actually I have a simulation running to find the best 4 of the Beta2 file)

Like in the normal case you need at least 4 Reference Systems to determine P0.
not more than 2 in a line and not more than 3 in a plane
example:
(0,0,0)
(1,0,0)
(0,1,0)
(0,0,1)
is a perfect reference

With those 4 you can build 4*3 = 12 planes which is a bit pointles because always 2 will be the same just flipped M1 to M2 and M2 to M1 (flipped) and from the 6 left only 3 really contribute I believe the other 3 will most probabily be rendunant too if you analyze it although I don't know for sure.

But it doesn't harm in any way to simple add up all 12 planes in the Error Sum that we want to minimzie. That's what I do.

 

[JesusFreke]

Now - with a radius of 8... we get 17^3 places to check (4913).
Which would have to be multiplied with 47.775.... Ouch

It's a bit of lie though - Because most of the C(15,3) combos returns candidates very close to each other - So the cubes overlap by quite a lot usually.
So I remove the duplicates before doing the reverse distance check

Like you said, a "bit" of a lie . The vast majority of those calculations will be duplicates, which you can easily optimize with memoization, or other sorts of deduplication, like you mentioned.

And to be honest, you could even do something more intelligent, like keep track of which distances for each point in the cube search that "invalidate" that point (i.e. have an error > 0), and then ensure that every point except the 1 valid point are invalidated by at least 3 distances (for n+2 redundancy). It's effectively the same thing, but you only have to do the reverse distance checks for each point once.

And now that I think about it, that could be used even to find invalid distances.

As a completely made up, but hopefully not too unrealistic example: Let's say that you end up with a "cube" (I'll use a 2-d grid for illustration) that has the following number of invalidations (the number of distances that have an error of > 0) for each point.

9 9 9 9 9
9 5 5 5 9
9 5 1 5 9
9 5 5 5 9
9 9 9 9 9

Looking at it this way, it's immediately apparent that whatever distance is invalidating the point in the middle is the wrong distance. After removing that distance, you would end up with:

8 8 8 8 8
8 4 4 4 8
8 4 0 4 8
8 4 4 4 8
8 8 8 8 8

And from this "invalidation cube" (if you have a better term, feel free to suggest! ), you can see that we have n+3 redundancy (the minimum number of invalidations is 4, which gives 3 redundant invalidations).

It should be a simple matter to keep track of the number of invalidations while doing the reverse distance checks. And then to find a bad distance or distances, you search for the point with the least number of invalidations. If there is only 1 point, then that is the correct point, and the distances invalidating it are incorrect. If there are multiple points that have the same minimum number of invalidations, then I *think* you can assume that the intersection (in set terms) of invalidating distances of those points is incorrect. And then, once you remove those incorrect distances, there are a couple of cases:

1. You end up with multiple "minimum" points that are invalidated by non-overlapping sets of distances. You need more data to determine which distance is invalid
2. You end up with a single minimum point - this is the "correct" coordinate, but likely with a low level of redundancy/certainty - and the distances invalidating it are invalid.

Yes, I think that's a much better way of thinking about it

 

[TornSoul]

Alright TGC alpha version 0.2 is live.

Some minor changes
- added some extra options, specifically "outputmode" (Terse vs Verbose)

Also the status object of the response has been generalized to the same format for all 3 possible Methods.
The submit method, unfortunately due to it's verbosity, was different from the others.
The former two have been fixed to conform.

Added a "knownstatus" to the GetSystems method. Makes it possible to pull only systems that have coordinates, or the reverse, or all.

Also: The api docs have been fully updated!!! (was THAT a chore to do....)

Api docs: http://edstarcoordinator.com/api.html

Please take note to use "ver:0" (zero) while this is still alpha - or you won't get anything back.
Will be changed to "ver:2" once we are satisfied things work.

Last thing on the list is to update the input form for EDSC itself - But that's for tomorrow....

 

[TargetLost]

Aha! - There's the missing bit

And how do you deal with the fact that the distances are not exact (rounding errors) - As the math relies on exact values to work (it's the same for std trilation - But it will always produce a result regardless, it just might not be correct )

The input for r1 and r2 is of course the imperfect distance from ED rounded to 2 digi after the point.
So the planes will be at slightly wrong position. (In my graphics see dropbox link tha ancor point PK will be slightly wrong) (However if P0 is well between M1 and M2 but far away of their line then it looks like the error gets natural minimised already.)

Thats where minimizing of least square error comes into play. That's what is really good for to handle exactly such inaccuracy.
If we have more than 3 planes all might be a bit wrong then the real position will be in a small distance to that planes (or multiple plane builds a cross section instead a point) and we simple seek the best spot in there by asuming it will be the one with the smallest distance to each plane.

(if I just think about it..might be the 6 relevant planes instead of 3 in case of 4 points might help here but I really haven't checked it all that in deep I more tried it out and saw that it works very well better than I ever expected. Remember I original only wanted to have some good start values for newton )

 

[Little Angel]

So, I'm at a decision point, and it would be good to get some advice.

I'm working on a companion tool for ED.

Primarily, it's for me to help me look at the map and plan jump routes when the BB, or commodities window is open. Bluntly, a replacement for the Galactic Map, which is too cumbersome to be very useful right now. Additional functionality can be added as I go.

A reminder:
[video=youtube;PIiapow-2SQ]https://www.youtube.com/watch?v=PIiapow-2SQ[/video]

You can try to use it here, but currently I'm using a beta of the Unity webplayer, so it could be hit and miss for the next few days/weeks until Unity releases the version I'm working with for the web (It's in RC1). I can produce a WebGL version, but I have not had the chance to test it. Eventually, this is an easy port to tablets, pc, etc.

--

The decision point:

I'm at the point where myself, or any user this tool gets distributed to, could contribute to a crowdsourced mapping solution by pushing new data from the tool to some sort of online repository.

I've dug through some of the bulk posts, and I've been through the revised OP, but I'm still unclear what the best way to proceed is.

I'm at the stage where I have a working test UI where I can update existing start data - including trading information like Allegiance, etc. I can create a new star system and add the data to it. I can add a test where the distance to neighbouring stars can be added as well, returning the location of the new star system.

If I had a format to write to, and a location to push the data to, I can add it to this tool.

Then, after distributing this tool, which I hope other Commanders would use for their personal needs, all this new and additional data could be pushed to a public place, adding to the mapping project.

Part of taking the pain out of the crowdsourcing process is making the process useful to the people using it. "Dang, that system isn't in my map. Better add it!", and then have a "push" or "share" button there after the data is added.

There would need to be an "update" button as well, to grab that updated data, but that should be relatively easy as well.

Advice?

 

[TornSoul]

Added graphics that explains the base of the idea and the Maxima Formulas

https://www.dropbox.com/sh/9g15l3um92vu0x3/AACldLmEAPC_2JzM4K_wtT02a?dl=0

That helps a ton - Thanks!
I still have no idea what eq1 represents though
Ie. why is that formula correct, what does it "do" (is it adding vectors or...)

The rest I can follow.

But it doesn't harm in any way to simple add up all 12 planes in the Error Sum that we want to minimzie.

Probably true

Any idea if this is resistant to wrongly reported distances?

If not, perhaps (as JesusFreke has been suggesting for the other method) leave out 1 pair, and then try for each such combination (as one should then be wrong, and thus be identifiable)

The first derivation of this Err Sum gives you a perfectly linear equation set. Which you can simple solve A*x = b
It's a Matrix of 3X3. (we have 3 coords)

That last bit I'm not sure how to handle (by hand) either

With more than 4 reference systems you are in fact getting an over determined system as well, which needs to be handled.

 

[TornSoul]

If I had a format to write to, and a location to push the data to, I can add it to this tool.
<snip>
There would need to be an "update" button as well, to grab that updated data, but that should be relatively easy as well.

Advice?

The TGC (hosted on EDSC) is what you are looking for (look up a couple of posts).
It ticks all your marks.

Alright TGC alpha version 0.2 is live.

<snip>
Also: The api docs have been fully updated!!! (was THAT a chore to do....)

Api docs: http://edstarcoordinator.com/api.html

Please take note to use "ver:0" (zero) while this is still alpha - or you won't get anything back.
Will be changed to "ver:2" once we are satisfied things work.

Sounds like exactly what you are looking for


And I *really* like the idea of the map!

----

Note that data will change again once we hit Gamma (if you weren't already aware)

 

[Little Angel]

The TGC (hosted on EDSC) is what you are looking for (look up a couple of posts).
It ticks all your marks.



Sounds like exactly what you are looking for


And I *really* like the idea of the map!

----

Note that data will change again once we hit Gamma (if you weren't already aware)

Yay! Thanks! I think I just stumbled over that post as I was back reading. (80 pages of maths was intimidating me.)

Thanks for the "like". I'll make sure I get it out on as many platforms as possible. Personally, for me, I want it on my iPad. And test show it runs fine on the iPad with the current star set.

I am aware the data will change.

What I'm hoping to do is get something ready in time for Gamma, so people have some thing they can use to help out.

I'll admit I'm much better at front-ends than all the heavy lifting back-end stuff you've all been working on. My wife can do that, but it can be a struggle for me at times.

 

[Little Angel]

I am assuming that, now that I've read up on EDSC, the only data being held is the Star name, and it's coordinates (in, say a Vector3 format)? So any of the other system data: Star Type, Economy, etc., is not being maintained specifically by anyone in this mapping group?

 

[TornSoul]

So any of the other system data: Star Type, Economy, etc., is not being maintained specifically by anyone in this mapping group?

It's on the TODO for TGC.

Should be easy enough to add once (via it's own method) we are happy with the core of TGC.
The DB is setup to be prepared for such extensions.

But there's only so much time in a day

---
EDIT: In fact it should be so easy (as it's nothing but data submission) that if you where to outline what you want to submit/retrieve, I could probably knock something up really quickly - should I run out of other things to do the next few days

 

[RedWizzard]

TGC alpha 0.1 is live

Let me know how it goes - and what changes/additions you'd like to see

and ofc.. any bugs... let me know

First bug: if I call GetSystems with cr < 2 and outputmode = 2 I get an internal server error. I suspect there is bad data with cr = 1 that's causing this.

I think it would be good to include the cr in the distance output too (there is a cr on each distance, right?)

 

[TornSoul]

First bug: if I call GetSystems with cr < 2 and outputmode = 2 I get an internal server error. I suspect there is bad data with cr = 1 that's causing this.

Confirmed with v0.2 - Will look into it.

I think it would be good to include the cr in the distance output too (there is a cr on each distance, right?)

Well duh me.. No idea how I managed to not put the cr value in the output - Because yes it's absolutely there..

 

[TornSoul]

cr added and api docs updated.


The bug... Seems to be intermittent.
It works now... But didn't before, just as you reported...

Next time it happens for you, could you try
1: repeating the request 4-5 times (or whatever) (trying to establish if it's just the first one or two hits that fail)
2: If it still errors, try doing a "valid" request (change say cr to 5)
- If that then works, then try the cr=1 again.

The above is what I did before it worked again by itself - I'd like to try and establish if that's a pattern or not.

As it is I got nothing to go on... (intermittent errors is the *worst* kind of errors...)

 

[RedWizzard]

cr added and api docs updated.


The bug... Seems to be intermittent.
It works now... But didn't before, just as you reported...

Next time it happens for you, could you try
1: repeating the request 4-5 times (or whatever) (trying to establish if it's just the first one or two hits that fail)
2: If it still errors, try doing a "valid" request (change say cr to 5)
- If that then works, then try the cr=1 again.

The above is what I did before it worked again by itself - I'd like to try and establish if that's a pattern or not.

As it is I got nothing to go on... (intermittent errors is the *worst* kind of errors...)

Yes, I tested that way before. Just tried it again and it's still failing consistently if cr < 2 and outputmode = 2 on both my own code and the jsfiddle from the api page. Momentarily thought it was working in the jsfiddle until I realised I was calling GetDistances instead of GetSystems. GetDistances does return data and I noticed that your commander name seems to be corrupt:

commandercreate: "TornSoulåøæêá"

The other "unusual" thing about that system is the null coordinates. GetDistances works anyway so probably neither of those are causing the issue.

 

[TornSoul]

Hmm maybe I tested on GetDistances as well when it worked...
Failing consistently(a Good Thing(tm)) for me now as well.

commandercreate: "TornSoulåøæêá"

The other "unusual" thing about that system is the null coordinates. GetDistances works anyway so probably neither of those are causing the issue.

Hehe - No that is actually perfect.
From testing "weird characters" getting transferred back and forth correctly.
But nice of you to notice/report!


The null coordinates: I've been in great doubt about how to handle (display/transmit) that actually..
I've settled on just putting null there, as that's what's in the DB - and at least JavaScript will handle that just nicely.
It seems to be most consistent - although it ain't so pleasing on the eyes. Which really shouldn't matter one bit (still annoys me though )

 

[TornSoul]

Fixed.

And it was indeed the null coords that was the issue.
I'd missed *one* spot where I was converting the coords (hope there isn't more lurking...)

(and yes yes.. I really should get that re-factored out so it only happens in one place... )