Re: [mkgmap-dev] patch to write polygons in decreasing order
Hi Gerd My device shows buildings as very slightly paler than the pale background and so it is difficult to see them anyway, but I can't see any difference between with and without --order-by-decreasing-area. Is the change you are seeing relating them having an outline, and this has changed from 1 aggregate outline to an outline per defined building. The reason for the change in ShapeMergeFilter is to stop it combining areas that came from different OSM objects - it is only allowed to re -join objects that got split to expose holes in multi-polygon processing or were split because they had too many points to go into a subDivision. The rationale for this is that if two or more overlapping areas straddle a subdivision boundaries, they must be output in the same relative order in each subdivision, otherwise different areas could show 'on top' on each side of the boundary line. At the subdivision processing stage, merging areas unrelated except by typeCode would make this output ordering impossible. I was considering ShapeMergeFilter to be a pure map-space optimisation. If the difference you are seeing is related to area outlines, this has grave implication not just on what I'm trying to do, but also on the way mkgmap might chop up any polygon. Ticker On Thu, 2016-11-10 at 13:39 +0000, Gerd Petermann wrote:
Hi Ticker,
I still don’t understand the change in ShapeMergeFilter. One of the nice effects of this filter is that it merges buildings or forests with the same attributes. I would assume that this is still a good idea, but you have to maintain the fullArea value. Use the attached input file and compare the shapes of the buildings.
Gerd
Von: Ticker Berkin Gesendet: Donnerstag, 10. November 2016 13:35 An: Gerd Petermann Betreff: Re: AW: [mkgmap-dev] patch to write polygons in decreasing order
Hi Gerd
I hope this version of the patch will fix all the issues you have raised with the previous ones except performance.
Regards Ticker Berkin
On Tue, 2016-11-08 at 16:51 +0000, Gerd Petermann wrote:
Reg. PrepShapesForMerge: This was only used for the overview map, so Coord.equals() is the best we can get for that. I see no problems when you change it to use more precise values. Reg. Performance: Yes, no problem for now. Reg. mkgmap:skipSizeFilter: It is used to make sure that even small pieces are written to the map (to avoid white triangles in the sea). I now think that it makes sense to keep that separate from the size calculation.
Gerd
Von: Ticker Berkin Gesendet: Dienstag, 8. November 2016 15:48 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] patch to write polygons in decreasing order
Hi Gerd
1/ I hadn't discovered 'ant test' - Sorry. I'll fix ShapeMergeFilterTest.
2/ To see what is happening with ShapeMergeFilter not doing anything I tried fixing all the equal coordinates to be identical simply by calling prepShapesForMerge() just before invoking ShapeMergeFilter each time.
This gave some very strange behaviour - I was getting lots of:
SEVE: uk.me.parabola.mkgmap.filters.ShapeMergeFilter mapHants/74210002.osm.pbf: ignoring shape with id 350798212 and type 0x50 at resolution 24, it has 4 points and has an empty area
which I fixed it by changing prepShapesForMerge() to be more like the equivalent in PolygonSplitter, ie using it.unimi.dsi.fastutil.longs.Long2ObjectOpenHashMap<Coord> rather than HashMap<Coord,Coord>
Looking at Coord.hashCode() - I presume this is what the hashMap<Coord> version uses - it doesn't seem adequate to make a unique hash, so causing incorrect Coord instances to be plugged back into the shape. I'm surprised this hasn't caused other problems.
I then get a reasonable amount of shapeMerging and the img size is reduced slightly, but a bit bigger than the release code; I'd expect this.
3/ The run-time also increases as expected; Can we live with this until it can be improved with more efficient clipping?
4/ Setting fullArea of all the Sea polygons is necessary for 2 reasons: 1/ shapeMergeFilter won't merge shapes with different fullArea. 2/ it needs to be sorted/output in a consistent order with respect to other shapes that might also straddle subDivisions.
Setting to a large value means that, providing _draworder is the same for everything, tidal areas like beaches, mud-flats etc will show rather than sea. It could be set to a low value instead, so that the sea overwrites the inter-tidal areas. This achieves the default look of a map on my garmin device but without relying on the inbuilt _draworder or having TYP _draworder higher for sea.
I was thinking this could be made into an option or a mkgmap: tag so that, for systems without TYP / _draworder, there is a way of flipping the behaviour. Maybe even a value that looks like a layer-number could be specified, giving the functionality requested by Jürgen < rheinskipper1000@gmx.de>
The rationale for mkgmap:skipSizeFilter being applied to sea is related to setting sea polygons to have a large area - the sea shouldn't be lots of distinct polygons, just 1 big, very complicated one.
Ticker
On Sat, 2016-11-05 at 01:13 -0700, Gerd Petermann wrote:
Hi Ticker,
I've started to run some tests. No crash until now. A few remarks so far: 1) please use ant test before producing patches. This will show you that ShapeMergeFilterTest needs changes. 2) You already mentioned that ShapeMergeFilter doesn't work as you would expect. I think the reason is that the splitIntoAreas() method replaces the original Coord instances. This will produce pairs of different Coord instances which are "highPrecEqual" (and may not have the same flags set). The code in PolygonClipper tries to avoid this problem. The ShapeMergeFilter will only merge shapes which have identical Coord instances.
Alternative would be to implement a clipper which doesn't need area.intersect(). I've once coded the "Sutherland-Hodgman algorithm" but didn't use it yet as it failed with special cases like self -intersecting ways or concave shapes producing spikes, but I still think this would be a great improvement. See attached (out-aged) patch and the wiki
https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm
for further details.
3) With my test set of 10 tiles run time is much higher (r3701: 112 s, patched : 164 s) and img sizes are a bit higher (40 MB / 42MB) .
4) Reg. fullArea : I agree that AreaSizeFunction should return the value for the complete multipolygon but I don't yet understand the special treatment in SeaGenerator. If I got that right you try to make sure that all sea polygons are written before others, no matter how large they are? This seems to duplicate the code for mkgmap:skipSizeFilter which is also a bit dirty. Maybe
I fully agree that the current data flow for shapes is not good, so also the item "rewrite classes that hold information about map objects, esp. shapes" in the to-do list.
Gerd
mp_suth_hodg.patch < http://gis.19327.n8.nabble.com/file/n5885381/mp_suth_hodg.patch> ; ;;
Ticker Berkin wrote
Hi Gerd
I've fixed it and the test case now runs. I've also incorporated your 3 other points.
I've added the following comment to mkgmap/build/MapArea.java
/* Failed to split!
This happens easily when doing low resolution overview levels (have a high shift value) and we are insisting that areas can only be split on boundaries that can be represented exactly with the relevant shift for the level. All the lines/shapes that need to be put at this level are here, but represented at the highest resolution without any filtering relevant to the resolution. In the end it tries to split a single pixel because it contains, say, 100s of bits of Sea and Coastline with complex shapes which it thinks is too much data for a subDivision, but actually will mostly disappear when we come to write it. And it will look meaningless - the lines/shapes should have been simplified much earlier in the process, then they could appear as such in reasonably size subDivision.
The logic of levels, lines and shape placement, simplification, filtering and splitting, subDivision splitting etc needs a re-think and re-organisation. */
I could try and explain this more fully in another thread and maybe it should go on the enhancement list
Regards Ticker
On Sat, 2016-10-22 at 14:00 +0100, Ticker Berkin wrote:
Hi Gerd
I've reproduced the crash.
I think the problem is that area.getEstimatedSizes() (called from MapSplitter.addAreasToList) doesn't reflects what will go into the area when the option is in effect and so addAreasToList might keep recursing.
I need to think about this more deeply. There is a related issue where complex shapes are split earlier when there probably is no need because they will be split later to scattered into lots of subDivisions.
Concerning the other problems:
It wasn't dead code - rather a function with side effects - I'll re -code it.
Sorry about Long vs long.
I notice ShapeMergeFilterTest in the patch. I experimented a bit with mergeShapes and was surprised it wasn't doing a bit of merging when my option was in effect - I was expecting it join bits of the complex shapes mentioned earlier.
I'm away on holiday next week. I should be able to send you something in a couple of weeks time.
Regards Ticker
On Sat, 2016-10-22 at 01:04 -0700, Gerd Petermann wrote:
Hi Ticker,
I reviewed the patch, it looked good but the patched version crashes in a recursion because of an java.lang.StackOverflowError. I think the problem is in the rounding in Area class. I've uploaded test data that should allow you to reproduce the problem: http://files.mkgmap.org.uk/download/310/test.zip
Besides that I found two small problems: 1) The unit tests did not compile with the patch 2) MultPpolygonRelation.java contains dead (?) code and uses Long instead of long. Please check my changes in the attached modified patch:
sortAreas_v2.patch
< http://gis.19327.n8.nabble.com/file/n5884759/sortAreas_v2.pat ch> ;
;;
Ciao, Gerd
Ticker Berkin wrote > Hi > > I have a patch that outputs polygons into the map file in > decreasing > size order, so that, assuming equal _drawOrder, the Garmin > device > renders small details over larger areas, much like how they > appear > on > OpenStreetMap.org. > > As well as sorting by size, polygons that straddle > subDivisions > are cut up and placed into their correct subdivision, rather > than > being > put into an arbirary one, which, if it isn't the one in > focus, > renders > over the focus subdivision. > > The original, full, area of polygons is tracked throug > h > a > ny cutting and clipping so that relative ordering is correct > across > subdivision and map boundaries. > > All this is controlled by the option --order-by -decreasing > -area, > with a > default of false that leaves the behavior of mkgmap > unchanged. > A > s such, I think this patch could be applied to the trunk > development. > > Regards > Ticker Berkin > mk > > _______________________________________________ > mkgmap-dev mailing list
> mkgmap-dev@.org
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev > > sortAreas.patch (25K) > < > http://gis.19327.n8.nabble.com/attachment/5884038/0/sortAreas > .p > atch>
-- View this message in context: http://gis.19327.n8.nabble.com/patch-to -write-polygons-in-decreasing-order-tp5884038p5884759.html Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list
mkgmap-dev@.org
mkgmap-dev mailing list
mkgmap-dev@.org
mkgmap-dev mailing list
mkgmap-dev@.org
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
sortAreas_v3.patch (31K) < http://gis.19327.n8.nabble.com/attachment/5885284/0/sortAreas_v 3.patch>
-- View this message in context: http://gis.19327.n8.nabble.com/patch-to -write-polygons-in-decreasing-order-tp5884038p5885381.html Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Ticker, sorry, still some problems: 1) I think I found an error in method Area.roundPof2(int val, int shift) I wanted to find out why you did not use Util.roundUp(int val, int shift). For val=-9567 and shift=4 I see -9568 from your routine and -9552 from the other So it seems your routine doesn't round up as the javadoc says. So either the doc or the result is wrong. 2) Please check the new log messages. The severity level warning should not be used for debug messages. A warning message should be understandable for the end user. 3) Reg. performance: I think most of the area.intersect calls are not needed when you add this block at the beginning of splitIntoAreas(): // quick check if bbox of shape lies fully inside one of the areas for (int areaIndex = 0; areaIndex < areas.length; ++areaIndex) { if (areas[areaIndex].getBounds().contains(e.getBounds())) { used[areaIndex] = true; areas[areaIndex].addShape(e); return; } } // Shape crosses area(s), we have to split it // Convert to a awt area ... ciao, Gerd -- View this message in context: http://gis.19327.n8.nabble.com/patch-to-write-polygons-in-decreasing-order-t... Sent from the Mkgmap Development mailing list archive at Nabble.com.
Hi Gerd I'll check on the rounding, fix the warn>debug and add the pre-test to the splitting into areas. I've just loaded GPSMapEdit and see what you mean about the long lines of buildings - they are wavy!. I'll work out why it is happening. Regards Ticker On Fri, 2016-11-11 at 01:25 -0700, Gerd Petermann wrote:
Hi Ticker,
sorry, still some problems: 1) I think I found an error in method Area.roundPof2(int val, int shift) I wanted to find out why you did not use Util.roundUp(int val, int shift).
For val=-9567 and shift=4 I see -9568 from your routine and -9552 from the other So it seems your routine doesn't round up as the javadoc says. So either the doc or the result is wrong.
2) Please check the new log messages. The severity level warning should not be used for debug messages. A warning message should be understandable for the end user.
3) Reg. performance: I think most of the area.intersect calls are not needed when you add this block at the beginning of splitIntoAreas(): // quick check if bbox of shape lies fully inside one of the areas for (int areaIndex = 0; areaIndex < areas.length; ++areaIndex) { if (areas[areaIndex].getBounds().contains(e.getBounds())) { used[areaIndex] = true; areas[areaIndex].addShape(e); return; } } // Shape crosses area(s), we have to split it // Convert to a awt area ...
ciao, Gerd
-- View this message in context: http://gis.19327.n8.nabble.com/patch-to -write-polygons-in-decreasing-order-tp5884038p5885742.html Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Gerd I think the reason why the buildings look different is because, without --order-by-decreasing-area, they get merged into a single area and then a filter (DouglasPeucker), finding the intermediate points are within the tolerance of a straight line, removes all but the 4 corners of the complete block. With --order-by, they are output individually as accurately as possible, but, because we are at/beyond at the limit of accuracy, rounding effects become obvious. You mentioned GPSMapEdit not showing the smaller shape on top of the larger. Using it to look at your test case of buildings in Bremen, and the difference between with/without the option, I think it might apply the size rule itself - drawing smaller shapes on top of larger. The example I found was Penny supermarket @ 53.06650,8.79501 straddling a number of buildings. With the buildings merged, it is smaller and hence shows. With them separate, the buildings are smaller and they show. Does this fit with your observations? Which examples were you looking at? www.openstreetmap.org doesn't show Penny either. I didn't use Util.roundUp because I wanted something to round to the closest power of 2 and it rounds up to the next power of 2. I've improved the javaDoc text for roundPof2. I've made the other changes and attach a patch. Regards Ticker On Fri, 2016-11-11 at 11:37 +0000, Ticker Berkin wrote:
Hi Gerd
I'll check on the rounding, fix the warn>debug and add the pre-test to the splitting into areas.
I've just loaded GPSMapEdit and see what you mean about the long lines of buildings - they are wavy!. I'll work out why it is happening.
Regards Ticker
On Fri, 2016-11-11 at 01:25 -0700, Gerd Petermann wrote:
Hi Ticker,
sorry, still some problems: 1) I think I found an error in method Area.roundPof2(int val, int shift) I wanted to find out why you did not use Util.roundUp(int val, int shift).
For val=-9567 and shift=4 I see -9568 from your routine and -9552 from the other So it seems your routine doesn't round up as the javadoc says. So either the doc or the result is wrong.
2) Please check the new log messages. The severity level warning should not be used for debug messages. A warning message should be understandable for the end user.
3) Reg. performance: I think most of the area.intersect calls are not needed when you add this block at the beginning of splitIntoAreas(): // quick check if bbox of shape lies fully inside one of the areas for (int areaIndex = 0; areaIndex < areas.length; ++areaIndex) { if (areas[areaIndex].getBounds().contains(e.getBounds())) { used[areaIndex] = true; areas[areaIndex].addShape(e); return; } } // Shape crosses area(s), we have to split it // Convert to a awt area ...
ciao, Gerd
-- View this message in context: http://gis.19327.n8.nabble.com/patch-to -write-polygons-in-decreasing-order-tp5884038p5885742.html Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Ticker, thanks for your work, I've committed it now with r3701. I'll probably move calcAreaSizeTestVal() and roundPof2() to Utils tomorrow. Gerd Ticker Berkin wrote
Hi Gerd
I think the reason why the buildings look different is because, without --order-by-decreasing-area, they get merged into a single area and then a filter (DouglasPeucker), finding the intermediate points are within the tolerance of a straight line, removes all but the 4 corners of the complete block. With --order-by, they are output individually as accurately as possible, but, because we are at/beyond at the limit of accuracy, rounding effects become obvious.
You mentioned GPSMapEdit not showing the smaller shape on top of the larger. Using it to look at your test case of buildings in Bremen, and the difference between with/without the option, I think it might apply the size rule itself - drawing smaller shapes on top of larger. The example I found was Penny supermarket @ 53.06650,8.79501 straddling a number of buildings. With the buildings merged, it is smaller and hence shows. With them separate, the buildings are smaller and they show. Does this fit with your observations? Which examples were you looking at? www.openstreetmap.org doesn't show Penny either.
I didn't use Util.roundUp because I wanted something to round to the closest power of 2 and it rounds up to the next power of 2. I've improved the javaDoc text for roundPof2.
I've made the other changes and attach a patch.
Regards Ticker
On Fri, 2016-11-11 at 11:37 +0000, Ticker Berkin wrote:
Hi Gerd
I'll check on the rounding, fix the warn>debug and add the pre-test to the splitting into areas.
I've just loaded GPSMapEdit and see what you mean about the long lines of buildings - they are wavy!. I'll work out why it is happening.
Regards Ticker
On Fri, 2016-11-11 at 01:25 -0700, Gerd Petermann wrote:
Hi Ticker,
sorry, still some problems: 1) I think I found an error in method Area.roundPof2(int val, int shift) I wanted to find out why you did not use Util.roundUp(int val, int shift).
For val=-9567 and shift=4 I see -9568 from your routine and -9552 from the other So it seems your routine doesn't round up as the javadoc says. So either the doc or the result is wrong.
2) Please check the new log messages. The severity level warning should not be used for debug messages. A warning message should be understandable for the end user.
3) Reg. performance: I think most of the area.intersect calls are not needed when you add this block at the beginning of splitIntoAreas(): // quick check if bbox of shape lies fully inside one of the areas for (int areaIndex = 0; areaIndex < areas.length; ++areaIndex) { if (areas[areaIndex].getBounds().contains(e.getBounds())) { used[areaIndex] = true; areas[areaIndex].addShape(e); return; } } // Shape crosses area(s), we have to split it // Convert to a awt area ...
ciao, Gerd
-- View this message in context: http://gis.19327.n8.nabble.com/patch-to -write-polygons-in-decreasing-order-tp5884038p5885742.html Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list
mkgmap-dev@.org
mkgmap-dev mailing list
mkgmap-dev@.org
mkgmap-dev mailing list
mkgmap-dev@.org
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
sortAreas_v5.patch (36K) <http://gis.19327.n8.nabble.com/attachment/5885760/0/sortAreas_v5.patch>;
-- View this message in context: http://gis.19327.n8.nabble.com/patch-to-write-polygons-in-decreasing-order-t... Sent from the Mkgmap Development mailing list archive at Nabble.com.
Hi Ticker, Ticker Berkin wrote
I think the reason why the buildings look different is because, without --order-by-decreasing-area, they get merged into a single area and then a filter (DouglasPeucker), finding the intermediate points are within the tolerance of a straight line, removes all but the 4 corners of the complete block. With --order-by, they are output individually as accurately as possible, but, because we are at/beyond at the limit of accuracy, rounding effects become obvious.
forgot to reply on this. You are right, only it's not DouglasPeucker but RemoveObsoletePointsFilter which removes the nodes at resolution 24. (DP filter is skipped also for shapes at res 24) Gerd -- View this message in context: http://gis.19327.n8.nabble.com/patch-to-write-polygons-in-decreasing-order-t... Sent from the Mkgmap Development mailing list archive at Nabble.com.
participants (2)
-
Gerd Petermann -
Ticker Berkin