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

Sat Nov 5 08:13:35 GMT 2016

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.patch>  
>> > ;;
>> > 
>> > 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	through	
>> > > 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_v3.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.