[mkgmap-dev] Splitting the entire planet in one pass.

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