# [mkgmap-dev] Explanation of the is_in function

From Joris Bo jorisbo at hotmail.com on Thu May 21 14:43:36 BST 2020

```Hi

Maybe it helps if I say that my example is a multipolygon square with a lot of holes in it.

The 'wrong' line somehow bends towards on of the holes.

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.

The line which is considered 'outside'  is actually inside for 60 meters and only outside for 5? meters

But i just see that it also shares 3 nodes in a row with the border of the square.

[cid:image003.jpg at 01D62F86.91D50BF0]

The test area

Spot     https://www.openstreetmap.org/#map=18/48.13510/11.57713

Square https://www.openstreetmap.org/relation/7431621#map=18/48.13532/11.57615

Line ok           https://www.openstreetmap.org/way/240014251

Line ok           https://www.openstreetmap.org/way/240014254

Line ok           https://www.openstreetmap.org/way/240014253

Line not ok          https://www.openstreetmap.org/way/240014256

Line ok (but more out then in) https://www.openstreetmap.org/way/23447316

Line ok           https://www.openstreetmap.org/way/240014255

-----Oorspronkelijk bericht-----
Van: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> Namens Gerd Petermann
Verzonden: donderdag 21 mei 2020 13:16
Aan: Development list for mkgmap <mkgmap-dev at lists.mkgmap.org.uk>
Onderwerp: Re: [mkgmap-dev] Explanation of the is_in function

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20200521/3af9bf7c/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image003.jpg
Type: image/jpeg
Size: 63053 bytes
Desc: image003.jpg
URL: <http://www.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20200521/3af9bf7c/attachment-0001.jpg>
```