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

Thu Nov 12 09:16:08 GMT 2009

Hi Steve,

Thanks for the info, comments inline...

> 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.
> 

Ah, yes, I can see how that works now - my mistake, I will revert my
changes.

> 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().

That's fine as long as the amount that the object is outside of the
area is so large that it exceeds the 15 bit offset from the centre of
the subdivision. Which is what happens with big lines/polygons.

> 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.

Yes, it's the splitting by bbox that is not right. 

> 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.

I am pondering whether for lines and polygons that they should be put
into each area that their bounding box intersects with and then they
can be clipped to within that area (or sub-areas if necessary).

Cheers,

Mark