[mkgmap-dev] Allow blanks in function parameters

Wed Jan 8 18:52:54 GMT 2020

Hi Ticker,

 java.awt.Polygon uses the same insideness logic as  java.awt.Area. I doesn't handle points on boundaries in a way that we need,
it returns true for some and false for others. See Definition of insideness in https://docs.oracle.com/javase/8/docs/api/java/awt/Shape.html
I want to get rid of this test.

I think the 3x3 matrix is used to avoid intersection tests which would not find an intersection. No idea if it works well or if it really improves performance.

Gerd

________________________________________
Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap at jagit.co.uk>
Gesendet: Mittwoch, 8. Januar 2020 19:27
An: mkgmap development
Betreff: Re: [mkgmap-dev] Allow blanks in function parameters

Hi Gerd

For the POINT test, the MultiPolygonRelation code already seems to be
doing quite a lot of this with "polygon...contains(highPrecLon,
highPrecLat)", presumably from java.awt.Polygon.

Failing that, shouldn't the simpler Crossing Number test cn_PnPoly() be
sufficient, applying it one-at-a-time to each target polygon?
But even this looks less efficient than it could be because all the
segments in the other plane that are totally to the right of the point
can increment "cn" without bothering to calculate the intersection.

I haven't been been able to fathom the 3-by-3 matrix, but I feel there
are some assumptions being made and cases the code doesn't handled
correctly.

I can almost imagine the code for dealing with just 1 polygon that
doesn't run back on itself, using something like the spike detection
algorithm at the point when segments touch to tell if lines are
following the same path or going inwards or outwards from each other by
keeping track of sign of the triangle area, with ~0 being ON. If the
signs change, then line/polygon is OUT-ON-IN the target. If the sign is
consistent, then there is no crossing and it is OUT-ON or ON-IN.

I doubt that this helps you much.

Ticker

On Wed, 2020-01-08 at 17:28 +0000, Gerd Petermann wrote:
> Hi Ticker,
>
> thanks for the patch, is committed.
> I think I've found a solution for the insideness tests, but the code
> needs some cleanup.
> Probably a first working version tomorrow...
>
> Gerd
>
> ________________________________________
> Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag
> von Ticker Berkin <rwb-mkgmap at jagit.co.uk>
> Gesendet: Mittwoch, 8. Januar 2020 14:37
> An: mkgmap development
> Betreff: Re: [mkgmap-dev] Allow blanks in function parameters
>
> Hi Gerd
>
> Attached is a patch for the function args + minor fix/tidy-up to
> StyledConverter that stops it doing extra work for wayRules
>
> I need to think about the rest, but I imagine all the special cases
> where a node of a line/polygon touches a node of maybe many polygons
> is
> about impossible to decipher!
>
> Also major difficulties if there are overlapping polygons that match
> the tagKey/Value
>
> Ticker
>
> On Wed, 2020-01-08 at 13:12 +0000, Gerd Petermann wrote:
> > Hi Ticker,
> >
> > regarding the shapes my current approch is to combine them before
> > running insideness tests. So, the two residential areas around w18
> > are combined to one,
> > but the two shapes near w30 are kept separate.
> >
> > I think the needed checks for ways are more or less the same as in
> > the code for MultipolygonRelation.contains(WayAndLazyPolygon
> > polygon1, JoinedWay polygon2)
> > Maybe I'll use that code, but up to now I don't understand all of
> > it,
> > esp. the part with the 3x3 matrix starting in line 1546.
> >
> > For a point I can use a variant of the wn_PnPoly() algorithm
> > published here:
> > http://geomalgorithms.com/a03-_inclusion.html
> >
> > For segment-segment intersections we have an algorithm. It finds
> > when
> > a segment crosses or touches another segment.
> > When a segment a-b is touching the boundary in b there are several
> > possible cases.
> > I did not find a standard solution for the question if two line
> > strings a-b-c and x-b-y are crossing in b, or just touching, or if
> > they are overlapping.
> > That's what I am still working on. See w9, w11, w16, and w17 which
> >
> > Note that most standard intersection algorithms assume that a
> > crossing at the end of two line segments is a very special case. In
> > OSM, this is the normal case.
> > If you have an idea how to solve the problem with all the special
> > cases shown in my sample file please try to code it.
> >
> > My current work-in-progress solution doesn't work for w9, w11,
> > w21*,
> > w27*, b5, b6, and b18. (w21 and w27 give different results when I
> > reverse the way points before testing).
> >
> > If you have an idea how to implement the tests I'd be happy to get
> > a
> > patch for this as well. The current code in the branch can be used
> > as
> > sample for "what you should not do" ;)
> >
> > Attached is a patch with my current work-in-progress version, lots
> > of
> > duplicated code.
> >
> > Gerd
> >
> > ________________________________________
> > Von: mkgmap-dev <mkgmap-dev-bounces at lists.mkgmap.org.uk> im Auftrag
> > von Ticker Berkin <rwb-mkgmap at jagit.co.uk>
> > Gesendet: Mittwoch, 8. Januar 2020 12:12
> > An: mkgmap-dev at lists.mkgmap.org.uk
> > Betreff: Re: [mkgmap-dev] Allow blanks in function parameters
> >
> > Hi Gerd
> >
> > I'll do patch for the function parameters shortly.
> >
> > Are you trying to trying to check if a way/polygon is in all nearby
> > polygons simultaneously, or just checking one-by-one until you get
> > 'true'?
> >
> > If one-by-one, the moment any line crosses then you can stop, with
> > IN/ON/OUT all being true (unless the line/polygon folds back on
> > itself). If no crossing, then need to take any point that wasn't ON
> > and see if that is IN; presumably using the same logic as for POINT
> > is
> > -in.
> >
> > The problem with the one-by-one is that multi-polygon processing
> > might
> > have split the target polygon and so the this simplistic method can
> > give the wrong answer.
> >
> > Considering all targets simultaneously looks much more complicated,
> > but
> > I guess you need to make a list of all crossing points and cancel
> > out
> > ones at the same position.
> >
> > For POINT is-in, I guess you just cut the polygon(s) through the
> > point
> > and count the cuts on one side, even>OUT, odd>IN. true>ON
> >
> > Ticker
> >
> > On Wed, 2020-01-08 at 10:14 +0000, Gerd Petermann wrote:
> > > Hi Ticker,
> > >
> > > I am still struggling with the insideness tests.
> > >
> > > I noticed that the scanner doesn't accept a blank in the
> > > functions
> > > parameters, e.g.  these two rules are not accepted:
> > > building=* & building!=no & is_in(landuse,residential, any)=false
> > > [0x13 resolution 24]
> > > building=* & building!=no & is_in(landuse, residential,any)=false
> > > [0x13 resolution 24]
> > >
> > > I'd prefer to allow this as well. Maybe you can have a look at
> > > this?
> > >
> > > Gerd
> > _______________________________________________
> > 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