[mkgmap-dev] [mkgmap-svn] Commit: r1367: Rewrite pickArea() to avoid a problem with unequally sized areas.

Wed Nov 11 23:50:37 GMT 2009

Hi Mark

On 11/11/09 11:21, svn commit wrote:
> Version 1367 was commited by markb on 2009-11-11 11:21:31 +0000 (Wed, 11 Nov 2009)
>
> Rewrite pickArea() to avoid a problem with unequally sized areas.
>
> The original pickArea() assumed that all the areas to choose from had
> the same widths and the same heights. Unfortunately, that is not true and
> so it was occasionally putting elements in the wrong area.

The split routine does or should divide into areas with equal widths
apart from the last one, but that is taken care of in pickArea().  If
it didn't that would be a bug, but I don't see that happening.

What I do see is objects being outside the area, so for example the
test for xcell < 0 (in the original code) is sometimes true, but
this also isn't really a problem in itself and you shouldn't drop the
objects just because they don't appear to be in the area - the areas are
expanded to cope with objects they contain via getFullBounds().

I believe the underlying problem is that there is nothing to stop a
subdivision getting too big due to a small number of large objects.
Imagine that a subdivision has just two objects that are close to the
maximum size positioned far enough apart that the combined bounding
box is too large for a subdivision.  I don't think there is anything
in the code to deal with this.  It won't be split if there are few
other objects, and even if it does get split they might still end up
in the same subdivision and you would have to split again and again
potentially until they were in different ones.

When you increased the maximum sizes of objects, the problem is almost
certainly going to occur with the background areas if nothing else.  I
always thought that they should be in their own subdivision because of
this.  Still, I think the problem can occur however much you limit the
maximum size of objects, although it might be easier to fix.

I think that the current recursive algorithm will be difficult to
modify to deal with this; a new approach is probably needed.

..Steve