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

Tue May 8 07:53:10 BST 2012

Hi WanMil,

sorry, forget my complains. I overlooked that SimpleRouteTest uses two input
files for testing. I was confused by the data from the 2nd file.
MapSplitter doesn't see any data outside of the bbox saved in the OSM file.

So, we have two different bounding boxes in MapSplitter:
1) A real bounding box which grows with the data added to an area and 
2) A logical bounding box which is devided in the split process and which is
used to calculate 
the offsets.

I have no clear idea for an optimized algorithm, I guess it could be somehow
similar to the 
DensityMap in the tile splitter, but I doubt that it will be much faster.
Probably more importantant is
the problem that you have described in your picture. I think a solution for
this must make sure that we don't add two (or more) large objects to one
area, or we have to allow a logical bounding box with 
a width and height equal to 1 (instead of 10). 
I don't know if this limit of 10 is given by the img format or if it is just
a reasonable value to stop
the recursion?

Gerd

WanMil wrote
> 
> Hi Gerd,
> 
> there are two reasons for the overlap:
> 1. lines and shapes need to be clipped and therefore they require that 
> at least one more point outside the bbox is available
> 2. multipolygons can be handled the better the more complete they are 
> contained in the tile
> 
> The MapSplitter algorithm has nothing to do with this overlap. All items 
> are already clipped to the bounding box when the MapSplitter comes into 
> action (see StyledConverter.clipper).
> 
> WanMil
> 
>> Hi WanMil,
>>
>> I think we are talking about different things reg. the bounding boxes. I
>> meant the two bounding boxes within the OSM data.
>> We read the data and may find a bounding box. If we do, we use it. The
>> OSM file may contain a lot of points outside of
>> this bounding box (I think this is the effect of the overlap parameter
>> in splitter).
>> The question for me is at what point this overlap is no longer needed,
>> means, isn't it possible to clip everything that is outside
>> of the bounding box which was saved in the OSM file?
>> I think that would help to simplify the MapSplitter algorithm.
>>
>> Gerd
>>
>>
>>  > Date: Mon, 7 May 2012 19:56:24 +0200
>>  > From: wmgcnfg@
>>  > To: mkgmap-dev at .org
>>  > Subject: Re: [mkgmap-dev] Commit: r2277: Adjust TRE size of test
>>  >
>>  > > 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 .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
> 
> _______________________________________________
> 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-tp5689583p5692834.html
Sent from the Mkgmap Development mailing list archive at Nabble.com.