[mkgmap-dev] Commit: r2277: Adjust TRE size of test

Mon May 7 18:56:24 BST 2012

> Hi WanMil,
>
> sorry, I should have run the tests myself.

I didn't do that either before committing...

>
> We see the different values because the patched version splits
> a few more times. I think the result is okay, but maybe there is a better
> solution.
> If  I got this right, we deal with two different bounding boxes: the
> bounding box that is saved in the OSM data and the bounding box of all
> objects. I wonder if it is correct that the MapSplitter has to handle data
> that is outside of the OSM bounding box? These two different bboxes were the
> reason for some errors in the splitting process, and my patch only
> fixes the problem in MapSplitter / MapArea, but maybe it could be handled
> earlier?

Yes but I think that requires the general rework of the subdivision 
algorithm I explained in one of my previous posts.

In general you have to find an algorithm that assigns all elements to a 
subdivision so that the multiple limits of the subdivision are not 
exceeded.
The current algorithm implements a top-down algorithm, i.e. create the 
largest possible subdivisions, add all elements to it and split them 
until all limits are ok. The problem arises if splitting does not help 
to find a solution and the limits are still exceeded.

The bottom-up algorithm would add elements to subdivisions so that their 
limits are not exceeded. Theoretically this would results in a better 
fill level of the subdivisions and therefore less subdivisions. Maybe it 
is necessary to split elements so that they fit into a subdivision 
without exceeding its limits. I don't know if this algorithm is ever 
possible. Problems might be:
- if subdivisions need to be hierarchical over different layers you need 
a kind of subdivision splitting when processing the next layer
- the algorithm handling the multiple limits is complex. Maybe it's 
easier to start with adding only one type of elements to a subdivision 
(so having POI subdivisions, line subdivisions and shape subdivisions). 
This reduces the number of limits the algorithm has to handle 
simultanously.
- when is it better to split a line because it does not fit to a 
subdivision or to create a new subdivision? Creating a new subdivision 
might result is lots of subdivisions with a few lines/shapes only.

Hopefully you have some good ideas for that :-) Anyhow it is astonishing 
how good the current algorithm with the two bounds works.

WanMil

>
> Gerd
>
>
> WanMil wrote
>>
>> Gerd,
>>
>> the SimpleRouteTest checks if the file sizes of the img files are as
>> expected. After commiting the subdivision change the TRE file size
>> changed. I think thats ok, but can you please check that yourself?
>>
>> Thanks!
>> WanMil
>>
>>>
>>> Version 2277 was commited by wanmil on 2012-05-06 20:16:39 +0100 (Sun, 06
>>> May 2012)
>>>
>>> Adjust TRE size of test
>>>
>>> Commit 2276 changed the size of the TRE file by using a different
>>> subdivision algorithm.
>>> _______________________________________________
>>> 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
>>
>
>
> --
> View this message in context: http://gis.19327.n5.nabble.com/Commit-r2277-Adjust-TRE-size-of-test-tp5689583p5690595.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