[mkgmap-dev] Branch is_in ready for a first test

Wed Feb 5 11:56:57 GMT 2020

Hi Gerd

My idea would be have a list of methods per rule-context, eg:

POLYGON: any, all
LINE: all, all_in_or_on, all_on, any, any_in_or_on
POINT: in, in_or_on, on
  until someone comes up with clearer names.

These should be an enumeration in Java so they can be changed, aliased
etc without needing to change the main code and checked as the function
is parsed.

The main logic operates as it does now, except LINE and POLYGON
handling probably need to diverge, setting the 3 internal booleans
IN/ON/OUT. Then, at the end, these are converted to a single boolean
result according to requested method and the table a)..e) for LINEs in
my previous mail

POLYGON results should be based on: is ALL/ANY of the area of rule
polygon in matching polygon(s).

The issue of polygons with holes, esp. if the rule polygon is the hole
in the target polygon are impossible to decide. I think one of your
examples had a residential area where some of the major buildings where
cut out from this area with a multi-polygon relation. Is the building
in the residential area? Logical answer is no - there is no area shared
between the two. Expected answer - yes if you know what a residential
area and a building are.

Optimisation can be performed for, eg, the any... methods, stopping as
soon as the relevant IN or ON flag is set.

Regarding cases L1-L6 for lines:
L1 OUT         
L2 OUT ON      
L3     ON   
L4     ON IN   
L5        IN
L6 OUT ON IN   

My intention was to phrase the query, via the method, in terms like:
 Is any part of this line in the matching polygons?
 Is all of this line in matching polygons?
 Is this line an edge of matching polygons?
rather than the 3 flags defining the relationship the particular line
to the polygon, so is_in(any) matches L4/L5/L6 and is_in(all) matches
L4/L5, etc (here, for LINEs, method 'any' is 'any-in' and 'all' is
'some-in-none-out')

Also, at the same time, ignore the cases where an inner line touches
the edge or an outer line touches the edge.

This gives the 5 cases a) to e)

Handling the question this way gets around problems like:
> For case L3 the results of is_in(x,y,any) and is_in(x,y,all) are
> rather unpredictable, but more likely "false" is returned.
If the rule wants to do something with a line that bounds the polygon,
it asks for is_in(all_on)

For POINTs, the same rational applies, the rule asks for what it want
to handle, eg is_in(in_or_on)=false to match a POI that outside the
polygon.

Ticker

On Wed, 2020-02-05 at 08:51 +0000, Gerd Petermann wrote:
> Hi Ticker,
> 
> I am lost in alternatives. I don't like the current solution and I
> also don't like my "three bit flags" solution.
> With the current code we can only distinguish 4 cases, your original
> list contained 6 cases, the newer 5.
> What should be changed in current code (r4228)?  More or other method
> parameters?
> 
> Please ignore the tuning idea. Most of this is only true in theory as
> rounding problems don't allow stop early unless a a real crossing (in
> -out or out-in) is detected. In reality the internal rounding of
> coordinates create something like a halo along the polygon edges.
> Results are unpredictable when a tested point is inside that halo
> unless it is exactly at the same position of a polygon node. Same
> position means it is either the identical node or has identical OSM
> coordinates.
> 
> With polygons we have the special case shown with b13 and b14 in my
> example file is-in-hook-samples-v4.osm. I forgot to add cases where
> the target polygon is inside the tested polygon. Typically those
> would be tagging errors, e.g. landuse=residential inside a
> building=yes or a closed way with both tags.
> 
> If I got you right you suggest to introduce more methods? As a
> reminder, these are the 6 different cases for a line:
> L1: all of the line is outside the polygon
> L2: some of the line is outside and the rest touches or runs along
> the polygon edge
> L3: all of the line runs along the polygon edge
> L4: some of the line is inside and the rest touches or runs along.
> L5: all of the line is inside the polygon
> L6: some is inside and some outside the polygon. Obviously some point
> is on the polygon edge but we don't care if runs along the edge.
> 
> For case L3 the results of is_in(x,y,any) and is_in(x,y,all) are
> rather unpredictable, but more likely "false" is returned.
> 
> For points we have - in theory - just three states:
> P1: point is inside polygon
> P2: point is on the edge of a polygon
> P3 point is outside
> The current code ignores the method parameter and the halo problem
> and returns true for P1 and P2 and false for P3.
> 
> The current code treats polygons like lines but case L3 may return
> different results as the code tries to find out if the tested polygon
> is inside a hole.
> 
> 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, 5. Februar 2020 07:58
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] Branch is_in ready for a first test
> 
> Hi all
> 
> I'm still of the opinion that it is better to specify a 'method'
> parameter rather than return 3 flags for the following reasons:
> 
> - for polygons, it is only meaningful to need to know if ANY or ALL
> of
> the rule polygon is in the target.
> 
> - for lines, it was thought better for the 'ALL' case to allow/ignore
> the line touching the edge, as long as the rest was IN. This tuning
> ability is lost unless keywords are used.
> 
> - for points, I agree that returning one of the 3 flags seems to make
> sense, but I still maintain it is clearer to have methods that ask
> in/in-or-on/on rather than the equivalent test with a regexp for the
> on
> -or-on case.
> 
> - for many methods, optimisation is possible, eg. 1/ the processing
> can
> stop as soon an element is found that determines the result. 2/ The
> target polygons can be processed one-by-one instead of joined
> together.
> 
> - to express the line question any-in-or-on with a regexp is messy
> and
> obscure. In the java coding of the function, I expect it to use flags
> like IN/ON/OUT, and it is trivial for the Java to convert these, in
> conjunction with the 'method', to a boolean result that is easily
> handled at the rule level.
> 
> - negation of the function is trivial when it returns a boolean.
> 
> - method keyword is more readable (and writeable) than bitstring
> regex
> test.
> 
> - the method keyword allows extendability, eg 1/ different accuracy
> requirements, 2/ magic keywords that could split the rule object into
> the parts that return true and the parts that return false.
> 
> - Mike's idea of 'coincident' - see later.
> 
> I don't thing we should consider line/polygon splitting at the
> moment.
> 
> @jan, With my table:
>                                                   simplified
> a) some-in-none-out(all) IN and not OUT
> b) all-in-or-on          (IN or ON) and not OUT   not OUT
> c) all-on                ON and not (OUT or IN)   not (OUT or IN)
> d) any-in(any)           IN
> e) any-in-or-on          IN or ON
> I was attempting to show precisely the meaningful line cases in terms
> of the flags, which I hoped to remain hidden. Without the method
> keyword, you'd have to implement the equivalent for the cases you
> required with a regexp to test the flags.
> 
> Mike Baggaley, on 16th Jan, suggested the following keywords; I've
> added a transliteration of his description of how these correspond to
> the flags:
>    all_inside      IN and not (ON or OUT)
> a) touching        IN and not OUT
> b) all_touching    not OUT
> d) some_inside     IN
> e) some_touching   IN or ON
>    coincident      all points of rule object match the target polygon
> 
> I think the use of 'touching' here is confusing and it is best to
> cover
> all possibilities with a suitable method in 1 call to the function.
> 
> @gerd, if I haven't convinced you that method keywords are better, it
> is probably better to use a single letter Y/N or T/F.
> 
> Ticker
> 
> On Wed, 2020-02-05 at 00:49 +0100, jan meisters wrote:
> > Hi all,
> > 
> > thanks for the ongoing development.
> > 
> > I like the abstraction that Gerd has given, be it with digits or
> > letters; and its implementation of all Tickers 6 cases.
> > With his explanation I could easily reproduce my simple but
> > satisfying cemetery results as by 4418.
> > 
> > On Tickers argumentation my idea is limited, as I´m not able to
> > understand all code internals he might has in mind.
> > Despite this - and if I got him correctly that it´s this logic we
> > have now - it sounds adequate as well for what I can overlook.
> > 
> > Regarding the splitting proposed by Arndt I think it´s not always
> > useful.
> > To handle improper drawings in OSM I´d prefer such a behaviour to
> > be
> > definable then.
> > Don´t know if I could need it.
> > 
> > Jan
> > 
> > _______________________________________________
> > 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