[mkgmap-dev] [PATCH v1] Subdivision splitting

Mon Jan 31 21:35:20 GMT 2011

The patch changes the way how subdivisions are splitted.

1.: The LineMergeFilter, the LineSplitterFilter and the 
PolygonSplitterFilter runs now before subdivions are built. This avoids 
the problem that single lines/polygons are bigger than allowed in one 
subdivision.
ToDo: The filters parameters use very small values (e.g. 250 points for 
lines) which is only needed after a subdivision has been built. So maybe 
it is good to run these filters twice. First with subdivision limits 
before creating subdivisions and second after splitting each subdivision 
with lower RGN(?) limits.

2.: Subdivisions are no longer split in equal bounds sizes but into 
rather equal item sizes.
ToDo: At the moment a too large subdivision is split into 4 
subdivisions. This algorithm might be improved to compute it 
dynamically. Also points, lines and shapes should have a different 
weight in the split algorithm.

This patch is a very early patch but if fixes the "Area (xxx,yyy) to 
(zzz,qqq) contains ... but can't be split further" messages.

At the moment I am thinking about how to continue:
Maybe it is reasonable to run an initial filter (filters that are not 
resolution dependant) set just before starting the subdivision creation. 
[This is what the patch already does.]
The result of this filter set will not be changed afterwards and is used 
as input of each subdivision creation step.

For each resolution the subdivisions of the previous resolution are 
copied but the contents are removed. Then the resolution dependant 
filter sets are applied (DP filter, SizeFilter, etc.) and the results 
are assigned to the subdivisions. As a last step too big subdivisions 
are splitted. [This swaps the current processing.]

Possible problems:
A line l in resolution 15 is subdivision A.
l is splitted into 3 parts l1 to l3 in resolution 18. Is it necessary 
that l1 to l3 are assigned to child subdivisions of A or is it possible 
that e.g. l3 is assigned to a child B1 of subdivision B because the 
splitted line l3 fits better to B1?
Are there any routing problems?

I have found the thread 
http://www.mail-archive.com/mkgmap-dev@lists.mkgmap.org.uk/msg07335.html 
which indicates that my idea does not work.

WanMil

-------------- next part --------------
A non-text attachment was scrubbed...
Name: subdiv_v1.patch
Type: text/x-patch
Size: 19909 bytes
Desc: not available
Url : http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20110131/ea57def2/attachment.bin 