Incorrect compilation of grid lines

classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

Incorrect compilation of grid lines

Roger Calvert
I have a file containing the British National Grid lines, as printed on Ordnance Survey maps. This can be found at http://www.rogercalvert.me.uk/osm/GBGrid/GBGrid.zip (this contains two files, they are the same except for the addition of the 'version' tag in the GBGrid06.osm file). I compile this file with mkgmap and overlay it on my GPS map.

This works correctly with mkgmap 2654 and It displays correctly in JOSM.

With mkgmap version 3241, the lines are misaligned and out of position. The behaviour is the same on MapSource, BaseCamp and my device. No error messages are produced.

(I have not used any versions of mkgmap in between these two).

My style file allocates codes in the 0x10300 range to these lines, but the effect is the same when I use code 0x21 (contour) for all lines.

Attached are screen dumps for a small part of the map, from JOSM, mkgmap 2654 and mkgmap 3241, and also the batch file I used to compile it.

I would greatly appreciate any advice.

Many thanks,

Roger

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Grid-josm.jpg (104K) Download Attachment
Grid-mapsource-mkgmap2654.jpg (80K) Download Attachment
Grid-mapsource-mkgmap3241.jpg (90K) Download Attachment
Test.bat (996 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Incorrect compilation of grid lines

Steve Ratcliffe
Hi Roger

> This works correctly with mkgmap 2654 and It displays correctly in JOSM.
>
> With mkgmap version 3241, the lines are misaligned and out of position.
> The behaviour is the same on MapSource, BaseCamp and my device. No error
> messages are produced.
>
> (I have not used any versions of mkgmap in between these two).

I've tried lots of different versions and I believe that the behaviour
changes at version r3081.  This is the merge of the branch that keeps
coordinates at a higher accuracy.  There are a lot of versions on
that branch and I may have to work out where on the branch things
changed.

..Steve
_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Incorrect compilation of grid lines

Roger Calvert
Steve,

Thanks for looking into this. Best of luck with narrowing it down further! Let me know if there is anything else I can do.

Roger

On 26/06/2014 18:30, Steve Ratcliffe wrote:
Hi Roger

This works correctly with mkgmap 2654 and It displays correctly in JOSM.

With mkgmap version 3241, the lines are misaligned and out of position.
The behaviour is the same on MapSource, BaseCamp and my device. No error
messages are produced.

(I have not used any versions of mkgmap in between these two).

I've tried lots of different versions and I believe that the behaviour
changes at version r3081.  This is the merge of the branch that keeps
coordinates at a higher accuracy.  There are a lot of versions on
that branch and I may have to work out where on the branch things
changed.

..Steve
_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev




_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Incorrect compilation of grid lines

Roger Calvert
In reply to this post by Steve Ratcliffe
Steve,

Has there been any progress in tracking this one down? I can live with an earlier version, but unless there is something special about my file, the problem could be affecting other people's maps too.

Roger

On 26/06/2014 18:30, Steve Ratcliffe wrote:
Hi Roger

This works correctly with mkgmap 2654 and It displays correctly in JOSM.

With mkgmap version 3241, the lines are misaligned and out of position.
The behaviour is the same on MapSource, BaseCamp and my device. No error
messages are produced.

(I have not used any versions of mkgmap in between these two).

I've tried lots of different versions and I believe that the behaviour
changes at version r3081.  This is the merge of the branch that keeps
coordinates at a higher accuracy.  There are a lot of versions on
that branch and I may have to work out where on the branch things
changed.

..Steve
_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev




_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Incorrect compilation of grid lines

Gerd Petermann
Hi Roger, Steve,

I've just returned from a cycle trip. I'll have a look at the problem during the next days.

Gerd


Date: Sat, 19 Jul 2014 12:56:01 +0100
From: [hidden email]
To: [hidden email]
Subject: Re: [mkgmap-dev] Incorrect compilation of grid lines

Steve,

Has there been any progress in tracking this one down? I can live with an earlier version, but unless there is something special about my file, the problem could be affecting other people's maps too.

Roger

On 26/06/2014 18:30, Steve Ratcliffe wrote:
Hi Roger

This works correctly with mkgmap 2654 and It displays correctly in JOSM.

With mkgmap version 3241, the lines are misaligned and out of position.
The behaviour is the same on MapSource, BaseCamp and my device. No error
messages are produced.

(I have not used any versions of mkgmap in between these two).

I've tried lots of different versions and I believe that the behaviour
changes at version r3081.  This is the merge of the branch that keeps
coordinates at a higher accuracy.  There are a lot of versions on
that branch and I may have to work out where on the branch things
changed.

..Steve
_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev




_______________________________________________ mkgmap-dev mailing list [hidden email] http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Incorrect compilation of grid lines

Gerd Petermann
In reply to this post by Roger Calvert
Hi Roger,

the problem is caused by the routine that removes obsolete points from straigt lines.
This routine doesn't care (enough) about the spherical distortian.
The routine uses herons formula to "calculate distance of point in the middle to line c1,c2".
This formula is for 2D, but used to work good enough with the rather short ways
we have in OSM. (The formula is also used in the Douglas-Peucker filter).
With long lines the as in your data, the errors are too big and the routine returns garbage.

If I got that right, we have to use the formula for the "Cross-track distance" as described here:
http://www.movable-type.co.uk/scripts/latlong.html
 
Unfortunately, this routine uses more trigonometrical calculations, so it will be slower.

@Programmers: Any other ideas?

Gerd


Date: Wed, 25 Jun 2014 12:12:18 +0100
From: [hidden email]
To: [hidden email]
Subject: [mkgmap-dev] Incorrect compilation of grid lines

I have a file containing the British National Grid lines, as printed on Ordnance Survey maps. This can be found at http://www.rogercalvert.me.uk/osm/GBGrid/GBGrid.zip (this contains two files, they are the same except for the addition of the 'version' tag in the GBGrid06.osm file). I compile this file with mkgmap and overlay it on my GPS map.

This works correctly with mkgmap 2654 and It displays correctly in JOSM.

With mkgmap version 3241, the lines are misaligned and out of position. The behaviour is the same on MapSource, BaseCamp and my device. No error messages are produced.

(I have not used any versions of mkgmap in between these two).

My style file allocates codes in the 0x10300 range to these lines, but the effect is the same when I use code 0x21 (contour) for all lines.

Attached are screen dumps for a small part of the map, from JOSM, mkgmap 2654 and mkgmap 3241, and also the batch file I used to compile it.

I would greatly appreciate any advice.

Many thanks,

Roger

_______________________________________________ mkgmap-dev mailing list [hidden email] http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Incorrect compilation of grid lines

Felix Hartmann-2
not an idea - but a comment. I think that for such a special nonusual case, there should be no degradation for the general use. Wouldn't it be enough to just switch off douglas peucker algo for maps where you want to include long "straigt" lines?
On 25.07.2014 10:46, Gerd Petermann wrote:
Hi Roger,

the problem is caused by the routine that removes obsolete points from straigt lines.
This routine doesn't care (enough) about the spherical distortian.
The routine uses herons formula to "calculate distance of point in the middle to line c1,c2".
This formula is for 2D, but used to work good enough with the rather short ways
we have in OSM. (The formula is also used in the Douglas-Peucker filter).
With long lines the as in your data, the errors are too big and the routine returns garbage.

If I got that right, we have to use the formula for the "Cross-track distance" as described here:
http://www.movable-type.co.uk/scripts/latlong.html
 
Unfortunately, this routine uses more trigonometrical calculations, so it will be slower.

@Programmers: Any other ideas?

Gerd


Date: Wed, 25 Jun 2014 12:12:18 +0100
From: [hidden email]
To: [hidden email]
Subject: [mkgmap-dev] Incorrect compilation of grid lines

I have a file containing the British National Grid lines, as printed on Ordnance Survey maps. This can be found at http://www.rogercalvert.me.uk/osm/GBGrid/GBGrid.zip (this contains two files, they are the same except for the addition of the 'version' tag in the GBGrid06.osm file). I compile this file with mkgmap and overlay it on my GPS map.

This works correctly with mkgmap 2654 and It displays correctly in JOSM.

With mkgmap version 3241, the lines are misaligned and out of position. The behaviour is the same on MapSource, BaseCamp and my device. No error messages are produced.

(I have not used any versions of mkgmap in between these two).

My style file allocates codes in the 0x10300 range to these lines, but the effect is the same when I use code 0x21 (contour) for all lines.

Attached are screen dumps for a small part of the map, from JOSM, mkgmap 2654 and mkgmap 3241, and also the batch file I used to compile it.

I would greatly appreciate any advice.

Many thanks,

Roger

_______________________________________________ mkgmap-dev mailing list [hidden email] http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev


_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

-- 
keep on biking and discovering new trails

Felix
openmtbmap.org & www.velomap.org

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Incorrect compilation of grid lines

Gerd Petermann
Hi Felix,

I agree. I am working on a simple patch that tries to detect that the formula doesn't work.
I just have to decide what to do in that case, typically it is better to keep the point, so
img size might increase.

Gerd


Date: Fri, 25 Jul 2014 11:12:40 +0200
From: [hidden email]
To: [hidden email]
Subject: Re: [mkgmap-dev] Incorrect compilation of grid lines

not an idea - but a comment. I think that for such a special nonusual case, there should be no degradation for the general use. Wouldn't it be enough to just switch off douglas peucker algo for maps where you want to include long "straigt" lines?
On 25.07.2014 10:46, Gerd Petermann wrote:
Hi Roger,

the problem is caused by the routine that removes obsolete points from straigt lines.
This routine doesn't care (enough) about the spherical distortian.
The routine uses herons formula to "calculate distance of point in the middle to line c1,c2".
This formula is for 2D, but used to work good enough with the rather short ways
we have in OSM. (The formula is also used in the Douglas-Peucker filter).
With long lines the as in your data, the errors are too big and the routine returns garbage.

If I got that right, we have to use the formula for the "Cross-track distance" as described here:
http://www.movable-type.co.uk/scripts/latlong.html
 
Unfortunately, this routine uses more trigonometrical calculations, so it will be slower.

@Programmers: Any other ideas?

Gerd


Date: Wed, 25 Jun 2014 12:12:18 +0100
From: [hidden email]
To: [hidden email]
Subject: [mkgmap-dev] Incorrect compilation of grid lines

I have a file containing the British National Grid lines, as printed on Ordnance Survey maps. This can be found at http://www.rogercalvert.me.uk/osm/GBGrid/GBGrid.zip (this contains two files, they are the same except for the addition of the 'version' tag in the GBGrid06.osm file). I compile this file with mkgmap and overlay it on my GPS map.

This works correctly with mkgmap 2654 and It displays correctly in JOSM.

With mkgmap version 3241, the lines are misaligned and out of position. The behaviour is the same on MapSource, BaseCamp and my device. No error messages are produced.

(I have not used any versions of mkgmap in between these two).

My style file allocates codes in the 0x10300 range to these lines, but the effect is the same when I use code 0x21 (contour) for all lines.

Attached are screen dumps for a small part of the map, from JOSM, mkgmap 2654 and mkgmap 3241, and also the batch file I used to compile it.

I would greatly appreciate any advice.

Many thanks,

Roger

_______________________________________________ mkgmap-dev mailing list [hidden email] http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev


_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

-- 
keep on biking and discovering new trails

Felix
openmtbmap.org & www.velomap.org

_______________________________________________ mkgmap-dev mailing list [hidden email] http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Incorrect compilation of grid lines

Felix Hartmann-2
Hi Gerd,

the only thing I am afraid about is broken contourlines data (due to
errors or missing data). There you quite often end up with long straight
lines. So the patch shouldn't make such errors even worse - I long even
hoped that mkgmap could have a function/filter to delete all long lines
- say straight over 5km without intersection, because I don't think that
such long straight lines exist in OSM data (except ferry lines, power
lines, railways and highway=motorway/trunk)


So maybe better not detect such a problem automatically, but add a
filter for the style-file where you could switch off douglas peucker
especially
e.g.: gridlines=yes [0x* nodouglaspeucker]
On 25.07.2014 11:15, Gerd Petermann wrote:
> a simple patch that tries to detect that the formula doesn't work.
> I just have to decide what to do in that case, typically it is better
> to keep the point, so
> img size might increase.

--
keep on biking and discovering new trails

Felix
openmtbmap.org & www.velomap.org

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Incorrect compilation of grid lines

Roger Calvert
In reply to this post by Gerd Petermann
Gerd,

Thanks for diagnosing this.

It would be possible for me to re-structure the file so that lines are no longer than (say) 10km. This would increase the source (and presumably .img)  file size somewhat, but should be handleable. I would need to do the same for my latitude/longitude grid generator. (This might also help with a rather different problem I have had with Osmand, which does not always show labels on the lines within the screen area - if the lines were much shorter, the labels would be more likely to appear on screen.)

What maximum length of line would produce sensible results?

Of course, this would not solve the problem for other lines such as contour lines, mentioned by Felix. Perhaps automatic detection of excessively long lines, with some default action, combined with a warning, would be appropriate. This would give the user the chance to find and perhaps change the offending data.

Thanks again,

Roger

On 25/07/2014 09:46, Gerd Petermann wrote:
Hi Roger,

the problem is caused by the routine that removes obsolete points from straigt lines.
This routine doesn't care (enough) about the spherical distortian.
The routine uses herons formula to "calculate distance of point in the middle to line c1,c2".
This formula is for 2D, but used to work good enough with the rather short ways
we have in OSM. (The formula is also used in the Douglas-Peucker filter).
With long lines the as in your data, the errors are too big and the routine returns garbage.

If I got that right, we have to use the formula for the "Cross-track distance" as described here:
http://www.movable-type.co.uk/scripts/latlong.html
 
Unfortunately, this routine uses more trigonometrical calculations, so it will be slower.

@Programmers: Any other ideas?

Gerd




_______________________________________________ mkgmap-dev mailing list [hidden email] http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev


_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev


_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Incorrect compilation of grid lines

Gerd Petermann
Hi Roger,

I prefer to solve the problem in mkgmap. My problem is that I don't yet fully understand the math,
so I am not sure in what case the heron formula doesn't work. Up to now I've only understood
that a term gets negative and therefore the calculation of the sqrt fails. This results
in a distance of Double.NaN and I can detect that case. A simple patch seems to fix
your problem, but I'd like to understand the effect first.
If I don't get that working, I'll implement the suppression flag as supposed by Felix.

Gerd

Roger Calvert wrote
Gerd,

Thanks for diagnosing this.

It would be possible for me to re-structure the file so that lines are
no longer than (say) 10km. This would increase the source (and
presumably .img)  file size somewhat, but should be handleable. I would
need to do the same for my latitude/longitude grid generator. (This
might also help with a rather different problem I have had with Osmand,
which does not always show labels on the lines within the screen area -
if the lines were much shorter, the labels would be more likely to
appear on screen.)

What maximum length of line would produce sensible results?

Of course, this would not solve the problem for other lines such as
contour lines, mentioned by Felix. Perhaps automatic detection of
excessively long lines, with some default action, combined with a
warning, would be appropriate. This would give the user the chance to
find and perhaps change the offending data.

Thanks again,

Roger

On 25/07/2014 09:46, Gerd Petermann wrote:
> Hi Roger,
>
> the problem is caused by the routine that removes obsolete points from
> straigt lines.
> This routine doesn't care (enough) about the spherical distortian.
> The routine uses herons formula to "calculate distance of point in the
> middle to line c1,c2".
> This formula is for 2D, but used to work good enough with the rather
> short ways
> we have in OSM. (The formula is also used in the Douglas-Peucker filter).
> With long lines the as in your data, the errors are too big and the
> routine returns garbage.
>
> If I got that right, we have to use the formula for the "Cross-track
> distance" as described here:
> http://www.movable-type.co.uk/scripts/latlong.html
>
> Unfortunately, this routine uses more trigonometrical calculations, so
> it will be slower.
>
> @Programmers: Any other ideas?
>
> Gerd
>
> ------------------------------------------------------------------------
> ------------------------------------------------------------------------
>
> _______________________________________________ mkgmap-dev mailing
> list [hidden email] 
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
>
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

--
------------------------------------------------------------------------

Roger Calvert
http://www.rogercalvert.me.uk
------------------------------------------------------------------------

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Incorrect compilation of grid lines

Gerd Petermann
In reply to this post by Felix Hartmann-2
Hi Felix,

see
http://gis.19327.n5.nabble.com/Patch-v1-detect-cases-where-Herons-formula-is-failing-in-3D-tp5812773.html

please let me know if the patched verrsion causes any problems.

The only expected effect of the patch is that fewer points are removed
from the original data. On normal OSM data, the effect is minimal.

I tried it with normal OSM data and some contourlines. For data
in Australia I see small changes at low resolutions (<=15) for shorelines,
but I can't say which result is worse, as both versions are a mess.

Gerd

> Date: Fri, 25 Jul 2014 11:24:44 +0200

> From: [hidden email]
> To: [hidden email]
> Subject: Re: [mkgmap-dev] Incorrect compilation of grid lines
>
> Hi Gerd,
>
> the only thing I am afraid about is broken contourlines data (due to
> errors or missing data). There you quite often end up with long straight
> lines. So the patch shouldn't make such errors even worse - I long even
> hoped that mkgmap could have a function/filter to delete all long lines
> - say straight over 5km without intersection, because I don't think that
> such long straight lines exist in OSM data (except ferry lines, power
> lines, railways and highway=motorway/trunk)
>
>
> So maybe better not detect such a problem automatically, but add a
> filter for the style-file where you could switch off douglas peucker
> especially
> e.g.: gridlines=yes [0x* nodouglaspeucker]
> On 25.07.2014 11:15, Gerd Petermann wrote:
> > a simple patch that tries to detect that the formula doesn't work.
> > I just have to decide what to do in that case, typically it is better
> > to keep the point, so
> > img size might increase.
>
> --
> keep on biking and discovering new trails
>
> Felix
> openmtbmap.org & www.velomap.org
>
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev