[mkgmap-dev] Explanation of the is_in function

Thu May 21 15:10:21 BST 2020

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 at lists.mkgmap.org.uk> im
> > > Auftrag
> > > von Ticker Berkin <rwb-mkgmap at 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 at lists.mkgmap.org.uk> im
> > > > Auftrag
> > > > von Joris Bo <jorisbo at 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 at lists.mkgmap.org.uk> Namens
> > > > Ticker Berkin
> > > > Verzonden: dinsdag 19 mei 2020 18:57
> > > > Aan: Development list for mkgmap <
> > > > mkgmap-dev at 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 at lists.mkgmap.org.uk
> > > > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > > > _______________________________________________
> > > > mkgmap-dev mailing list
> > > > mkgmap-dev at lists.mkgmap.org.uk
> > > > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > > > _______________________________________________
> > > > mkgmap-dev mailing list
> > > > mkgmap-dev at lists.mkgmap.org.uk
> > > > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > > _______________________________________________
> > > mkgmap-dev mailing list
> > > mkgmap-dev at lists.mkgmap.org.uk
> > > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > > _______________________________________________
> > > mkgmap-dev mailing list
> > > mkgmap-dev at lists.mkgmap.org.uk
> > > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > _______________________________________________
> > mkgmap-dev mailing list
> > mkgmap-dev at lists.mkgmap.org.uk
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev