[mkgmap-dev] Explanation of the is_in function

Thu May 21 13:16:58 BST 2020

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