[mkgmap-dev] Splitting the entire planet in one pass.From Scott Crosby scrosby at cs.rice.edu on Fri Sep 17 16:00:24 BST 2010
On Fri, Sep 17, 2010 at 2:06 AM, Chris Miller <chris_overseas at hotmail.com> wrote: >> A new set of patches and line of development in my tree. > > Wow, looks like you've been really busy on this. Fantastic work! Sounds like > you've implemented a lot of things I've wanted to investigate but haven't > even had time to look at let alone code up. And all the great performance > improvements aside, I think a lot of people will be very interested in the > potential of non-rectangular area support so they can clip to eg country > boundaries. > That requires having the OSMWriter object decide if it 'really' wants the point or not, IE, return false from nodeBelongsToThisArea() for points inside the bbox. Not too difficult, I suspect, if the polygon handling code is imported from osmosis and areas.list is extended to support giving polygon geometry information. > As I see it the one big remaining problem to solve is to include entire ways > & relations if one of their nodes falls within (or they encompass) an area. > I think only certain ways/rels need to be taken into account for this which > should make the problem a bit easier to deal with. Still not easy and requires postprocessing and multiple passes. Roughly, these two algo's will work, but it will NOT catch relations/ways that enter an area, but do not contain any nodes in the area: // Algorithm A: To catch all nodes in a way: Set overlap to 0. (Or a low value to try to catch ways that cross the boundary, but do not contain any nodes *in* the area.) Track which areas a way is in (already done in SplitProcessor.ways). Track nodes missing from ways/relations. If way/relation contains a node that is in area X output it in that file and look at the other node ID's in that way/relation. If any of them are not marked as being in area X, store them in a 'missedNodes' SparseInt2ShortMultiMap. In a second pass, output any nodes in the missedNodes map that are not in the coords Map (indicating that they have already been output), then adding them to the coords Map. In postprocessing, read each file and sort to place nodes at the beginning. Algorithm A will get the complete set of ways that cross the boundary in two passes, which means that if a relation contains a way across a boundary, at least that way will be complete, even if other ways in that relation are excluded. Algorithm B is complete, handling relations containing ways/relations, and correct, but much more expensive. // Algorithm B: This algorithm gets everything, eg, relations containing ways/relations and is much more expensive. Because relations can contain relations, we need to effectively implement a breadth first search across the relation graph, where missingXXXX are the 'grey' colored fringe, and coords/ways/relations are the 'black' visited nodes. Set overlap to 0. We saved which ways were output to which region in SplitProcessor.ways Save which relations were output to which areas in SplitProcessor.relations. If a relation references a way has not been output to the region in question, add the missing way to a missingWays map. If a relation references a relation that has not been output to the region in question, add the missing relation to a missingRelations map. In additional passes, output all ways/relations in the missingNodes/missingWays/missingRelations map which have not been already output, removing them from those maps when they are output. They may reference nodes/ways/relations that are not yet in coords/ways/relations, (ie, not output), causing the referenced nodes/ways/relations entities to be added to the missignNodes/missingWays/missingRelations map. Postprocess by sorting all of the data in each output file. it is possible, but the number of passes will be equal to the 2+maximum depth of the directed graph induced by relations. > (as an aside, if you want to read more along the lines of compressed oops, > take a look at http://blogs.sun.com/jrose/entry/fixnums_in_the_vm to see > where things are hopefully headed within the VM. It should, among other things, > make using autoboxed primitives much much cheaper) > Thanks for the link. Scott
- Previous message: [mkgmap-dev] Splitting the entire planet in one pass.
- Next message: [mkgmap-dev] Splitting the entire planet in one pass.
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
More information about the mkgmap-dev mailing list