[mkgmap-dev] [PATCH V1] boundary preparer with quadtree

Fri Feb 3 17:31:23 GMT 2012

Hi WanMil,

attached is a patch that changes the boundary preparer to use a quadtree, I
think it is goodenough now for a first public review.

http://gis.19327.n5.nabble.com/file/n5454571/boundary_prep_quadtree_v1.patch
boundary_prep_quadtree_v1.patch 

Features:
a) preparer runs in 50% of the time
b) LocationHook is also much faster when the new bnd files are used, but
mkgmap still works with the existing *.bnd files
c) bnd file size is a bit larger (~ 20%), but zip compressed size is much
smaller (dunno why)

I hope I found all big errors, but there is still some work to do:
1) some error messages are only meaningfull for the programmer, but I kept
them for now
2) some tools do not yet work with the new bnd files, e.g. BoundaryFile2Gpx
reports wrong coverage. It is probably possible to adapt them, but I did not
try yet.
3) The workoutBoundaryRelations() method is a good candidate for parallel
execution, each thread could process one bnd file.

A few remarks:
1) As mentioned before, I kept the bnd format, but used a trick to save the
position in the quadtree.
The boundaryid is padded with the "treepath" and a number which is
incremented for each boundary in a given quadtree node,
boundaryid=r1202073_332_3 means boundary data is OSM relation 1202073, and
it should be added to "root->child[3]->child[3]->child[2].nodes"
2) The tag mkgmap:lies_in was replaced by mkgmap:intersects_with, format is
equal
3) A special case: Boundaries that are referenced in mkgmap:intersects_with
tags, but do not appear with
the treepath. We need the tags of those boundaries to be able to find the
right iso code. These boundaries are added to the bnd file, but not with the
original area info, just with the bbox of the original area. Without that
trick, the bnd files would be much larger.
4) I kept a lot of code that allows to create gpx files for boundary areas
that are somehow strange, e.g. extremely small triangles, long and thin
spilkes etc. Probably most of that code will be removed later.

ciao,
Gerd

--
View this message in context: http://gis.19327.n5.nabble.com/PATCH-V1-boundary-preparer-with-quadtree-tp5454571p5454571.html
Sent from the Mkgmap Development mailing list archive at Nabble.com.