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@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@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@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Mittwoch, 8. Januar 2020 12:12 An: mkgmap-dev@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@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev