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

Tue May 8 17:33:11 BST 2012

Hi Gerd,

> 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.

The main target should not be a faster but a better algorithm that 
handles all cases of input data.

> 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?

I think it's a vale to stop the recursion.

WanMil

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