[mkgmap-dev] Area splitting

Sat Jan 29 21:59:46 GMT 2011

In the last days there have been two questions around the mkgmap message 
"Area (xxx,yyy) to (zzz,qqq) contains ... but can't be split further".

The message is printed during the subdivision creation process which 
means a tile is splitted into several subdivisions which do not exceed a 
special dimension and does not exceed a maximum size (which means a max 
number of nodes, lines and/or shapes).

I have started to look how this works because I think there is some work 
to do. Such errors will occurr more often with increasing density of map 
information. The split process does not seem to be optimal.

I want to start with a list of questions and observations and hope 
someone of you is able to answer/comment them or is willing to dive into 
the source code to get an idea of what's going on there.

1. Class Area definition
An area is defined with minLat, minLong, maxLat, maxLong. It is not 
possible to define an area with minLat==maxLat or minLong==maxLong. Is 
there any reason for this?

2. Class Area split
The split method divides the area into a given number of (rather) equal 
sized subareas.
An area [(0,0) to (100,100)] would be split (xsplit==2, ysplit==1) into
[(0,0) to (50,100)]
[(50,0) to (100,100)]
I think this is wrong, because the two areas are overlapping at x==50. 
Does anyone know why the split method does not split into distinct areas?

3. Class MapSplitter
As far as I understand lines and shapes are put to the subdivision that 
contain their center points.

Assuming the situation (I describe a line example but the same applies 
to shapes)

          E
  ------- +
  |     | +
  |  x  | +
  ------- +
          +
S+++++++++

S = start point of a line
E = end point of a line
+ = line
x = center point
-| = borders of the subdivision

The line is defined in the subdivision although it does not intersect 
the subdivision. But its center point is located in the subdivision.
Is that correct?

The coordinates of the line points are stored as diffs to the center of 
the subdivision as a kind of compression. The diffs have a higher and 
lower limit. If a line is quite long and one point is far away from the 
center of the subdivision it could not be stored. What happens in such a 
case? I think a warning message is printed in the constructor of the 
Subdivision class but what happens to the line point?
Would it be better to split a line in such a case? Or would it be better 
to split a line so that the complete line fits into a subdivision?

4. Subdivision splitting
In case a subdivision is too full it is splitted into equal sized areas. 
Would it be a good first approach to improve the splitting so that the 
algorithm tries to split the subdivision into rather equal filled 
subdivisions (e.g. each splitted subdivision should contain the same 
number of points plus center points of lines/shapes?

Have fun!
WanMil