2) Calculate it in BoundaryPreparer and save it in the .bnd files (with a new or extended format). In this case we can avoid higher calculation time if that means reducing redundancy. With precompiled quadtrees the LocationHook just has to create a small master-quadtree and load required parts into it.
The quadtree in my patch probably contains a lot of redundant information because tiles with admin-level=2 or =4 will cover big parts of the tree, and the information is (almost always) already contained in the smaller areas because I use the information from the lies_in tags.
Mmh, I though the merge step will create non overlapping areas and each area contains *all* of its information. So there should be no large admin_level=2 area left but lots small areas all containing the admin_level=2,3,4,5,6,7,8,9,10,11 information.
The current implementation uses the infos of the lies_in tag and stops merging when larger areas are not adding information. So, the larger areas are kept untouched (and typically unused). They are just eating up some kb heap memory.
Ok, I haven't gone into deep in the merge() method. But I think you are going the right way!
I did not try it, but I expect that the merge() process result should be the same if we don't use the lies_in information.
If not something is wrong?!
I think so, and yes, the results are very different. So, I first have to analyse why this doesn't work as expected.
If we move the quadtree to the preparer, we can omit the calculation of the lies_in tags (I think they are not needed elsewhere), but we should try to avoid saving redundant information.
The lies_in information is only 80% of the information required for the new quadtree. So it might help but is not sufficient to remove the merge step.
Hmm, I don't fully understand what you mean. I thought about this: My idea is to replace the algorithm in BoundaryPreparer.workoutBoundaryRelations() by a call of BoundaryQuadTree and to save the quadtree.
Maybe we want the same but we are talking in a different way about that. Let me try in other words: The preparer creates *non overlapping* areas containing all boundary information. So each point lies only in one (or none) precompiled area (ignoring the fact that there is a problem when a point lies exactly on the edge of an area). The area can be used to tag the point (which also mean a way using one point) with all available boundary information. In the end this would be the same result as your intended merge step (if we ignore the quadtree structure). This precompiled information is stored to the bnd files and loaded by mkgmaps LocationHook. The LocationHook creates the BoundaryQuadTree from this information and because of the precompilation no more merge step is required. Do you aggree?
If we can save the quadtree in a format that can be loaded faster than the time that is now needed to load the .bnd files plus calculating the quadtree, I'd vote for optimizing it for the preparer.
The preparer would have to do the merge step: From the given boundaries create not overlapping areas with all location information. I would not try to store additional quadtree information. You can try but I don't expect any measurable improvements by that.
Okay, that sound's like a good alternative with the advantage that we can keep the format of the bnd files.
All in all: Please keep the format of the bnd files as simple as possible and think about using it for other purposes. e.g. the current format could easily be used for coastline processing - one can precompile the coastlines and mgkmap could load the sea areas from the precompiled sea file. This would be great to have (a big!! performance and quality improvement). But someone needs to implement that.
I did not look at coastline processing until now, but if that requires optimization than I will do after fixing the remaining problems.
Yes, it's not a very big deal when you know the system of the precompiled bounds. But it would be a great improvement (also for people with fewer GBs of memory). WanMil