[mkgmap-dev] Area splitting

Sun Jan 30 16:50:58 GMT 2011

> Hi
>
> It would be good if we had a tool to visualise the strategies used to
> allocate elements to the subdivisions. Something that displays the
> subdivision boundaries and highlights the elements that belong to a
> subdivision in some way.
>
> I really have no idea of the best way to do this.

Sounds complicated. The only idea I have is to create a separate osm 
file for each subdivision. The osm file(s) could be loaded into JOSM for 
inspection. But this is only useful to check some special subdivisions 
and not the complete process.

>
>> 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?
>
> Perhaps it is but then it would not be able to contain anything except
> perhaps a vertical or horizontal line. Why do you think it is important
> that it should be possible.

Nothing special. I just wondered if that's correct...

>
>> 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?
>
> This is just a grid used to allocate elements to subdivision.  In
> reality the subdivision is expanded to contain its elements. So they
> always overlap by quite a bit.
>
> When a division is split, then each element is allocated in one of the
> two new divisions. When the splitting is finished the real subdivision
> bounds are calculated based on the actual contents. The only important
> thing is that each element can be allocated into exactly one of the new
> divisions.

Yeah, I see. Summary: it is allowed that subdivision sizes overlap. 
Maybe there is room for improvement to reduce overlapping size.
While thinking about it I guess that less overlapping means faster map 
drawing because MapSource and the devices have to read less data if 
subdivisions do not overlap so much?!

>
>> 3. Class MapSplitter
>> As far as I understand lines and shapes are put to the subdivision that
>> contain their center points.
>
> I can't remember the whole history here, I think at one time I used the
> first point in the line, but it didn't produce particularly uniform results.

Center point is a good choice because that minimizes the maximum value 
of the lat/long diffs.

>
>> 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?
>
> Because the grid is only used to allocate elements to subdivisions, it
> doesn't matter that no point is actually in the grid section.  The
> subdivision will always be sized to contain its contents.
>
> I'm not saying that its a good thing though. Possible room for
> improvement there if it happens often.

I agree.

>
>> 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?
>
> Well this is the main problem.  We split lines earlier on.  Originally I
> split lines so that in the worst case they would never be too big to fit
> into a subdivision. Perhaps we should split them after we know roughly
> where the subdivision boundaries are going to be.

Yes, that's it. The filters are processed AFTER the subdivisions are 
created. From my point of view this should be the other way round.

I have a tile containing a polygon with 38350 points. This single 
polygon exceeds the limits of a subdivision. Because the polygon filters 
run after the subdivison creation the algorithm to create the 
subdivisions fails.

It would be better to run some or all filters before so that the smaller 
elements can be used to create the subdivisions. I will try to change 
that as a next step.

>
>> 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?
>
> Probably yes!

I tried to do that and implemented an easy approach. But this works only 
after it is ensured that there is no element that exceeds the 
subdivision limits by putting the filter chain before the subdivision 
creation.

>
> I think our existing approach gives sub-divisions that overlap a lot
> more than Garmin or cgpsmapper produced maps.
>
> It is certainly something that needs looking at again and I encourage
> you to do so.
>
> ..Steve

WanMil