[mkgmap-dev] Explanation of the is_in function

Thu May 21 13:12:06 BST 2020

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