Explanation of the is_in function

Hi When testing the IS_IN function I get very nice results ! Thank you very much for this improvement. Could somebody help me to explain why a certain pedestrian is not catched by the rules? Also not a big deal, I'm already happy wit the current results, it is just for understanding. I am using pedestrian streets without an outline if crossing pedestrian areas. 95% works perfectly but some seem to fool me. Before (The red lines are nicely replaced in the after situation, but the blue one is not) highway = pedestrian & jbmsquare != true & is_in(highway,pedestrian, any) = true [0x10d0c resolution 24 continue] area: München Viktualienmarkt: https://www.openstreetmap.org/#map=19/48.13504/11.57637 pedestrian : https://www.openstreetmap.org/way/240014256 square: https://www.openstreetmap.org/relation/7431621#map=19/48.13512/11.57670 [cid:image002.jpg@01D62CF3.C553B200] After [cid:image005.jpg@01D62CF3.C553B200] Met vriendelijke groet, Joris Bo jorisbo@hotmail.com<mailto:jorisbo@hotmail.com>

Hi Joris couple of questions: 1/ what is jbmsquare and how is it set 2/ what does the rule 'continue' into. It looks like the red lines that have gone are entirely within the pedestrian area, but the blue one isn't. Ticker On Mon, 2020-05-18 at 07:07 +0000, Joris Bo wrote:
Hi
When testing the IS_IN function I get very nice results ! Thank you very much for this improvement. Could somebody help me to explain why a certain pedestrian is not catched by the rules? Also not a big deal, I’m already happy wit the current results, it is just for understanding. I am using pedestrian streets without an outline if crossing pedestrian areas. 95% works perfectly but some seem to fool me.
Before (The red lines are nicely replaced in the after situation, but the blue one is not)
highway = pedestrian & jbmsquare != true & is_in(highway,pedestrian, any) = true [0x10d0c resolution 24 continue]
area: München Viktualienmarkt: https://www.openstreetmap.org/#map=19/48.13504/11.57637 pedestrian : https://www.openstreetmap.org/way/240014256 square: https://www.openstreetmap.org/relation/7431621#map=19/48.1351 2/11.57670
After
Met vriendelijke groet,
Joris Bo jorisbo@hotmail.com
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Ticker, Thank you very much for your interest. Because I test pedestrian IS_IN another pedestrian I do not want to accidentally test the way against itself So I first must be sure I test a way against a square and nothing else. So i set the jbmsquare if it is an area highway = pedestrian & (mkgmap:mp_created = true | is_closed() = true) {set jbmsquare = true} highway = pedestrian & jbmsquare != true & is_in(highway,pedestrian, any) = true [0x10d0c resolution 24 continue] I use continue because if the processed element would have been a square in stead of a street it should get a polygon fill color in the polygons file later on as well. I’m very pleased with the results sofar. Actually none of the red marked lines is completely within the area, they all go out somewhere. The green ‘dreifaltigkeitsplatz’ is even 95% outside the square but still be considered inside (which is correct from mkgmap point of view and the method ‘any’ ) So ‘only’ the blue marked viktualienmarkt-way is not considered inside where I think it is, just as the others. Kind regards, Joris [cid:image001.jpg@01D62D0B.81F92F90] -----Oorspronkelijk bericht----- Van: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> Namens Ticker Berkin Verzonden: maandag 18 mei 2020 10:20 Aan: Development list for mkgmap <mkgmap-dev@lists.mkgmap.org.uk> Onderwerp: Re: [mkgmap-dev] Explanation of the is_in function Hi Joris couple of questions: 1/ what is jbmsquare and how is it set 2/ what does the rule 'continue' into. It looks like the red lines that have gone are entirely within the pedestrian area, but the blue one isn't. Ticker On Mon, 2020-05-18 at 07:07 +0000, Joris Bo wrote:
Hi
When testing the IS_IN function I get very nice results ! Thank you
very much for this improvement.
Could somebody help me to explain why a certain pedestrian is not
catched by the rules?
Also not a big deal, I’m already happy wit the current results, it is
just for understanding.
I am using pedestrian streets without an outline if crossing
pedestrian areas. 95% works perfectly but some seem to fool me.
Before
(The red lines are nicely replaced in the after situation, but the
blue one is not)
highway = pedestrian & jbmsquare != true & is_in(highway,pedestrian,
any) = true [0x10d0c resolution 24 continue]
area: München Viktualienmarkt:
pedestrian : https://www.openstreetmap.org/way/240014256
square: https://www.openstreetmap.org/relation/7431621#map=19/48.1351
2/11.57670
After
Met vriendelijke groet,
Joris Bo
jorisbo@hotmail.com<mailto:jorisbo@hotmail.com>
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk<mailto:mkgmap-dev@lists.mkgmap.org.uk>
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk<mailto:mkgmap-dev@lists.mkgmap.org.uk> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Joris I can't do anything in the next few days to investigate this but I'll have a look when I can. Ticker

Hi Ticker, Thx for the update, off course no problem. Gr Joris -----Oorspronkelijk bericht----- Van: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> Namens Ticker Berkin Verzonden: dinsdag 19 mei 2020 18:57 Aan: Development list for mkgmap <mkgmap-dev@lists.mkgmap.org.uk> Onderwerp: Re: [mkgmap-dev] Explanation of the is_in function Hi Joris I can't do anything in the next few days to investigate this but I'll have a look when I can. Ticker _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Ticker the problem is in mkgmap. I can reproduce it with the attached simple example. I think the bug is in the distance calculation in isPointInShape(), see attached patch. It returned ON for a point which is clearly inside. I've also changed the way how test points are calculated so that the rounding tolerances are less likely to produce a problem. I don't understand the meaning of the comment // there is a small area between the square EPS_HP*2 and the circle within, where, if polygon vertex and // segments are the other side, it might still be calculated as ON. so maybe my patch makes things worse in other situations? My understanding is that we can use a² + b² = c² , so maybe the comment can be removed as well? Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Joris Bo <jorisbo@hotmail.com> Gesendet: Dienstag, 19. Mai 2020 21:12 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Explanation of the is_in function Hi Ticker, Thx for the update, off course no problem. Gr Joris -----Oorspronkelijk bericht----- Van: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> Namens Ticker Berkin Verzonden: dinsdag 19 mei 2020 18:57 Aan: Development list for mkgmap <mkgmap-dev@lists.mkgmap.org.uk> Onderwerp: Re: [mkgmap-dev] Explanation of the is_in function Hi Joris I can't do anything in the next few days to investigate this but I'll have a look when I can. Ticker _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Gerd Looking at your example, the end point of the line is inside the area, but only by about 1 metre. This is the within the tolerance of a point being considered ON a line with the current algo/EPS. All the other points on the line ON or OUT of the area. Changing the tolerance and/or the type of distance calculation might change the overall answer to be IN & ON & OUT, but consider if the end point of the line was exactly on the edge; the answer would be wrong. The problem really is in the line following shape edge algo that should spot that the line has diverged from the edge into the area. I haven't looked in detail yet at Joris's failures, but did you notice if they were of this pattern, where the line spans the area in one bound? In your change to isPointInShape, you've lost the general case (line not horizontal or vertical): distSqrd = lonDifSqrd * latDifSqrd / (lonDifSqrd + latDifSqrd); Regarding the comment about a small error area on the outside of the polygon vertex where a point will report ON but shouldn't - this area is very small but does exist and so the the comment is valid. Ticker On Wed, 2020-05-20 at 08:53 +0000, Gerd Petermann wrote:
Hi Ticker
the problem is in mkgmap. I can reproduce it with the attached simple example.
I think the bug is in the distance calculation in isPointInShape(), see attached patch. It returned ON for a point which is clearly inside. I've also changed the way how test points are calculated so that the rounding tolerances are less likely to produce a problem. I don't understand the meaning of the comment // there is a small area between the square EPS_HP*2 and the circle within, where, if polygon vertex and // segments are the other side, it might still be calculated as ON. so maybe my patch makes things worse in other situations? My understanding is that we can use a² + b² = c² , so maybe the comment can be removed as well?
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Joris Bo <jorisbo@hotmail.com> Gesendet: Dienstag, 19. Mai 2020 21:12 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Explanation of the is_in function
Hi Ticker,
Thx for the update, off course no problem.
Gr Joris
-----Oorspronkelijk bericht----- Van: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> Namens Ticker Berkin Verzonden: dinsdag 19 mei 2020 18:57 Aan: Development list for mkgmap <mkgmap-dev@lists.mkgmap.org.uk> Onderwerp: Re: [mkgmap-dev] Explanation of the is_in function
Hi Joris
I can't do anything in the next few days to investigate this but I'll have a look when I can.
Ticker
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Ticker, the error is in the formular distSqrd = lonDifSqrd * latDifSqrd / (lonDifSqrd + latDifSqrd); If one of the values is small (< 1) and the other is big, the result is far from being correct. What should this formular express? Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 21. Mai 2020 13:07 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Explanation of the is_in function Hi Gerd Looking at your example, the end point of the line is inside the area, but only by about 1 metre. This is the within the tolerance of a point being considered ON a line with the current algo/EPS. All the other points on the line ON or OUT of the area. Changing the tolerance and/or the type of distance calculation might change the overall answer to be IN & ON & OUT, but consider if the end point of the line was exactly on the edge; the answer would be wrong. The problem really is in the line following shape edge algo that should spot that the line has diverged from the edge into the area. I haven't looked in detail yet at Joris's failures, but did you notice if they were of this pattern, where the line spans the area in one bound? In your change to isPointInShape, you've lost the general case (line not horizontal or vertical): distSqrd = lonDifSqrd * latDifSqrd / (lonDifSqrd + latDifSqrd); Regarding the comment about a small error area on the outside of the polygon vertex where a point will report ON but shouldn't - this area is very small but does exist and so the the comment is valid. Ticker On Wed, 2020-05-20 at 08:53 +0000, Gerd Petermann wrote:
Hi Ticker
the problem is in mkgmap. I can reproduce it with the attached simple example.
I think the bug is in the distance calculation in isPointInShape(), see attached patch. It returned ON for a point which is clearly inside. I've also changed the way how test points are calculated so that the rounding tolerances are less likely to produce a problem. I don't understand the meaning of the comment // there is a small area between the square EPS_HP*2 and the circle within, where, if polygon vertex and // segments are the other side, it might still be calculated as ON. so maybe my patch makes things worse in other situations? My understanding is that we can use a² + b² = c² , so maybe the comment can be removed as well?
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Joris Bo <jorisbo@hotmail.com> Gesendet: Dienstag, 19. Mai 2020 21:12 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Explanation of the is_in function
Hi Ticker,
Thx for the update, off course no problem.
Gr Joris
-----Oorspronkelijk bericht----- Van: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> Namens Ticker Berkin Verzonden: dinsdag 19 mei 2020 18:57 Aan: Development list for mkgmap <mkgmap-dev@lists.mkgmap.org.uk> Onderwerp: Re: [mkgmap-dev] Explanation of the is_in function
Hi Joris
I can't do anything in the next few days to investigate this but I'll have a look when I can.
Ticker
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Gerd The variables and calculations are all double precision floating, so the only danger I see is exponent under or overflow when squaring lon/latDif. Does java give a run-time error for this? Apart from this, the accuracy should be good. If considering re-writing the general case as: distSqrd = lonDifSqrd / (lonDifSqrd + latDifSqrd) * latDifSqrd; it makes underflow more likely. As the line gets closer to horizontal or vertical then the answer tends towards the smaller of the values, so the testing could be changed to: if (abs(lonDif)) < someSmallAmount) distSqrd = latDifSqrd; else if (abs(latDif) < someSmallAmount) distSqrd = lonDifSqrd; else distSqrd = lonDifSqrd * latDifSqrd / (lonDifSqrd + latDifSqrd); Have you seen evidence that this is a problem? Ticker On Thu, 2020-05-21 at 11:15 +0000, Gerd Petermann wrote:
Hi Ticker,
the error is in the formular distSqrd = lonDifSqrd * latDifSqrd / (lonDifSqrd + latDifSqrd);
If one of the values is small (< 1) and the other is big, the result is far from being correct. What should this formular express?
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 21. Mai 2020 13:07 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Explanation of the is_in function
Hi Gerd
Looking at your example, the end point of the line is inside the area, but only by about 1 metre. This is the within the tolerance of a point being considered ON a line with the current algo/EPS. All the other points on the line ON or OUT of the area.
Changing the tolerance and/or the type of distance calculation might change the overall answer to be IN & ON & OUT, but consider if the end point of the line was exactly on the edge; the answer would be wrong.
The problem really is in the line following shape edge algo that should spot that the line has diverged from the edge into the area.
I haven't looked in detail yet at Joris's failures, but did you notice if they were of this pattern, where the line spans the area in one bound?
In your change to isPointInShape, you've lost the general case (line not horizontal or vertical): distSqrd = lonDifSqrd * latDifSqrd / (lonDifSqrd + latDifSqrd);
Regarding the comment about a small error area on the outside of the polygon vertex where a point will report ON but shouldn't - this area is very small but does exist and so the the comment is valid.
Ticker
On Wed, 2020-05-20 at 08:53 +0000, Gerd Petermann wrote:
Hi Ticker
the problem is in mkgmap. I can reproduce it with the attached simple example.
I think the bug is in the distance calculation in isPointInShape(), see attached patch. It returned ON for a point which is clearly inside. I've also changed the way how test points are calculated so that the rounding tolerances are less likely to produce a problem. I don't understand the meaning of the comment // there is a small area between the square EPS_HP*2 and the circle within, where, if polygon vertex and // segments are the other side, it might still be calculated as ON. so maybe my patch makes things worse in other situations? My understanding is that we can use a² + b² = c² , so maybe the comment can be removed as well?
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Joris Bo <jorisbo@hotmail.com> Gesendet: Dienstag, 19. Mai 2020 21:12 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Explanation of the is_in function
Hi Ticker,
Thx for the update, off course no problem.
Gr Joris
-----Oorspronkelijk bericht----- Van: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> Namens Ticker Berkin Verzonden: dinsdag 19 mei 2020 18:57 Aan: Development list for mkgmap <mkgmap-dev@lists.mkgmap.org.uk> Onderwerp: Re: [mkgmap-dev] Explanation of the is_in function
Hi Joris
I can't do anything in the next few days to investigate this but I'll have a look when I can.
Ticker
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Gerd Do I mean this - let me thing about it again! Ticker On Thu, 2020-05-21 at 13:12 +0100, Ticker Berkin wrote:
Hi Gerd
The variables and calculations are all double precision floating, so the only danger I see is exponent under or overflow when squaring lon/latDif. Does java give a run-time error for this? Apart from this, the accuracy should be good.
If considering re-writing the general case as: distSqrd = lonDifSqrd / (lonDifSqrd + latDifSqrd) * latDifSqrd; it makes underflow more likely.
As the line gets closer to horizontal or vertical then the answer tends towards the smaller of the values, so the testing could be changed to:
if (abs(lonDif)) < someSmallAmount) distSqrd = latDifSqrd; else if (abs(latDif) < someSmallAmount) distSqrd = lonDifSqrd; else distSqrd = lonDifSqrd * latDifSqrd / (lonDifSqrd + latDifSqrd);
Have you seen evidence that this is a problem?
Ticker
On Thu, 2020-05-21 at 11:15 +0000, Gerd Petermann wrote:
Hi Ticker,
the error is in the formular distSqrd = lonDifSqrd * latDifSqrd / (lonDifSqrd + latDifSqrd);
If one of the values is small (< 1) and the other is big, the result is far from being correct. What should this formular express?
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 21. Mai 2020 13:07 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Explanation of the is_in function
Hi Gerd
Looking at your example, the end point of the line is inside the area, but only by about 1 metre. This is the within the tolerance of a point being considered ON a line with the current algo/EPS. All the other points on the line ON or OUT of the area.
Changing the tolerance and/or the type of distance calculation might change the overall answer to be IN & ON & OUT, but consider if the end point of the line was exactly on the edge; the answer would be wrong.
The problem really is in the line following shape edge algo that should spot that the line has diverged from the edge into the area.
I haven't looked in detail yet at Joris's failures, but did you notice if they were of this pattern, where the line spans the area in one bound?
In your change to isPointInShape, you've lost the general case (line not horizontal or vertical): distSqrd = lonDifSqrd * latDifSqrd / (lonDifSqrd + latDifSqrd);
Regarding the comment about a small error area on the outside of the polygon vertex where a point will report ON but shouldn't - this area is very small but does exist and so the the comment is valid.
Ticker
On Wed, 2020-05-20 at 08:53 +0000, Gerd Petermann wrote:
Hi Ticker
the problem is in mkgmap. I can reproduce it with the attached simple example.
I think the bug is in the distance calculation in isPointInShape(), see attached patch. It returned ON for a point which is clearly inside. I've also changed the way how test points are calculated so that the rounding tolerances are less likely to produce a problem. I don't understand the meaning of the comment // there is a small area between the square EPS_HP*2 and the circle within, where, if polygon vertex and // segments are the other side, it might still be calculated as ON. so maybe my patch makes things worse in other situations? My understanding is that we can use a² + b² = c² , so maybe the comment can be removed as well?
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Joris Bo <jorisbo@hotmail.com> Gesendet: Dienstag, 19. Mai 2020 21:12 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Explanation of the is_in function
Hi Ticker,
Thx for the update, off course no problem.
Gr Joris
-----Oorspronkelijk bericht----- Van: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> Namens Ticker Berkin Verzonden: dinsdag 19 mei 2020 18:57 Aan: Development list for mkgmap <mkgmap-dev@lists.mkgmap.org.uk> Onderwerp: Re: [mkgmap-dev] Explanation of the is_in function
Hi Joris
I can't do anything in the next few days to investigate this but I'll have a look when I can.
Ticker
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Gerd Considering an almost vertical in highPrec units, the min lat difference is 1, the max lon difference is the longest realistic line in a tile, call it BIG Taking a node near this line, lonDif will be within a few factors of BIG and squaring it won't be a problem. latDif will be the horizontal difference to the line -1..+1. This could be almost zero and squaring it could cause underflow. Also, if exactly zero, it will confuse the test for an exactly vertical line. Same considerations apply to a horizontal line. I'll do a patch to fix these 2 issues, but I don't think it will solve Joris's problem Ticker On Thu, 2020-05-21 at 13:16 +0100, Ticker Berkin wrote:
Hi Gerd
Do I mean this - let me thing about it again!
Ticker
On Thu, 2020-05-21 at 13:12 +0100, Ticker Berkin wrote:
Hi Gerd
The variables and calculations are all double precision floating, so the only danger I see is exponent under or overflow when squaring lon/latDif. Does java give a run-time error for this? Apart from this, the accuracy should be good.
If considering re-writing the general case as: distSqrd = lonDifSqrd / (lonDifSqrd + latDifSqrd) * latDifSqrd; it makes underflow more likely.
As the line gets closer to horizontal or vertical then the answer tends towards the smaller of the values, so the testing could be changed to:
if (abs(lonDif)) < someSmallAmount) distSqrd = latDifSqrd; else if (abs(latDif) < someSmallAmount) distSqrd = lonDifSqrd; else distSqrd = lonDifSqrd * latDifSqrd / (lonDifSqrd + latDifSqrd);
Have you seen evidence that this is a problem?
Ticker
On Thu, 2020-05-21 at 11:15 +0000, Gerd Petermann wrote:
Hi Ticker,
the error is in the formular distSqrd = lonDifSqrd * latDifSqrd / (lonDifSqrd + latDifSqrd);
If one of the values is small (< 1) and the other is big, the result is far from being correct. What should this formular express?
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 21. Mai 2020 13:07 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Explanation of the is_in function
Hi Gerd
Looking at your example, the end point of the line is inside the area, but only by about 1 metre. This is the within the tolerance of a point being considered ON a line with the current algo/EPS. All the other points on the line ON or OUT of the area.
Changing the tolerance and/or the type of distance calculation might change the overall answer to be IN & ON & OUT, but consider if the end point of the line was exactly on the edge; the answer would be wrong.
The problem really is in the line following shape edge algo that should spot that the line has diverged from the edge into the area.
I haven't looked in detail yet at Joris's failures, but did you notice if they were of this pattern, where the line spans the area in one bound?
In your change to isPointInShape, you've lost the general case (line not horizontal or vertical): distSqrd = lonDifSqrd * latDifSqrd / (lonDifSqrd + latDifSqrd);
Regarding the comment about a small error area on the outside of the polygon vertex where a point will report ON but shouldn't - this area is very small but does exist and so the the comment is valid.
Ticker
On Wed, 2020-05-20 at 08:53 +0000, Gerd Petermann wrote:
Hi Ticker
the problem is in mkgmap. I can reproduce it with the attached simple example.
I think the bug is in the distance calculation in isPointInShape(), see attached patch. It returned ON for a point which is clearly inside. I've also changed the way how test points are calculated so that the rounding tolerances are less likely to produce a problem. I don't understand the meaning of the comment // there is a small area between the square EPS_HP*2 and the circle within, where, if polygon vertex and // segments are the other side, it might still be calculated as ON. so maybe my patch makes things worse in other situations? My understanding is that we can use a² + b² = c² , so maybe the comment can be removed as well?
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Joris Bo <jorisbo@hotmail.com> Gesendet: Dienstag, 19. Mai 2020 21:12 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Explanation of the is_in function
Hi Ticker,
Thx for the update, off course no problem.
Gr Joris
-----Oorspronkelijk bericht----- Van: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> Namens Ticker Berkin Verzonden: dinsdag 19 mei 2020 18:57 Aan: Development list for mkgmap < mkgmap-dev@lists.mkgmap.org.uk> Onderwerp: Re: [mkgmap-dev] Explanation of the is_in function
Hi Joris
I can't do anything in the next few days to investigate this but I'll have a look when I can.
Ticker
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Gerd Here is patch that prevents possible underflow when node is very close to an almost horizontal or vertical line and incorrect results when exactly on this line. Ticker

Hi Ticker, the patched version still returns ON for a Coord which is not ON and thus doesn't work with my example. The result doesn't depend on the position of the last point of the way as long as it is builds a nearly or exactly straight line with two nodes of the shape. Your algorithm returns true for each such point, even when it is 100m away from any shape vertex. See my new example where A,B and C build a straight line. Another node is very close to the edge but still returns IN (OK) Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 21. Mai 2020 17:07 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Explanation of the is_in function Hi Gerd Here is patch that prevents possible underflow when node is very close to an almost horizontal or vertical line and incorrect results when exactly on this line. Ticker

Hi Gerd I think I understand what is going wrong. I'll do another patch tomorrow. Ticker On Fri, 2020-05-22 at 13:36 +0000, Gerd Petermann wrote:
Hi Ticker,
the patched version still returns ON for a Coord which is not ON and thus doesn't work with my example. The result doesn't depend on the position of the last point of the way as long as it is builds a nearly or exactly straight line with two nodes of the shape.
Your algorithm returns true for each such point, even when it is 100m away from any shape vertex. See my new example where A,B and C build a straight line. Another node is very close to the edge but still returns IN (OK)
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 21. Mai 2020 17:07 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Explanation of the is_in function
Hi Gerd
Here is patch that prevents possible underflow when node is very close to an almost horizontal or vertical line and incorrect results when exactly on this line.
Ticker
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Gerd Here is a patch that should fix the problem - In the original code I got carried away with the symmetry of Lat/Lon handling in the distance calculation but the set-up for the crossing calculation isn't symmetric! I've also explained the ON error area more carefully and used INFINITY instead of NaN because that is the horizontal distance where a line through the node would meet a horizontal polygon side. Ticker On Fri, 2020-05-22 at 21:44 +0100, Ticker Berkin wrote:
Hi Gerd
I think I understand what is going wrong. I'll do another patch tomorrow.
Ticker
On Fri, 2020-05-22 at 13:36 +0000, Gerd Petermann wrote:
Hi Ticker,
the patched version still returns ON for a Coord which is not ON and thus doesn't work with my example. The result doesn't depend on the position of the last point of the way as long as it is builds a nearly or exactly straight line with two nodes of the shape.
Your algorithm returns true for each such point, even when it is 100m away from any shape vertex. See my new example where A,B and C build a straight line. Another node is very close to the edge but still returns IN (OK)
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 21. Mai 2020 17:07 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Explanation of the is_in function
Hi Gerd
Here is patch that prevents possible underflow when node is very close to an almost horizontal or vertical line and incorrect results when exactly on this line.
Ticker
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Ticker, yes, the patch seems to fix the problems regarding isPointInShape(). I've also changed the code which calculates new points (pTest) near points which are known to be ON. This is still just a good guess and it is easy to construct test cases where a shape has a sharp angle so that it is nearly impossible to find a point which is IN but not inside the EPS halo and thus calculated as ON. Let's see if this matters... Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Samstag, 23. Mai 2020 12:01 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Explanation of the is_in function Hi Gerd Here is a patch that should fix the problem - In the original code I got carried away with the symmetry of Lat/Lon handling in the distance calculation but the set-up for the crossing calculation isn't symmetric! I've also explained the ON error area more carefully and used INFINITY instead of NaN because that is the horizontal distance where a line through the node would meet a horizontal polygon side. Ticker On Fri, 2020-05-22 at 21:44 +0100, Ticker Berkin wrote:
Hi Gerd
I think I understand what is going wrong. I'll do another patch tomorrow.
Ticker
On Fri, 2020-05-22 at 13:36 +0000, Gerd Petermann wrote:
Hi Ticker,
the patched version still returns ON for a Coord which is not ON and thus doesn't work with my example. The result doesn't depend on the position of the last point of the way as long as it is builds a nearly or exactly straight line with two nodes of the shape.
Your algorithm returns true for each such point, even when it is 100m away from any shape vertex. See my new example where A,B and C build a straight line. Another node is very close to the edge but still returns IN (OK)
Gerd
________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 21. Mai 2020 17:07 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Explanation of the is_in function
Hi Gerd
Here is patch that prevents possible underflow when node is very close to an almost horizontal or vertical line and incorrect results when exactly on this line.
Ticker
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Maybe it helps if I say that my example is a multipolygon square with a lot of holes in it. The 'wrong' line somehow bends towards on of the holes. But then still at least 4 out of 6 lines around do perfectly wat is meant to be, 1 is considered 'inside' which is true but only for a certain 10 meters where 60 meters are outside. Bad luck for me but software is oke. The line which is considered 'outside' is actually inside for 60 meters and only outside for 5? meters But i just see that it also shares 3 nodes in a row with the border of the square. [cid:image003.jpg@01D62F86.91D50BF0] The test area Spot https://www.openstreetmap.org/#map=18/48.13510/11.57713 Square https://www.openstreetmap.org/relation/7431621#map=18/48.13532/11.57615 Line ok https://www.openstreetmap.org/way/240014251 Line ok https://www.openstreetmap.org/way/240014254 Line ok https://www.openstreetmap.org/way/240014253 Line not ok https://www.openstreetmap.org/way/240014256 Line ok (but more out then in) https://www.openstreetmap.org/way/23447316 Line ok https://www.openstreetmap.org/way/240014255 -----Oorspronkelijk bericht----- Van: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> Namens Gerd Petermann Verzonden: donderdag 21 mei 2020 13:16 Aan: Development list for mkgmap <mkgmap-dev@lists.mkgmap.org.uk> Onderwerp: Re: [mkgmap-dev] Explanation of the is_in function Hi Ticker, the error is in the formular distSqrd = lonDifSqrd * latDifSqrd / (lonDifSqrd + latDifSqrd); If one of the values is small (< 1) and the other is big, the result is far from being correct. What should this formular express? Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 21. Mai 2020 13:07 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Explanation of the is_in function Hi Gerd Looking at your example, the end point of the line is inside the area, but only by about 1 metre. This is the within the tolerance of a point being considered ON a line with the current algo/EPS. All the other points on the line ON or OUT of the area. Changing the tolerance and/or the type of distance calculation might change the overall answer to be IN & ON & OUT, but consider if the end point of the line was exactly on the edge; the answer would be wrong. The problem really is in the line following shape edge algo that should spot that the line has diverged from the edge into the area. I haven't looked in detail yet at Joris's failures, but did you notice if they were of this pattern, where the line spans the area in one bound? In your change to isPointInShape, you've lost the general case (line not horizontal or vertical): distSqrd = lonDifSqrd * latDifSqrd / (lonDifSqrd + latDifSqrd); Regarding the comment about a small error area on the outside of the polygon vertex where a point will report ON but shouldn't - this area is very small but does exist and so the the comment is valid. Ticker On Wed, 2020-05-20 at 08:53 +0000, Gerd Petermann wrote:
Hi Ticker
the problem is in mkgmap. I can reproduce it with the attached simple
example.
I think the bug is in the distance calculation in isPointInShape(),
see attached patch. It returned ON for a point which is clearly
inside.
I've also changed the way how test points are calculated so that the
rounding tolerances are less likely to produce a problem.
I don't understand the meaning of the comment
// there is a small area
between the square EPS_HP*2 and the circle within, where, if polygon
vertex and
// segments are the other
side, it might still be calculated as ON.
so maybe my patch makes things worse in other situations?
My understanding is that we can use a² + b² = c² , so maybe the
comment can be removed as well?
Gerd
________________________________________
Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag
von Joris Bo <jorisbo@hotmail.com>
Gesendet: Dienstag, 19. Mai 2020 21:12
An: Development list for mkgmap
Betreff: Re: [mkgmap-dev] Explanation of the is_in function
Hi Ticker,
Thx for the update, off course no problem.
Gr Joris
-----Oorspronkelijk bericht-----
Van: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> Namens Ticker
Berkin
Verzonden: dinsdag 19 mei 2020 18:57
Aan: Development list for mkgmap <mkgmap-dev@lists.mkgmap.org.uk>
Onderwerp: Re: [mkgmap-dev] Explanation of the is_in function
Hi Joris
I can't do anything in the next few days to investigate this but I'll
have a look when I can.
Ticker
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
participants (3)
-
Gerd Petermann
-
Joris Bo
-
Ticker Berkin