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

Thu Nov 10 18:37:51 GMT 2016

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