<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
p.MsoPlainText, li.MsoPlainText, div.MsoPlainText
{mso-style-priority:99;
mso-style-link:"Tekst zonder opmaak Char";
margin:0cm;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Arial",sans-serif;
mso-fareast-language:EN-US;}
span.TekstzonderopmaakChar
{mso-style-name:"Tekst zonder opmaak Char";
mso-style-priority:99;
mso-style-link:"Tekst zonder opmaak";
font-family:"Arial",sans-serif;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:70.85pt 70.85pt 70.85pt 70.85pt;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="NL" link="#0563C1" vlink="#954F72">
<div class="WordSection1">
<p class="MsoPlainText">Hi <o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText"><span lang="EN-GB">Maybe it helps if I say that my example is a multipolygon square with a lot of holes in it.<o:p></o:p></span></p>
<p class="MsoPlainText"><span lang="EN-GB">The 'wrong' line somehow bends towards on of the holes.<o:p></o:p></span></p>
<p class="MsoPlainText"><span lang="EN-GB">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.<o:p></o:p></span></p>
<p class="MsoPlainText"><span lang="EN-GB">The line which is considered 'outside' is actually inside for 60 meters and only outside for 5? meters<o:p></o:p></span></p>
<p class="MsoPlainText"><span lang="EN-GB">But i just see that it also shares 3 nodes in a row with the border of the square.<o:p></o:p></span></p>
<p class="MsoPlainText"><span lang="EN-GB"><o:p> </o:p></span></p>
<p class="MsoPlainText"><span lang="EN-GB"><img width="839" height="258" style="width:8.7343in;height:2.6822in" id="Afbeelding_x0020_1" src="cid:image003.jpg@01D62F86.91D50BF0"></span><span lang="EN-GB"><o:p></o:p></span></p>
<p class="MsoPlainText"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoPlainText"><span lang="EN-GB">The test area<o:p></o:p></span></p>
<p class="MsoPlainText"><span lang="EN-GB">Spot <a href="https://www.openstreetmap.org/#map=18/48.13510/11.57713">
https://www.openstreetmap.org/#map=18/48.13510/11.57713</a><o:p></o:p></span></p>
<p class="MsoPlainText"><span lang="EN-GB">Square </span><a href="https://www.openstreetmap.org/relation/7431621#map=18/48.13532/11.57615"><span lang="EN-GB">https://www.openstreetmap.org/relation/7431621#map=18/48.13532/11.57615</span></a><o:p></o:p></p>
<p class="MsoPlainText"><span lang="EN-GB">Line ok </span><a href="https://www.openstreetmap.org/way/240014251"><span lang="EN-GB">https://www.openstreetmap.org/way/240014251</span></a><o:p></o:p></p>
<p class="MsoPlainText"><span lang="EN-GB">Line ok </span><a href="https://www.openstreetmap.org/way/240014254"><span lang="EN-GB">https://www.openstreetmap.org/way/240014254</span></a><o:p></o:p></p>
<p class="MsoPlainText"><span lang="EN-GB">Line ok </span><a href="https://www.openstreetmap.org/way/240014253"><span lang="EN-GB">https://www.openstreetmap.org/way/240014253</span></a><o:p></o:p></p>
<p class="MsoPlainText"><span lang="EN-GB">Line not ok </span><a href="https://www.openstreetmap.org/way/240014256"><span lang="EN-GB">https://www.openstreetmap.org/way/240014256</span></a><span lang="EN-GB"><o:p></o:p></span></p>
<p class="MsoPlainText"><span lang="EN-GB">Line ok (but more out then in) </span>
<a href="https://www.openstreetmap.org/way/23447316"><span lang="EN-GB">https://www.openstreetmap.org/way/23447316</span></a><o:p></o:p></p>
<p class="MsoPlainText"><span lang="EN-GB">Line ok </span><a href="https://www.openstreetmap.org/way/240014255"><span lang="EN-GB">https://www.openstreetmap.org/way/240014255</span></a><o:p></o:p></p>
<p class="MsoPlainText"><span lang="EN-GB"><o:p> </o:p></span></p>
<p class="MsoPlainText"><span lang="EN-GB"><o:p></o:p></span></p>
<p class="MsoPlainText"><span lang="EN-GB"><o:p> </o:p></span></p>
<p class="MsoPlainText"><span style="mso-fareast-language:NL">-----Oorspronkelijk bericht-----<br>
Van: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> Namens Gerd Petermann<br>
Verzonden: donderdag 21 mei 2020 13:16<br>
Aan: Development list for mkgmap <mkgmap-dev@lists.mkgmap.org.uk><br>
Onderwerp: Re: [mkgmap-dev] Explanation of the is_in function</span></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">Hi Ticker,<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">the error is in the formular<o:p></o:p></p>
<p class="MsoPlainText">distSqrd = lonDifSqrd * latDifSqrd / (lonDifSqrd + latDifSqrd);<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">If one of the values is small (< 1) and the other is big, the result is far from being correct.<o:p></o:p></p>
<p class="MsoPlainText">What should this formular express?<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">Gerd<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">________________________________________<o:p></o:p></p>
<p class="MsoPlainText">Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk><o:p></o:p></p>
<p class="MsoPlainText">Gesendet: Donnerstag, 21. Mai 2020 13:07<o:p></o:p></p>
<p class="MsoPlainText">An: Development list for mkgmap<o:p></o:p></p>
<p class="MsoPlainText">Betreff: Re: [mkgmap-dev] Explanation of the is_in function<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">Hi Gerd<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">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.<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">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.<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">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.<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">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?<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">In your change to isPointInShape, you've lost the general case (line not horizontal or vertical):<o:p></o:p></p>
<p class="MsoPlainText"> distSqrd = lonDifSqrd * latDifSqrd / (lonDifSqrd + latDifSqrd);<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">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.<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">Ticker<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">On Wed, 2020-05-20 at 08:53 +0000, Gerd Petermann wrote:<o:p></o:p></p>
<p class="MsoPlainText">> Hi Ticker<o:p></o:p></p>
<p class="MsoPlainText">><o:p> </o:p></p>
<p class="MsoPlainText">> the problem is in mkgmap. I can reproduce it with the attached simple
<o:p></o:p></p>
<p class="MsoPlainText">> example.<o:p></o:p></p>
<p class="MsoPlainText">><o:p> </o:p></p>
<p class="MsoPlainText">> I think the bug is in the distance calculation in isPointInShape(),
<o:p></o:p></p>
<p class="MsoPlainText">> see attached patch. It returned ON for a point which is clearly
<o:p></o:p></p>
<p class="MsoPlainText">> inside.<o:p></o:p></p>
<p class="MsoPlainText">> I've also changed the way how test points are calculated so that the
<o:p></o:p></p>
<p class="MsoPlainText">> rounding tolerances are less likely to produce a problem.<o:p></o:p></p>
<p class="MsoPlainText">> I don't understand the meaning of the comment<o:p></o:p></p>
<p class="MsoPlainText">> // there is a small area
<o:p></o:p></p>
<p class="MsoPlainText">> between the square EPS_HP*2 and the circle within, where, if polygon
<o:p></o:p></p>
<p class="MsoPlainText">> vertex and<o:p></o:p></p>
<p class="MsoPlainText">> // segments are the other
<o:p></o:p></p>
<p class="MsoPlainText">> side, it might still be calculated as ON.<o:p></o:p></p>
<p class="MsoPlainText">> so maybe my patch makes things worse in other situations?<o:p></o:p></p>
<p class="MsoPlainText">> My understanding is that we can use a² + b² = c² , so maybe the
<o:p></o:p></p>
<p class="MsoPlainText">> comment can be removed as well?<o:p></o:p></p>
<p class="MsoPlainText">><o:p> </o:p></p>
<p class="MsoPlainText">> Gerd<o:p></o:p></p>
<p class="MsoPlainText">><o:p> </o:p></p>
<p class="MsoPlainText">> ________________________________________<o:p></o:p></p>
<p class="MsoPlainText">> Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag
<o:p></o:p></p>
<p class="MsoPlainText">> von Joris Bo <jorisbo@hotmail.com><o:p></o:p></p>
<p class="MsoPlainText">> Gesendet: Dienstag, 19. Mai 2020 21:12<o:p></o:p></p>
<p class="MsoPlainText">> An: Development list for mkgmap<o:p></o:p></p>
<p class="MsoPlainText">> Betreff: Re: [mkgmap-dev] Explanation of the is_in function<o:p></o:p></p>
<p class="MsoPlainText">><o:p> </o:p></p>
<p class="MsoPlainText">> Hi Ticker,<o:p></o:p></p>
<p class="MsoPlainText">><o:p> </o:p></p>
<p class="MsoPlainText">> Thx for the update, off course no problem.<o:p></o:p></p>
<p class="MsoPlainText">><o:p> </o:p></p>
<p class="MsoPlainText">> Gr Joris<o:p></o:p></p>
<p class="MsoPlainText">><o:p> </o:p></p>
<p class="MsoPlainText">><o:p> </o:p></p>
<p class="MsoPlainText">><o:p> </o:p></p>
<p class="MsoPlainText">> -----Oorspronkelijk bericht-----<o:p></o:p></p>
<p class="MsoPlainText">> Van: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> Namens Ticker
<o:p></o:p></p>
<p class="MsoPlainText">> Berkin<o:p></o:p></p>
<p class="MsoPlainText">> Verzonden: dinsdag 19 mei 2020 18:57<o:p></o:p></p>
<p class="MsoPlainText">> Aan: Development list for mkgmap <mkgmap-dev@lists.mkgmap.org.uk><o:p></o:p></p>
<p class="MsoPlainText">> Onderwerp: Re: [mkgmap-dev] Explanation of the is_in function<o:p></o:p></p>
<p class="MsoPlainText">><o:p> </o:p></p>
<p class="MsoPlainText">> Hi Joris<o:p></o:p></p>
<p class="MsoPlainText">><o:p> </o:p></p>
<p class="MsoPlainText">> I can't do anything in the next few days to investigate this but I'll
<o:p></o:p></p>
<p class="MsoPlainText">> have a look when I can.<o:p></o:p></p>
<p class="MsoPlainText">><o:p> </o:p></p>
<p class="MsoPlainText">> Ticker<o:p></o:p></p>
<p class="MsoPlainText">><o:p> </o:p></p>
<p class="MsoPlainText">><o:p> </o:p></p>
<p class="MsoPlainText">> _______________________________________________<o:p></o:p></p>
<p class="MsoPlainText">> mkgmap-dev mailing list<o:p></o:p></p>
<p class="MsoPlainText">> mkgmap-dev@lists.mkgmap.org.uk<o:p></o:p></p>
<p class="MsoPlainText">> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev<o:p></o:p></p>
<p class="MsoPlainText">> _______________________________________________<o:p></o:p></p>
<p class="MsoPlainText">> mkgmap-dev mailing list<o:p></o:p></p>
<p class="MsoPlainText">> mkgmap-dev@lists.mkgmap.org.uk<o:p></o:p></p>
<p class="MsoPlainText">> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev<o:p></o:p></p>
<p class="MsoPlainText">> _______________________________________________<o:p></o:p></p>
<p class="MsoPlainText">> mkgmap-dev mailing list<o:p></o:p></p>
<p class="MsoPlainText">> mkgmap-dev@lists.mkgmap.org.uk<o:p></o:p></p>
<p class="MsoPlainText">> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev<o:p></o:p></p>
<p class="MsoPlainText">_______________________________________________<o:p></o:p></p>
<p class="MsoPlainText">mkgmap-dev mailing list<o:p></o:p></p>
<p class="MsoPlainText">mkgmap-dev@lists.mkgmap.org.uk<o:p></o:p></p>
<p class="MsoPlainText">http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev<o:p></o:p></p>
<p class="MsoPlainText">_______________________________________________<o:p></o:p></p>
<p class="MsoPlainText">mkgmap-dev mailing list<o:p></o:p></p>
<p class="MsoPlainText">mkgmap-dev@lists.mkgmap.org.uk<o:p></o:p></p>
<p class="MsoPlainText">http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev<o:p></o:p></p>
</div>
</body>
</html>