[mkgmap-dev] patch to write polygons in decreasing order

Tue Nov 8 14:48:31 GMT 2016

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 at 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 at .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 at .org
> 
> > > > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > > _______________________________________________
> > > mkgmap-dev mailing list
> > > 
> 
> > mkgmap-dev at .org
> 
> > > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > _______________________________________________
> > mkgmap-dev mailing list
> 
> > mkgmap-dev at .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 at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev