Modify

Opened 10 years ago

Closed 6 years ago

Last modified 4 years ago

#10391 closed enhancement (fixed)

Add support for "not element of" operator (⊈)

Reported by: Don-vip Owned by: team
Priority: major Milestone: 19.05
Component: Core validator Version:
Keywords: mapcss spatial operator building hangar aeroway barn Cc: simon04, bastiK, lists@…

Description (last modified by Don-vip)

I'd like to write this validator rule:

/* Many misuses of building=hangar insteaf of building=barn because it's the same word in French */
*[building=hangar][!aeroway]  *[aeroway] {
  throwWarning: tr("{0} not inside {1}", "{0.tag}", "{2.key}");
}

It's not possible yet, is it possible to add !∈ as a new spatial operator (negation of element of)?

Attachments (13)

10391_not_working.patch (5.4 KB ) - added by Don-vip 10 years ago.
10391.patch (3.3 KB ) - added by qeef 6 years ago.
Add support for "not element of" operator (∉)
0001-Add-support-for-not-element-of-operator.patch (4.0 KB ) - added by qeef 6 years ago.
Add support for "not element of" operator (∉)
0002-Remove-right-selector-iteration-when-ELEMENT_OF.patch (3.7 KB ) - added by qeef 6 years ago.
Remove right selector iteration when ELEMENT_OF
0001-Add-unit-test-for-element-of-operator.patch (5.3 KB ) - added by qeef 6 years ago.
0004-Add-unit-test-for-element-of-operator.patch (5.0 KB ) - added by GerdP 6 years ago.
modified version 0001-Add-unit-test-for-element-of-operator.patch
0005-new-selectors.patch (7.5 KB ) - added by GerdP 6 years ago.
first approach to implement new selectors
0005-new-selectors-v2.patch (10.6 KB ) - added by GerdP 6 years ago.
0005-new-selectors-v3.patch (13.3 KB ) - added by GerdP 6 years ago.
added unit test
0006-new-selectors.patch (11.6 KB ) - added by GerdP 6 years ago.
testdata.patch (1.2 KB ) - added by GerdP 6 years ago.
contains.osm (2.0 KB ) - added by GerdP 6 years ago.
hw-in-building.osm (3.5 KB ) - added by GerdP 6 years ago.

Download all attachments as: .zip

Change History (88)

comment:1 by bastiK, 10 years ago

Does the following work?

*[building=hangar][!aeroway]  *[aeroway] {
  set hangar_in_aeroway;
}
*[aeroway]!.hangar_in_aeroway {
  throwWarning: ...;
}

comment:2 by Don-vip, 10 years ago

I don't know.. but it's quite ugly ;) By the way for consistency we should use (U+2209)

comment:3 by Don-vip, 10 years ago

Description: modified (diff)
Summary: Add support for "not element of" operator (!∈)Add support for "not element of" operator (∉)

by Don-vip, 10 years ago

Attachment: 10391_not_working.patch added

comment:4 by Don-vip, 10 years ago

I tried to implement it but it's not working, why?

comment:5 by Aun Johnsen <lists@…>, 10 years ago

Cc: lists@… added

by qeef, 6 years ago

Attachment: 10391.patch added

Add support for "not element of" operator (∉)

comment:6 by qeef, 6 years ago

Guys, I just attached proposal patch, please comment.

I think that the current implementation of ELEMENT_OF is conceptually wrong because of iterating over right selector.

Also, testing is needed - I only tested the patch on:

area[building]  area[landuse=residential][landuse] {
  throwWarning: tr("Building inside {0}", "{0.tag}");
}
Last edited 6 years ago by Klumbumbus (previous) (diff)

comment:7 by qeef, 6 years ago

Sorry for typo in the example css, should be:

area[building]  area[landuse=residential][landuse] {
  throwWarning: tr("Building not inside {0}", "{0.tag}");
} 
Last edited 6 years ago by Klumbumbus (previous) (diff)

comment:8 by Don-vip, 6 years ago

Thanks for the patch! Simon, would you like to take a look?

by qeef, 6 years ago

Add support for "not element of" operator (∉)

by qeef, 6 years ago

Remove right selector iteration when ELEMENT_OF

comment:9 by qeef, 6 years ago

Just cleaned up the code.

Commit messages:

  • 0001-Add-support-for-not-element-of-operator.patch​
    Add support for "not element of" operator (∉)
    
    This patch changes the `matches` method of `ChildOrParentSelector` in a
    such way that `ELEMENT_OF` and `NOT_ELEMENT_OF` operators iterate over
    the *left* selector.
    
  • 0002-Remove-right-selector-iteration-when-ELEMENT_OF.patch
    Remove right selector iteration when ELEMENT_OF
    

comment:10 by qeef, 6 years ago

bump a little bit

comment:11 by stoecker, 6 years ago

Bumping is rude. Nagging is better 😊

comment:12 by stoecker, 6 years ago

Milestone: 18.10

comment:13 by michael2402, 6 years ago

The test you propose is very slow for large datasets. We should avoid having a O(n²) test in MapCSS.

I think that we should define the semantics of the "element of" operator first before changing how it works. I did not find it anywhere in the source or in the wiki.

in reply to:  13 ; comment:14 by Don-vip, 6 years ago

Replying to michael2402:

I think that we should define the semantics of the "element of" operator first before changing how it works. I did not find it anywhere in the source or in the wiki.

See #9516

in reply to:  14 comment:15 by qeef, 6 years ago

Replying to Don-vip:

Replying to michael2402:

I think that we should define the semantics of the "element of" operator first before changing how it works. I did not find it anywhere in the source or in the wiki.

See #9516

I would stick with well known definitions like https://en.wikipedia.org/wiki/Element_%28mathematics%29

Current implementation, when the following rule is used for two buildings inside residential area,

area[building]  area[landuse=residential][landuse] {
  throwWarning: tr("Building inside {0}", "{0.tag}");
}

returns selection of one of the buildings and the residential area. In patched version, both buildings are selected.

Can we agree that the current behavior is wrong and the patched is right? If not, I would say that the current behavior or operator is at least misleading.

Replying to michael2402:

The test you propose is very slow for large datasets. We should avoid having a O(n²) test in MapCSS.

Agree. But if you want to check if "element of", I don't see any other option in the worst case. I would be glad to discuss how to speedup the process. Also, I would like to point out the following section of the patch:

 58 +                if (!left.matches(e))
 59 +                    return false;
 60 +                boolean is_element_of = false;
 61 +                // Does exist any element in dataset that contains e.osm?
 62 +                for (IPrimitive p: e.osm.getDataSet().allPrimitives()) {
 63 +                    Environment ne = new Environment(p);
 64 +                    if (!right.matches(ne))
 65 +                        continue;

If or then iterate over the left selector and return if not match. Then check out all primitives (here could be some speedup maybe?) but skip those that does not match the right selector. In other words, more specific mapcss rule is written, faster behavior should be delivered. I haven't test it, so this is just theory.

Last edited 6 years ago by Don-vip (previous) (diff)

in reply to:  14 comment:16 by michael2402, 6 years ago

Replying to Don-vip:

Replying to michael2402:

I think that we should define the semantics of the "element of" operator first before changing how it works. I did not find it anywhere in the source or in the wiki.

See #9516

This is no exact semantics. It does not define which elements are allowed as outer and which ones are allowed as inner and when exactly the selector matches.

I was thinking of something like:

  • The selector inner ∈ outer matches every node or area inner as long as it is completely inside an area that matches outer.

We still need to define the parent semantics (e.g. that tags of the outer element are made available as parent)

comment:17 by Don-vip, 6 years ago

Milestone: 18.1018.11

comment:18 by qeef, 6 years ago

Nagging this time (as advised above).

Any replies to comment:15? Would like to know what should be done to include the patch.

michael2402 wrote:
The selector inner ∈ outer matches every node or area inner as long as it is completely inside an area that matches outer.

I think these are two things mixed:

  1. General operator behavior -- this patch deals with this problem.
  2. Possible inner and outer primitives and their relation using the operator -- the ContainsFinder method visit(...) deals with this problem.


michael2402 wrote:
We still need to define the parent semantics (e.g. that tags of the outer element are made available as parent)

Think that semantics is already defined as already works somehow, so we can talk about the need to redefine it. Or am I misunderstanding something? Anyway, this problem is not related to this patch in my opinion.

comment:19 by Don-vip, 6 years ago

Milestone: 18.1118.12

comment:20 by qeef, 6 years ago

Bumping again as nagging doesn't work.

Don't get me wrong, I just want to keep the thread alive. I am still interested in the proper functionality of as it allows us to create a MapCSS rule for buildings that are not in a residential area. We would appreciate such a rule while HOTOSM mapping.

comment:21 by stoecker, 6 years ago

Priority: normalmajor

Please, there should be a decision in one way or the other. Letting the patch provider hang in the air is not good style.

comment:22 by Don-vip, 6 years ago

Agreed. Michael, Simon, can you please look into it?

comment:23 by Don-vip, 6 years ago

@qeef I'm sorry this takes this long... As an immediate performance improvement I think instead of iterating on all primitives, we should only iterate on closed ways and multipolygons. This should avoid the creation of thousands of Environment objects for each iterated node / unclosed way.

Otherwise without any feedback from other team members I'm ok with the changes. Could you please add a unit test that covers the new operator?

comment:24 by michael2402, 6 years ago

I'm not happy with the patch, mostly due to the performance problems it introduces. We add a linear walk through all primitives for an element-of test. Before the patch, we only searched the elements inside the bounding box, which scales way better.
Using the element of test in drawing will introduce performance problems that way. And validation will take longer.
And we do not do any more multipolygon case handling, this code was probably there for a reason.

Due to a missing clear definition of "element of" I can't really tell if it is correct from a algorithmic point of view.

I think we should first write several unit tests to test that operator (you can use the Mappaint tests if you want something graphical or you can write your own test that tests the different cases of points / ways / multipolygons containing each other).

comment:25 by Don-vip, 6 years ago

Milestone: 18.1219.01

in reply to:  23 comment:26 by qeef, 6 years ago

@Don-vip @michael2402 Thanks for reply guys. I will create unit tests first. That's good point that will move us forward.

comment:27 by qeef, 6 years ago

The patch with unit test for element of operator follows. As this is my first unit test for JOSM, I am not completely sure if it's OK.

Also small question - is it possible to run just one test class/method from ant in JOSM?

comment:28 by Don-vip, 6 years ago

Milestone: 19.0119.02

comment:29 by qeef, 6 years ago

So, there are two things I would like to discuss.

  1. The first scenario is in 0001-Add-unit-test-for-element-of-operator.patch (sorry for the name, it should be 0003...):
    • MapCSS search area[building] ∈ area[landuse=residential][landuse] {},
    • two buildings inside residential area (in data_nodist/buildings-in-residential.osm).

The discussion should be about the result of search before and after the 0001-Add-support-for-not-element-of-operator.patch​ is applied. After the discussion, I will dig deeper to understand the multipolygon and performance issues mentioned earlier and fix those.

  1. The second thing is testContains in ChildOrParentSelectorTest.java:
    • MapCSS search node[tag("amenity") = parent_tag("amenity")] ∈ *[amenity] {},
    • scenario in data_nodist/amenity-in-amenity.osm.

I think that the result of MapCSS should be the node with amenity tag set. And that's not happening before 0001-Add-support-for-not-element-of-operator.patch​ is applied, neither after.

Thanks!

comment:30 by Don-vip, 6 years ago

Milestone: 19.0219.03

comment:31 by Don-vip, 6 years ago

Milestone: 19.03

in reply to:  29 ; comment:32 by GerdP, 6 years ago

Replying to qeef:

So, there are two things I would like to discuss.

  1. The first scenario is in 0001-Add-unit-test-for-element-of-operator.patch (sorry for the name, it should be 0003...):
    • MapCSS search area[building] ∈ area[landuse=residential][landuse] {},
    • two buildings inside residential area (in data_nodist/buildings-in-residential.osm).

The discussion should be about the result of search before and after the 0001-Add-support-for-not-element-of-operator.patch​ is applied. After the discussion, I will dig deeper to understand the multipolygon and performance issues mentioned earlier and fix those.

  1. The second thing is testContains in ChildOrParentSelectorTest.java:
    • MapCSS search node[tag("amenity") = parent_tag("amenity")] ∈ *[amenity] {},
    • scenario in data_nodist/amenity-in-amenity.osm.

I think that the result of MapCSS should be the node with amenity tag set. And that's not happening before 0001-Add-support-for-not-element-of-operator.patch​ is applied, neither after.

During the last days I got familiar with the code in ContainsFinder, see also ticket:17011#comment:22. I am not sure what you mean with "MapCSS search" here. Is it about the use in the validator or in the search dialog?
I think the latter doesn't really work as it "finds" the containing element and not the contained (or maybe the pair of both?).
Anyway, I think I've implemented a good base to implement this new operator.

in reply to:  32 comment:33 by qeef, 6 years ago

Replying to GerdP:

Replying to qeef:

...

  1. The second thing is testContains in ChildOrParentSelectorTest.java:
    • MapCSS search node[tag("amenity") = parent_tag("amenity")] ∈ *[amenity] {},
    • scenario in data_nodist/amenity-in-amenity.osm.

I think that the result of MapCSS should be the node with amenity tag set. And that's not happening before 0001-Add-support-for-not-element-of-operator.patch​ is applied, neither after.

During the last days I got familiar with the code in ContainsFinder, see also ticket:17011#comment:22. I am not sure what you mean with "MapCSS search" here. Is it about the use in the validator or in the search dialog?
I think the latter doesn't really work as it "finds" the containing element and not the contained (or maybe the pair of both?).
Anyway, I think I've implemented a good base to implement this new operator.

It's about unit tests. I think that the current testContains test with amenity should fail for current implementation of .

comment:34 by michael2402, 6 years ago

What I am still missing is a clear formal definition of ∈. As long as we do not have such a definition, whether that test fails or not is a purely subjective decision.

in reply to:  34 comment:35 by qeef, 6 years ago

Replying to michael2402:

What I am still missing is a clear formal definition of ∈. As long as we do not have such a definition, whether that test fails or not is a purely subjective decision.

I appreciate this approach, this is my suggestion.

I am using Node, Way, and Relation as in https://wiki.openstreetmap.org/wiki/Elements.
I am using Area as in https://wiki.openstreetmap.org/wiki/Area.
I am using Area Element as in https://en.wikipedia.org/wiki/Volume_element.
I am using relation types from https://wiki.openstreetmap.org/wiki/Types_of_relation.

Lets define as follows:

  • For node n it holds n∈n iff n=n (ids are the same).
  • For node n, way w it holds n∈w iff n is returned by w.getNodes().
  • For node n, way w the relation w∈n is not possible (always false).
  • For node n, area a, it holds n∈a iff n is area element of a.
  • For node n, multipolygon relation r it holds n∈r iff n∈at least one outer area && ¬(n∈any inner area).
  • For way w, multipolygon relation r it holds w∈r iff for each n∈w: n∈r && w does not cross any outer/inner area.
  • For node n, boundary relation r it holds n∈r iff n∈at least one outer area && ¬(n∈any inner area).
  • For way w, boundary relation r it holds w∈r iff for each n∈w: n∈r && w does not cross any outer/inner area.
  • For node n, relation r it holds n∈r iff n is member of r.
  • For way w, relation r it holds w∈r iff w is member of r.
  • is a binary relation that is reflexive, antisymmetric, and transitive.

I am not sure. Is this formal definition?

in reply to:  32 comment:36 by qeef, 6 years ago

Replying to GerdP:

Anyway, I think I've implemented a good base to implement this new operator.

I am interested in this, I will check your code when I save a little bit of time. If is well implemented, is a piece of cake.

comment:37 by michael2402, 6 years ago

@qeef

Yes, this is exactly what we need. There are some problems with your definition though:

  • Imagine a closed way w with area=yes and a node n in the middle of that area. n∈a would be both false (rule 2) and true (rule 4)
  • Same goes for relations / ways / nodes
  • ∈ is not transitive, since you can have a node that is part of a way, that way is part of a relation but the node is not in the relation.
  • ∈ is not reflexive, since r∉r and w∉w

We are mixing two concepts of element of: One is a 'is inside of', the other is 'is in the set'.

I think that we need two separate operators for that:

  • An 'is-child-of' operator. Like:
    • node<is child of>way
    • way<is child of>relation
    • A node would then never be the child of itself.
  • An 'is-inside-of' operator. Like:
    • node∈way iff way is an area and node is contained in the area.
    • node∈node iff they have same coordinates.
    • node∈relation iff relation is an area and node is in that area.
    • way∈node iff way is an area has only nodes with coordinates of that node. (to discuss, but would be consistent, since an area that is a point is element of an other area that is a point at the same coordinate)
    • way∈way iff both ways are areas and first area is completely contained in second area.
    • way∈relation iff both are areas and first area is completely contained in second area.
    • relation∈node iff relation is an area and has only nodes with coordinates of that node.
    • relation∈way iff both are areas and first area is completely contained in second area.
    • relation∈relation iff both are areas and first area is completely contained in second area.
Last edited 6 years ago by michael2402 (previous) (diff)

in reply to:  37 comment:38 by anonymous, 6 years ago

Replying to michael2402:

@qeef

Yes, this is exactly what we need. There are some problems with your definition though:

Good. I didn't think I can make it in one shot anyway.

  • Imagine a closed way w with area=yes and a node n in the middle of that area. n∈a would be both false (rule 2) and true (rule 4)
  • Same goes for relations / ways / nodes

If we need to stick to be formal, I agree. The problem here is that the way is also the area.

  • ∈ is not transitive, since you can have a node that is part of a way, that way is part of a relation but the node is not in the relation.
  • ∈ is not reflexive, since r∉r and w∉w

Also agree and is related to the next point.

We are mixing two concepts of element of: One is a 'is inside of', the other is 'is in the set'.

This is the case of my confusion with this operator, I would say. I agree with two operators, therefore. I would just propose a little bit different names:

  • Is subset of operator (irreflexive, asymmetric).
  • Is inside of operator (reflexive, antisymmetric, and transitive).

I think that we need two separate operators for that:

  • An 'is-child-of' operator. Like:
    • node<is child of>way
    • way<is child of>relation
    • A node would then never be the child of itself.

This would be is subset of operator :

  1. For nodes n1, n2 it holds n1⊂n2 is not possible.
  2. For node n, way w it holds n⊂w iff n is returned by w.getNodes().
  3. For node n, relation r it holds n⊂r iff is contained in r.
  1. For way w, node n it holds w⊂n is not possible.
  2. For ways w1, w2 it holds w1⊂w2 is not possible.
  3. For way w, relation r it holds w⊂r iff w is contained in r.
  1. For relation r, node n it holds r⊂n is not possible.
  2. For relation r, way w it holds r⊂w is not possible.
  3. For relations r1, r2 it holds r1⊂r2 iff r1 is contained in r2 => ¬(r2⊂r1). (Disputable because of recursive relations?)
  • An 'is-inside-of' operator. Like:

This would be is inside of operator :

  • node∈way iff way is an area and node is contained in the area.
  • node∈node iff they have same coordinates.
  • node∈relation iff relation is an area and node is in that area.

This one is tricky due to inner/outer roles. Here, I would prefer already mentioned n∈r iff n∈at least one outer area && ¬(n∈any inner area).

  • way∈node iff way is an area has only nodes with coordinates of that node. (to discuss, but would be consistent, since an area that is a point is element of an other area that is a point at the same coordinate)
  • way∈way iff both ways are areas and first area is completely contained in second area.
  • way∈relation iff both are areas and first area is completely contained in second area.

Again tricky due to inner/outer roles. I would stick with w∈r iff for each n∈w: n∈r && w does not cross any outer/inner area.

  • relation∈node iff relation is an area and has only nodes with coordinates of that node.
  • relation∈way iff both are areas and first area is completely contained in second area.
  • relation∈relation iff both are areas and first area is completely contained in second area.

The last tricky one. Imagine multipolygon relation with holes that is contained in some hole of other multipolygon relation.

Can we agree on these formal definitions?

Last edited 6 years ago by qeef (previous) (diff)

comment:39 by GerdP, 6 years ago

The current implementation for ∈ doesn't allow nodes on the right and I think this is correct. Nothing fits into a node unless we don't treat nodes as infinitely small. I also don't like the idea that N1∈N2 and N2∈N1 would both be true for two nodes with the same coordinates.
Besides that I think the current implementation meets the last list.
Special cases to consider:
For the ∈ operator an incomplete relation is ignored, as we cannot know the area unless we know all ways.

in reply to:  39 ; comment:40 by qeef, 6 years ago

Replying to GerdP:

The current implementation for ∈ doesn't allow nodes on the right and I think this is correct. Nothing fits into a node unless we don't treat nodes as infinitely small. I also don't like the idea that N1∈N2 and N2∈N1 would both be true for two nodes with the same coordinates.

Sounds reasonable to me as N1∈N2 is not important and ignoring nodes at the right side will probably enhance performance.

Besides that I think the current implementation meets the last list.

I don't think so. Please, check the buildings-in-residential.osm file in this patch https://josm.openstreetmap.de/attachment/ticket/10391/0001-Add-unit-test-for-element-of-operator.patch and run the search query (expert mode needed for MapCSS search) area[building] ∈ area[landuse=residential][landuse] {} from the same file.

Huh, and there is of course question if the element we search for is on the left or on the right?

Special cases to consider:
For the ∈ operator an incomplete relation is ignored, as we cannot know the area unless we know all ways.

I am not sure what you mean by "incomplete". Is it relation that is not area? Then I agree, it's in the definition.

in reply to:  40 comment:41 by GerdP, 6 years ago

Replying to qeef:

Besides that I think the current implementation meets the last list.

I don't think so. Please, check the buildings-in-residential.osm file in this patch https://josm.openstreetmap.de/attachment/ticket/10391/0001-Add-unit-test-for-element-of-operator.patch and run the search query (expert mode needed for MapCSS search) area[building] ∈ area[landuse=residential][landuse] {} from the same file.

Huh, and there is of course question if the element we search for is on the left or on the right?

Yes, the current implementation of ContainsFinder returns the right side in parent and all elements matching the left
in children. It is up to the calling method to interpret that result. I think the code was implemented for the validator,
the search dialog simply isn't aware of this special case.

Special cases to consider:
For the ∈ operator an incomplete relation is ignored, as we cannot know the area unless we know all ways.

I am not sure what you mean by "incomplete". Is it relation that is not area? Then I agree, it's in the definition.

Normally, a relation with type=multipolygon describes an area. You can have incomplete relations when you download a bounding box from OSM (e.g. you might only have some ways of a large multipolygon). Those ways might describe an area, but without knowing all ways we don't know the area of the relation (missing ways might describe holes or other other outer areas).
Anyhow, we can define that a relation only describes an area when it is complete.
A bit more complex is the case where a multipolygon relation is not valid, maybe because it is self-intersecting or outer way segments are touching. The current implementation doesn't care about this because the corresponding validator tests are quite complex.

by GerdP, 6 years ago

modified version 0001-Add-unit-test-for-element-of-operator.patch

comment:42 by michael2402, 6 years ago

I like the idea of using the subset operator for areas. So first, we would need to define an area, then we simply use <area> is subset of <area>.

An area is normally a set of (possibly infinite many) coordinates. To define an area, we could:

  • Define the area of a point to be that point
  • Define the area of a way to be the area covered by that way if that way is a valid area.
  • Define the area of a relation to be the area covered by any outer ring and not covered by any inner ring if it is a complete, valid multipolygon.

The problem with the ⊂ operator is, that it is difficult to implement efficiently. Subset with equality ⊆ is much easier to test.
So the definition would be:

  • a1 ⊆ a2 iff both are areas and every point covered by a1 is in the set of points covered by a2

This will lead to some difficulties/abnormalies:

  • a ⊆ a will only be true, if any of those are areas. So for a non-multipolygon relation, r ⊆ r will never hold (much like NaN is never equal to NaN)
  • n1 ⊆ n2 will be true if the nodes have the same coordinates

comment:43 by GerdP, 6 years ago

I can try to implement this new selector ⊆ as well. If I got that right we would also need also ⊇, ⊈, and ⊉.
Still, the open question is if a1 ⊆ a2 means that selector.matches(a1) is true or if selector.matches(a2) is true when a1 is inside of a2.
BTW: I think a better symbol for the current implementation of ContainsFinder would be ⭖ https://unicode-table.com/de/2B56/

Last edited 6 years ago by GerdP (previous) (diff)

in reply to:  43 ; comment:44 by michael2402, 6 years ago

Replying to GerdP:

I can try to implement this new selector ⊆ as well. If I got that right we would also need also ⊇, ⊈, and ⊉.
Still, the open question is if a1 ⊆ a2 means that selector.matches(a1) is true or if selector.matches(a2) is true when a1 is inside of a2.

I would suggest:
a ⊆ b → selector.matches(b)
a ⊇ b → selector.matches(b)

(Since in normal CSS, the matched element is always on the rightmost part of the expression)

BTW: I think a better symbol for the current implementation of ContainsFinder would be ⭖ https://unicode-table.com/de/2B56/

Yes, I think most confusion in this discussion comes from the confusion about what 'element of' means for nodes/ways.

in reply to:  44 comment:45 by GerdP, 6 years ago

Replying to michael2402:

Replying to GerdP:

I can try to implement this new selector ⊆ as well. If I got that right we would also need also ⊇, ⊈, and ⊉.
Still, the open question is if a1 ⊆ a2 means that selector.matches(a1) is true or if selector.matches(a2) is true when a1 is inside of a2.

I would suggest:
a ⊆ b → selector.matches(b)

So that would be the current ContainsFinder with additional support for nodes on the right side.

a ⊇ b → selector.matches(b)

(Since in normal CSS, the matched element is always on the rightmost part of the expression)

Yes, I also want to stick to that rule to avoid further confusion.
a ⊈ b would find an element b which doesn't "contain" any element matching a
a ⊉ b would find an element b which is not "inside" any element matching a

by GerdP, 6 years ago

Attachment: 0005-new-selectors.patch added

first approach to implement new selectors

comment:46 by GerdP, 6 years ago

I tried these new operators with rules like

area[landuse]   *[building]

to find buildings which are not inside a landuse area. I think the result is correct, but maybe will be surprising:
Many of the buildings in the result are mostly inside a landuse area, but they are also crossing it. So, care has to be taken when using it for validator results.

in reply to:  46 ; comment:47 by michael2402, 6 years ago

Replying to GerdP:

Many of the buildings in the result are mostly inside a landuse area, but they are also crossing it. So, care has to be taken when using it for validator results.

This is why I think that we allow borders to be included.
Example:
https://www.openstreetmap.org/way/261295953
https://www.openstreetmap.org/relation/5538537

For this case, *[building] ⊆ area[landuse] would match the two (assuming the border is placed exactly)
We could add a small margin of e.g. 2cm to the outer area (we use double coordinates, so this is possible) to adjust for floating point rounding issues when both areas share a side.

in reply to:  47 comment:48 by GerdP, 6 years ago

For this case, *[building] ⊆ area[landuse] would match the two (assuming the border is placed exactly)

No, the building is only almost contained. Maybe it ways meant to be contained but these tests are not made to guess.

We could add a small margin of e.g. 2cm to the outer area (we use double coordinates, so this is possible) to adjust for floating point rounding issues when both areas share a side.

I don't think this will help, besides the additional effort to calculate a slightly larger area. We have similar problems with other tests like crossing ways or crossing areas.
I'd rather add more selectors like an InsideOrOverlapping (or Not_Outside) to handle those cases.

comment:49 by GerdP, 6 years ago

I found a stupid bug in the patch regarding ⊇ and ⊉.
Working on a corrected version...
Besides that I am still not happy with the special cases for "node equals node".

by GerdP, 6 years ago

Attachment: 0005-new-selectors-v2.patch added

comment:50 by GerdP, 6 years ago

v2 fixes the bug with ⊇ and ⊉. It also improves code and performance. The additional code in MapCSSTagChecker makes sure that selected elements are also verified with the new operators ⊆ and ⊈.

by GerdP, 6 years ago

Attachment: 0005-new-selectors-v3.patch added

added unit test

by GerdP, 6 years ago

Attachment: 0006-new-selectors.patch added

comment:51 by GerdP, 6 years ago

My favourite solution so far:

  • ignore special cases with nodes at the same position, I see no use case for this.
  • ⊆ and ∈ work the same way

A bit problematic: What should matches() return for the NOT operators (⊈, ⊉) when the element is not an area?
With 0006-new-selectors.patch they return true if the right selector matches.

comment:52 by GerdP, 6 years ago

Any thoughts?

by GerdP, 6 years ago

Attachment: testdata.patch added

comment:53 by GerdP, 6 years ago

I've noticed that the last two patches did not contain a change in data_nodist\amenity-in-amenity.osm :(
See testdata.patch

in reply to:  51 comment:54 by qeef, 6 years ago

Replying to GerdP:

My favourite solution so far:

  • ignore special cases with nodes at the same position, I see no use case for this.
  • ⊆ and ∈ work the same way

A bit problematic: What should matches() return for the NOT operators (⊈, ⊉) when the element is not an area?
With 0006-new-selectors.patch they return true if the right selector matches.

I think that and should work for nodes also, i.e. bus stop in a residential area. Therefore matches() should return true when children.size() > 0, IMHO.

comment:55 by GerdP, 6 years ago

Can you give an example which doesn't work with the implementation in 0006-new-selectors.patch?

in reply to:  55 comment:56 by qeef, 6 years ago

Replying to GerdP:

Can you give an example which doesn't work with the implementation in 0006-new-selectors.patch?

Tested 0006*, works like a charm. My answer was more generic to "What should matches() return..." question.

I think that 0006* resolves the origin issue. Good job.

comment:57 by GerdP, 6 years ago

Milestone: 19.05

OK, thanks for testing. I'll commit it tomorrow if nobody complains.

comment:58 by GerdP, 6 years ago

Resolution: fixed
Status: newclosed

In 15102/josm:

fix #10391: Add support for "not element of" operator

  • implement 4 new operators: ⊆,⊈,⊇,⊉
  • ⊆ is a synonym for the existing ∈ operator that uses the ContainsFinder, it

matches for elements which contain one or more elements matching the left Selectors

  • ⊈ matches for elements which do not contain any element matching the left Selectors (also uses the ContainsFinder)
  • ⊇ matches for elements which are contained in an element matching the left Selectors, it uses the InsideOrEqualFinder and is typically slower than ⊆, so it is probably only usefull for the search dialog
  • ⊉ matches for elements which are NOT contained in any element matching the left Selector
  • Both ContainsFinder and InsideOrEqualFinder work with areas, an area is either descibed by a closed way or a valid, complete relation of type=multipolygon or type=boundary. Incomplete objects do not contain something, invalid objects produce unpredictable results.
  • An element A contains another element B when it is an area and when B is either a Node inside the area of A, or when it is also an area that is fully inside or equal to A. An element is not inside a relation when it is a member of that relation.
  • hint: with ∈,⊆,⊈ prefer to use area selector instead of * for the right side, for ⊇,⊉ use area selector on the left side

comment:59 by GerdP, 6 years ago

After writing the commit message I wondered in what situation we can use the new operators for the validator.
To be honest, I don't see any for ⊈,⊇,⊉
The "not" operators are likely to produce false positives, the ⊇ is just a slower version of ⊆, so it is only useful in the search dialog.

Following the example above one might want to use

area[aeroway]  *[building=hangar]{
  throwWarning: tr("{0} not inside {1}", "{0.tag}", "{2.key}");
}

If this test produces a result it will always be "building=hangar not inside null"
So, next try could be

area[aeroway]  *[building=hangar]{
  throwWarning: tr("{0} not inside aeroway area", "{0.tag}");
}

Problem: There might be a surrounding aeroway=aerodrome multipolygon in the OSM data which is simply incomplete in the downloaded area, or the multipolygon might be invalid.
So, the message should rather be

area[aeroway]  *[building=hangar]{
  throwWarning: tr("Found no enclosing aeroway area for {0}, consider to use building=barn", "{0.tag}");
}

Still, this message is missleading or obsolete when the multipolygon is incomplete or invalid and of course it is confusing when only a very small part of the building is outside of the aeroway.
Or am I to pessimistic? We have other tests which produce false positives for incomplete data like the "Way end node near other highway" test.

in reply to:  59 comment:60 by qeef, 6 years ago

Replying to GerdP:

After writing the commit message I wondered in what situation we can use the new operators for the validator.
To be honest, I don't see any for ⊈,⊇,⊉

For me, I am glad for because of HOT mapping. When validating some task, usually we would like to know if there are buildings outside of a residential area, so area[residential] ⊉ area[building] is what is needed.

comment:61 by GerdP, 6 years ago

Assume you meant area[landuse=residential] ⊉ area[building].
OK, as long as an experienced mapper uses this for quality checks I see no problems. For beginners such a rule could force
unwanted small landuse areas around single buildings because "JOSM complained".

in reply to:  61 comment:62 by qeef, 6 years ago

Replying to GerdP:

Assume you meant area[landuse=residential] ⊉ area[building].
OK, as long as an experienced mapper uses this for quality checks I see no problems. For beginners such a rule could force
unwanted small landuse areas around single buildings because "JOSM complained".

I agree. I don't have any example for core validator yet. Anyway, thanks for the new operators!

comment:63 by Don-vip, 6 years ago

Great work! Can you please update Help/Styles/MapCSSImplementation with the new operators and all the formalism you have collectively defined in this ticket? Thanks.

comment:64 by GerdP, 6 years ago

OK, I'll try.

by GerdP, 6 years ago

Attachment: contains.osm added

comment:65 by GerdP, 6 years ago

I've started to document the changes. I was a bit surprised about some results.
Try

*[building=hangar]  area[aeroway=aerodrome]

with the attached file contains.osm
I was surprised to find that a multipolygon with incomplete members matches the area selector. I learned that I have to add
:closed2 to get a reasonable result:

*[building=hangar]  area:closed2[aeroway=aerodrome]

I think I should add this somewhere in the wiki.

comment:66 by GerdP, 6 years ago

In 15105/josm:

see #10391: replace * by area for the right selector with ∈

by GerdP, 6 years ago

Attachment: hw-in-building.osm added

comment:67 by GerdP, 6 years ago

I've just noticed that unclosed ways produce rather unpredictable results. Try

*[highway]  area[building]

with the attached hw-in-building.osm.
I think the search should return all three buildings if we want to allow that unclosed ways are found or none if unclosed ways should be ignored.
The results are caused by the fact that Geometry.getArea() virtually adds a line from the last point to the first and thus closes the unclosed way and the calling methods don't check if a way is closed.
I think we do not yet have a correct method to find out if an unclosed way is inside an area, so I tend to change the code so that unclosed ways are never found.

in reply to:  67 comment:68 by qeef, 6 years ago

Replying to GerdP:

I've just noticed that unclosed ways produce rather unpredictable results. Try

*[highway]  area[building]

with the attached hw-in-building.osm.

In this particular case is not synonym for , as *[highway] ⊆ area[building] returns different result.

Also, it looks like matched element is not the rigthmost area[building] ⊆ *[highway].

To be honest, I am confused a little bit. I am sorry, probably I skipped something.

comment:69 by GerdP, 6 years ago

The code for ⊆ and ∈ is the same, so I don't see a way how they could produce different results.
Your example area[building] ⊆ *[highway] should not find anything. Did you mean area[building] ⊇ *[highway]?

in reply to:  69 comment:70 by qeef, 6 years ago

Replying to GerdP:

The code for ⊆ and ∈ is the same, so I don't see a way how they could produce different results.
Your example area[building] ⊆ *[highway] should not find anything. Did you mean area[building] ⊇ *[highway]?

I am really sorry. I ran old JOSM version. Stupid mistake. area[building] ⊆ *[highway] really do nothing.

I think that unclosed way in area may be beneficial in some cases (again HOT example - find residential area with no access road). But I think that it is another issue.

comment:71 by GerdP, 6 years ago

No problem. In fact JOSM tested (r15031) should not accept the new operators but it does. I think that's an error and I'll open a new ticket for it.
I'll also open a new ticket for the unclosed ways, this problem also exists in r15031.

comment:72 by GerdP, 6 years ago

See new tickets: #17745 and #17746

comment:73 by Don-vip, 6 years ago

Summary: Add support for "not element of" operator (∉)Add support for "not element of" operator (⊈)

comment:74 by Don-vip, 6 years ago

In 15151/josm:

see #10391 - report building=hangar outside of aeroway

comment:75 by Klumbumbus, 4 years ago

In 16830/josm:

fix #19570, see #10391 - Move hangar outside aeroway warning to external France specific rules

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain team.
as The resolution will be set.
The resolution will be deleted. Next status will be 'reopened'.

Add Comment


E-mail address and name can be saved in the Preferences .
 
Note: See TracTickets for help on using tickets.