
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