Commit: r1367: Rewrite pickArea() to avoid a problem with unequally sized areas.
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. This new version simply iterates through the areas testing to see if the element is contained within one. It may be slower for large numbers of areas but at least it should get the answer right. Mind you, I don't think the number of areas is ever that large because the subdivision process just divides areas by something small like 2 or 4. So probably not really slower at all. Also, it now throws away elements that are outside of the whole area and emits an error message.
svn commit escribió:
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.
This new version simply iterates through the areas testing to see if the element is contained within one. It may be slower for large numbers of areas but at least it should get the answer right. Mind you, I don't think the number of areas is ever that large because the subdivision process just divides areas by something small like 2 or 4. So probably not really slower at all.
Also, it now throws away elements that are outside of the whole area and emits an error message. I suppose errors below come from this change, but, how to fix them? I have tried to download the areas reported from a couple of these errors, but JOSM just say "No data found for this area" GRAVE (MapArea): Map element with type 0x1c (class uk.me.parabola.mkgmap.general.MapLine at http://www.openstreetmap.org/?lat=41.95737&lon=-6.94390&zoom=17 is outside of the map area centred on http://www.openstreetmap.org/?lat=41.78339&lon=-6.42048&zoom=17 width = 22164 height = 33765
Hi Carlos,
I suppose errors below come from this change, but, how to fix them? I have tried to download the areas reported from a couple of these errors, but JOSM just say "No data found for this area"
Yes, those errors seem to be produced by large lines that cross areas that don't appear to have any other content. That's almost certainly a clue as to what is going wrong. So, I think the only way they will get fixed is when I (or anyone else) finds what's wrong with mkgmap that's causing this to happen. I am continuing to work on this issue. Cheers, Mark
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
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
participants (4)
-
Carlos Dávila -
Mark Burton -
Steve Ratcliffe -
svn commit