Encoded binary paths anyone?

theo-armour commented 8 years ago

@geoffmcl

http://fgx.github.io/sandbox/flightpath-to-2d-map-texture/

and

http://fgx.github.io/sandbox/read-elevations-update-plane/

These scripts load a CSV file with 800+ points - but only display a simple rectangle to indicate min and max latitude and longitude

The reason is that the GooGle Maps API supports URS up to 2048 characters - which is not enough to contain all the points.

But it would be nice to show the full path detail. And this may be doable by encoding the paths

See

https://developers.google.com/maps/documentation/utilities/polylinealgorithm

What do you think? Is this something you could take a look at?

geoffmcl commented 8 years ago

@theo-armour wow... yeah that looks like an interesting coding issue ;=))

I tried to write it in perl script, and my first cut got close... see example down near bottom of the polylinealgorithm link...

Points: (38.5, -120.2), (40.7, -120.95), (43.252, -126.453)
Encode pts 38.5 -120.2 2.2 -0.75 2.552 -5.503 
My coded polyline: _p~I~ps\_ulLnnqC_mqNvxq@
Encoded polyline: _p~iF~ps|U_ulLnnqC_mqNvxq`@

Just got to figure out why I got some differences... then I could convert the flown track to a string-of-ascii...

Will probably have to also work on a decode just to understand the process more...

Be back soonest, if I can solve the problem...

geoffmcl commented 8 years ago

@theo-armour as reported, in this maze of issues, my perl script correctly generates the correct ascii in lots of cases, BUT still fails on some, I think only some negative values... bah, Bah, BAH!

I have re-written the algorithm again, in a new perl script, dec2google.pl, and it persists on having this same problem ;=((

I have even written, an also quite successful, ascii to decimal decoded, just to try to track down the problem... in reverse...

Example: If I pass -120.2 to my encoder, I get the wrong ascii ~ps|u - I expect ~ps|U - note just the last character u versus U... The difference between upper and lower case alpha is just one bit different... looks a simple problem, right? Ha! Ha!

If I pass the correct ascii ~ps|U to my decoder I get the correct -120.2 back... Yippee...

If I pass the bad ascii ~ps|u to my decoder I get back a stupid -287.97216 back... which if I pass to my encoder I get another ascii ~ps|u@ back... ie not yet a complete 2-way street...

Something BIT is WRONG!!!

Over the coming days I will publish these scripts for others to look at...

But I have spent so much time on this already, I must give it up for a while, until another thought occurs to me...

But no Goggle ascii track in the meantime... and no prediction of when!... sorry...

geoffmcl commented 8 years ago

PS: Note the title here is misleading... While this is an encoded path, it can not be called binary...

It should be Encoded ASCII paths anyone? ... maybe should amend the title... but not important...

theo-armour commented 8 years ago

Note the title here is misleading... While this is an encoded path, it can not be called binary...

Title is my bad. Sorry.

How about 'base64 polyline encoding scheme' as a title?

https://en.wikipedia.org/wiki/Base64

But I have spent so much time on this already, I must give it up for a while, until another thought occurs to me...

Again, I'm sorry to have created an issue with no easy solution.

Maybe this could help:

https://developers.google.com/maps/documentation/utilities/polylineutility

In any case, I think the priority should be on reducing the file size of the elevations data file and capturing points of interest.

On Tue, Apr 26, 2016 at 12:38 PM Geoff McLane notifications@github.com wrote:

PS: Note the title here is misleading... While this is an encoded path, it can not be called binary...

It should be Encoded ASCII paths anyone? ... maybe should amend the title... but not important...

— You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub https://github.com/fgx/fgx.github.io/issues/11#issuecomment-214862148

geoffmcl commented 8 years ago

@theo-armour concerning the title, as stated it is not so important, but it is also not base64 either... has some similarities, but not the same...

Maybe Google polyline encoding anyone?, or something... as far as I can see this is Google proprietary...

And I have already been using the polylineutility to generate more samples, extensively... but it does not show the full generation steps, unfortunately...

And I have already tried to explore the source of that page for clues on the Google polyline generation, and suspect it is in /maps/documentation/utilities/polyline-utility/polyline.js... the functions is showEncoding(), which uses var encodeString = google.maps.geometry.encoding.encodePath(latlngs);, where ever that is... could not immediately find it... but anyway that is in javascript, but it would still be good to look at, if found...

reducing the file size of the elevations data

Have already responded on this, and suggest aside from file compression to speed up an internet load, do not really see any other way to reduce the size of this list... at 512x512 means 262144 values, full stop... and any increase on the 512 means more...

But these are elevations, and to the nearest foot, or even nearest meter, would be accurate enough... so can be integers, not floats... that chops at least 2 bytes off each

And to take one clue from the Google polyline, another reduction might be only the first being a real full (integer, no decimals) altitude (AMSL), and every value following being a delta to the last...

But that means more work after your (zip/gz) load, (uncompressing) and calculating an actual value... but this might be faster...

Some comparative file sizes, and the last a gz/gzip compression -

1,572,863 elevations-512x512-r3.txt - current original file
2,097,152 elevations-512x512-r3.txt.bin - as double, binary Uint8Array - bigger
1,047,959 elevations-512x512-r3.txt.int - remove decimal - round to integer - ascii
   622,631 elevations-512x512-r3.txt.deltaint - only first whole, others as delta - ascii
   134,043 elevations-512x512-r3.txt.deltaint.gz - above gzipped - binary

That is 262144 deltas is just a 134 KB gz (binary) load - should be just a ms transfer and load... and as you say decompression should be fast... will try to push the last to the repo in case you want to try it...

capturing points of interest

I still do not know how to add this...

You seemed to have divide these up into 1, 2, 3 - take care adding a hash, #, as github sees these as links to other issues... but I see them as -

Some would be just placard, say naming a mountain, or hill, if it has a name... as something already visible in the terrain, like stay left of Mt Blah - big VFR flying clues...
Some would be man made object, like the castle on hill, or the intersection of the A-2 and C-53? roads, so have to add the object outline, and some placard... And this is per the image... these are all man-made VFR clues...
But note it does not include the circuit names like R-TL, base, etc that you picked up as annotations... these are, as you said sort of air controller waypoints, thus are not visual things...

This a VFR flight, with emphasis on the Visual on the ground...

Need to give this more thought...

theo-armour commented 8 years ago

@geoffmcl

Data Files

Some comparative file sizes, and the last a gz/gzip compression -

Wow! thanks for this comparison. It looks to me like zipping is the way to go.

In the past - with node.js - I have used https://stuk.github.io/jszip/

I will see if I can get this script to work in the browser with our files.

It seems to me that zipping could be useful both with elevation data and flightpath data

will try to push the last to the repo in case you want to try it...

I will have a try...

Points of Interest

I reckon this is an issue with a bunch of issues. And so it should have it's own issue.

I will start one and then cross-reference this and that issues.

Here is a link to the new issue Points of Interest

geoffmcl commented 8 years ago

@theo-armour ok, it seems I got my Google polyline perl generator fixed ;=))

I gave the vital clue when I mentioned the difference was I was generating u when it should be a U, and reminded myself that that is just 1 bit different, namely bit 0x20 - 100000!

And then look for where does that happen in the Google polyline algorithm steps...

Step 8. in the process says "OR each value with 0x20 if another bit chunk follows:". My added emphasis. So this OR-ing stops one 5-bit chunk before the end... but what about this end?

Well, at this point, for certain decimal values, the last 5-bit chunk can be 00000, and it seems it should then be discarded...

And when you do that, the OR with 0x20 stops one chunk earlier... and bingo the final U - 10110 does not get OR-ed with x20 to become the bad 110110 - u

Yowee, I love coding - so logical ;=))

Will now shortly be able to create a Google encoded path ;=))

zipping is the way to go

Ok, agree with this... my zip of the elevations was actually using gzip, but maybe JSZip handles this... not sure... but any compression/decompression method is fine...

But I have re-checked my generation using delta elevations, but maybe this is not so good! The cumulative loss of accuracy using just integer elevations means you can get quite a lot a drift from reality...

But a gzip of the 1,047,959 byte elevations-512x512-r3.txt.int, integer elevations, also produces a reasonable 221,387 byte elevations-512x512-r3.txt.int.gz... which I will add to the repo...

Look forward to your successful experimentation with these...

And of course zipping can then be applied to the flightpath list of points... say the 571,897 byte LEIG-L1500-cooked-01.csv, making it a 206,867 byte LEIG-L1500-cooked-01.csv.gz, even before applying the Google polyline algorithm...

VFR Reference points

We still seem very different, very far apart, on this ;=()

You point to fgx/fgx-airports, but what we have there are all IFR things... navaids, runways, ils, fixes... nothing to do with this VFR circuit of LEIG...

VFR - Visual Flight Rules - fly by what a human can see out the window on the ground
IFR - Instrument Flight Rules - Fly by instruments, with no window at all.

Well IFR can still use VFR for take off and landing, but after that, like in the Concord, the window is closed and it is all by instruments... waypoint to waypoint...

So again out of your 1, 2, 3 types, only maybe 2 would apply, but even then very selective of Other Local Waypoints... only those visible objects to fly this particular flight... not a general tourist map of the area...

So still need some discussion, understanding and agreement on this...

PS: For a few days now, having internet connection problems, so can not post this now... will try later... its working now, so...

theo-armour commented 8 years ago

Will now shortly be able to create a Google encoded path ;=))

Yay!

my zip of the elevations was actually using gzip, but maybe JSZip handles this... not sure..

I hope JSZIp handles gzip too - and will let you know.

I will get into this in the next few days. I really look forward to have 1024x1024 meshes.

VFR Reference points

Please can you copy these points over to the Points of Interest Issue?

Points of Interest

geoffmcl commented 8 years ago

@theo-armour using my fixed Google polyline perl generator generated my first ASCII list using LEIG-L1500-cooked-01.csv and got several shocks...

The first was that the delta distance between lots of waypoints is very small, so the the output looks like -

ohy|FqsaI@A@A@A@A@A@A@A@A@A@A@A@A@A and on... and
long lists of @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

What this mean is the delta difference between these initial points is 0,1... and the @@ mean 0,0...

That is quite understandable, since these were sampled at 1 Hz IIRC, and the aircraft is moving at a relatively slow speed of 60-100 knots, so does not travel far in 1 second...

And given the lossy nature of this algorithm - it rounds everything to a maximum of 5 decimal places, so when you try to put back together the track you get substantial drift for actual...

In this case the first point is 41.5861554761,1.6519343471, which is rounded down to 41.58616 1.65193, so when you add the first 10 deltas of 0,1 you get 41.58616,1.65203 , but the 10th waypoint is 41.58604,1.65199, so we are already some 14 meter off!

This is the same problem mentioned when trying to use deltas for the elevations. The values drift off the actual...

Now it might be possible to compensate a little for this, in not specifically using only the delta to the last, but keep good track of the deltas, and occasionally add a delta to correct... more work, but possible...

But the final realisation was that this only gives to the lat, lon of the track, but we need a 3D track - lat, lon, alt...

The up-shot is I do not think we can use this Google polyline for our track!

First it is only for 2D lines - we want 3D - and the lossy nature means more work would need to be done to ensure reconstruction will get back to actual.

So, while for me, this has been a great exercise in understanding and implementing the Google polyline algorithm, I think it has no use in this flight path generation...

Your thoughts?

So, as also discussed, I think compression/decompression is the only way to reduce these file sizes... How is that going?

FlightGear Views

I had another thought where you can see some of these FlightGear views in action, and that is in videos that people have made...

Here are 2 I looked at -

https://www.youtube.com/watch?v=mW3QBrVvmpM - fly-by view at abt 4 mins https://www.youtube.com/watch?v=APkHEFdcn_c - Chase view at abt 1 min

But there are many more...

theo-armour commented 8 years ago

@geoffmcl

So, as also discussed, I think compression/decompression is the only way to reduce these file sizes... How is that going?

I agree - and yet see jszip-test post - coming soon...

Views

Thanks for the video links. Watched both.

fgx / fgx.github.io