Re: [mkgmap-dev] Empty rectangles in map
Hi Ticker, thanks, results look much better. I see no changes in "normal" files and only small change in the test case. Commited with r4701. Gerd Von: mkgmap-dev im Auftrag von Ticker Berkin Gesendet: Montag, 10. Mai 2021 13:32 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Empty rectangles in map Hi Gerd Here is the change that always splits polygons into subdivisions by dividing along the internal boundaries rather than clipping. It is more efficient and the empty rectangle problem goes away. Ticker On Wed, 2021-04-28 at 12:41 +, Gerd Petermann wrote: > Hi Ticker, > > okay, so I'll wait for your results. The v1 patch always produces > larger files with normal maps without visual effects, so it seems to > split more often than needed (or prohibit merging too often) > > Gerd > > > Von: mkgmap-dev im Auftrag > von Ticker Berkin > Gesendet: Mittwoch, 28. April 2021 14:26 > An: Development list for mkgmap > Betreff: Re: [mkgmap-dev] Empty rectangles in map > > Hi Gerd > > Here is patch configured for Method 1, with more clarity about how to > change. > > I think the best solution will be a super Method 4. For a 5 x 4 > subdivision grid it will reduces the number of polygon cuts from 80 > (5*4*4) to 19 (5-1+5*(4-1)). > > It shouldn't be too difficult to implement and I'll look at it next > week. > > Ticker > > On Wed, 2021-04-28 at 09:14 +, Gerd Petermann wrote: > > Hi Ticker, > > > > please create two separate patches for method 1 and 2. It's not > > obvious to me what changes are needed to get method 1. > > > > Gerd > > > > > > Von: mkgmap-dev im Auftrag > > von Ticker Berkin > > Gesendet: Dienstag, 27. April 2021 13:11 > > An: Development list for mkgmap > > Betreff: Re: [mkgmap-dev] Empty rectangles in map > > > > Hi Gerd and others > > > > The cause for this unrendered area is as follows: > > > > A large multipolygon (larger than the maximum size for a level 1 > > subdiv) exists, and is broken into some similar size pieces and > > some > > smaller pieces to expose inners/holes. The same problem can be > > caused > > by any polygons having these size properties. > > > > Option --order-by-decreasing-area is not in effect (with this > > option > > the problem goes away). > > > > At the outermost level, the large pieces are split into the grid of > > subdivs necessary to be within size limits. Small pieces that fit > > within a subdiv are allocated to the correct one. Intermediate > > pieces > > that extend out of the nominal subdiv bounds, but don't exceed the > > actual addressing limits, are allocated to an existing subdiv based > > on > > their centre. Larger pieces that fit in a subdiv but would cause > > size > > problems if added to an existing subdiv are given a subdiv of their > > own. > > > > At the next level down, each of the above subdivs will required > > splitting to fit within the addressing limits. The logic that did > > this > > used the subdiv bounds and split this into a grid. Then every > > element > > in the outer MapArea is processed as above (ie split, safely > > placed, > > placed with overlap or own subdiv) > > > > The problem is that the splitting algorithm simply goes through the > > child subdiv, clips the polygon to this size and saves the bits > > that > > are within the area. Polygon parts that are outside the defined > > outer > > level never get noticed! > > > > There are various possible solutions: > > > > Method 1: use the rigorous polygon splitting into subdivs that - > > -order > > -by-decreasing-area uses for levels above level 0. This is simple > > to > > implement, safe, mergeShapes might recombine more cut fragments as > > they > > are all together. Disadvantages are that, for a normal map, more > > polygons might be split, leading to larger RGN size (but not for > > bad > > -map-split.osm.pbf). The overall size is still less that with - > > -order > > -by... > > > > Method 2: When the child subdiv grid is created, use any expanded > > size > > of the parent subdiv. This stops overhanging bits of polygons being > > lost. Again, simple to implement. It results in overlapping subdivs > > at > > lower levels and I don't know this causes other problems, but > > probably > > not; this used to be done and still does for some sizes of polygons > &
Re: [mkgmap-dev] Empty rectangles in map
Hi Gerd Here is the change that always splits polygons into subdivisions by dividing along the internal boundaries rather than clipping. It is more efficient and the empty rectangle problem goes away. Ticker On Wed, 2021-04-28 at 12:41 +, Gerd Petermann wrote: > Hi Ticker, > > okay, so I'll wait for your results. The v1 patch always produces > larger files with normal maps without visual effects, so it seems to > split more often than needed (or prohibit merging too often) > > Gerd > > > Von: mkgmap-dev im Auftrag > von Ticker Berkin > Gesendet: Mittwoch, 28. April 2021 14:26 > An: Development list for mkgmap > Betreff: Re: [mkgmap-dev] Empty rectangles in map > > Hi Gerd > > Here is patch configured for Method 1, with more clarity about how to > change. > > I think the best solution will be a super Method 4. For a 5 x 4 > subdivision grid it will reduces the number of polygon cuts from 80 > (5*4*4) to 19 (5-1+5*(4-1)). > > It shouldn't be too difficult to implement and I'll look at it next > week. > > Ticker > > On Wed, 2021-04-28 at 09:14 +, Gerd Petermann wrote: > > Hi Ticker, > > > > please create two separate patches for method 1 and 2. It's not > > obvious to me what changes are needed to get method 1. > > > > Gerd > > > > > > Von: mkgmap-dev im Auftrag > > von Ticker Berkin > > Gesendet: Dienstag, 27. April 2021 13:11 > > An: Development list for mkgmap > > Betreff: Re: [mkgmap-dev] Empty rectangles in map > > > > Hi Gerd and others > > > > The cause for this unrendered area is as follows: > > > > A large multipolygon (larger than the maximum size for a level 1 > > subdiv) exists, and is broken into some similar size pieces and > > some > > smaller pieces to expose inners/holes. The same problem can be > > caused > > by any polygons having these size properties. > > > > Option --order-by-decreasing-area is not in effect (with this > > option > > the problem goes away). > > > > At the outermost level, the large pieces are split into the grid of > > subdivs necessary to be within size limits. Small pieces that fit > > within a subdiv are allocated to the correct one. Intermediate > > pieces > > that extend out of the nominal subdiv bounds, but don't exceed the > > actual addressing limits, are allocated to an existing subdiv based > > on > > their centre. Larger pieces that fit in a subdiv but would cause > > size > > problems if added to an existing subdiv are given a subdiv of their > > own. > > > > At the next level down, each of the above subdivs will required > > splitting to fit within the addressing limits. The logic that did > > this > > used the subdiv bounds and split this into a grid. Then every > > element > > in the outer MapArea is processed as above (ie split, safely > > placed, > > placed with overlap or own subdiv) > > > > The problem is that the splitting algorithm simply goes through the > > child subdiv, clips the polygon to this size and saves the bits > > that > > are within the area. Polygon parts that are outside the defined > > outer > > level never get noticed! > > > > There are various possible solutions: > > > > Method 1: use the rigorous polygon splitting into subdivs that - > > -order > > -by-decreasing-area uses for levels above level 0. This is simple > > to > > implement, safe, mergeShapes might recombine more cut fragments as > > they > > are all together. Disadvantages are that, for a normal map, more > > polygons might be split, leading to larger RGN size (but not for > > bad > > -map-split.osm.pbf). The overall size is still less that with - > > -order > > -by... > > > > Method 2: When the child subdiv grid is created, use any expanded > > size > > of the parent subdiv. This stops overhanging bits of polygons being > > lost. Again, simple to implement. It results in overlapping subdivs > > at > > lower levels and I don't know this causes other problems, but > > probably > > not; this used to be done and still does for some sizes of polygons > > and > > lines. Some shape-merging won't happen because the joining bits are > > in > > a different subdiv. > > > > Method 3: Allocated oversize polygons to their own subdiv. Again, > > simple to implement, but I see no advantage over Method 2. Even > > more > > shape-merging might n
Re: [mkgmap-dev] Empty rectangles in map
Hi Ticker, okay, so I'll wait for your results. The v1 patch always produces larger files with normal maps without visual effects, so it seems to split more often than needed (or prohibit merging too often) Gerd Von: mkgmap-dev im Auftrag von Ticker Berkin Gesendet: Mittwoch, 28. April 2021 14:26 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Empty rectangles in map Hi Gerd Here is patch configured for Method 1, with more clarity about how to change. I think the best solution will be a super Method 4. For a 5 x 4 subdivision grid it will reduces the number of polygon cuts from 80 (5*4*4) to 19 (5-1+5*(4-1)). It shouldn't be too difficult to implement and I'll look at it next week. Ticker On Wed, 2021-04-28 at 09:14 +, Gerd Petermann wrote: > Hi Ticker, > > please create two separate patches for method 1 and 2. It's not > obvious to me what changes are needed to get method 1. > > Gerd > > > Von: mkgmap-dev im Auftrag > von Ticker Berkin > Gesendet: Dienstag, 27. April 2021 13:11 > An: Development list for mkgmap > Betreff: Re: [mkgmap-dev] Empty rectangles in map > > Hi Gerd and others > > The cause for this unrendered area is as follows: > > A large multipolygon (larger than the maximum size for a level 1 > subdiv) exists, and is broken into some similar size pieces and some > smaller pieces to expose inners/holes. The same problem can be caused > by any polygons having these size properties. > > Option --order-by-decreasing-area is not in effect (with this option > the problem goes away). > > At the outermost level, the large pieces are split into the grid of > subdivs necessary to be within size limits. Small pieces that fit > within a subdiv are allocated to the correct one. Intermediate pieces > that extend out of the nominal subdiv bounds, but don't exceed the > actual addressing limits, are allocated to an existing subdiv based > on > their centre. Larger pieces that fit in a subdiv but would cause size > problems if added to an existing subdiv are given a subdiv of their > own. > > At the next level down, each of the above subdivs will required > splitting to fit within the addressing limits. The logic that did > this > used the subdiv bounds and split this into a grid. Then every element > in the outer MapArea is processed as above (ie split, safely placed, > placed with overlap or own subdiv) > > The problem is that the splitting algorithm simply goes through the > child subdiv, clips the polygon to this size and saves the bits that > are within the area. Polygon parts that are outside the defined outer > level never get noticed! > > There are various possible solutions: > > Method 1: use the rigorous polygon splitting into subdivs that - > -order > -by-decreasing-area uses for levels above level 0. This is simple to > implement, safe, mergeShapes might recombine more cut fragments as > they > are all together. Disadvantages are that, for a normal map, more > polygons might be split, leading to larger RGN size (but not for bad > -map-split.osm.pbf). The overall size is still less that with --order > -by... > > Method 2: When the child subdiv grid is created, use any expanded > size > of the parent subdiv. This stops overhanging bits of polygons being > lost. Again, simple to implement. It results in overlapping subdivs > at > lower levels and I don't know this causes other problems, but > probably > not; this used to be done and still does for some sizes of polygons > and > lines. Some shape-merging won't happen because the joining bits are > in > a different subdiv. > > Method 3: Allocated oversize polygons to their own subdiv. Again, > simple to implement, but I see no advantage over Method 2. Even more > shape-merging might not happen. > > Method 4: Detect when an object will have bits missed and semi-cut > rather than clip them to continue having an oversize part in the > child > subdiv. This is more complicated to implement but, if done, could > replace the clipping code and be more efficient. If a parent subDiv > is > divided into 2 children, it already happens like this. > > Although I prefer Method 1, I suspect Method 2 is what should be done > in the short-term and so I've attached a patch that is configured for > Method 2, but, with a couple of edits to change some flag handling, > does Method 1. > > Ticker > > ___ > mkgmap-dev mailing list > mkgmap-dev@lists.mkgmap.org.uk > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Empty rectangles in map
Hi Gerd
Here is patch configured for Method 1, with more clarity about how to
change.
I think the best solution will be a super Method 4. For a 5 x 4
subdivision grid it will reduces the number of polygon cuts from 80
(5*4*4) to 19 (5-1+5*(4-1)).
It shouldn't be too difficult to implement and I'll look at it next
week.
Ticker
On Wed, 2021-04-28 at 09:14 +, Gerd Petermann wrote:
> Hi Ticker,
>
> please create two separate patches for method 1 and 2. It's not
> obvious to me what changes are needed to get method 1.
>
> Gerd
>
>
> Von: mkgmap-dev im Auftrag
> von Ticker Berkin
> Gesendet: Dienstag, 27. April 2021 13:11
> An: Development list for mkgmap
> Betreff: Re: [mkgmap-dev] Empty rectangles in map
>
> Hi Gerd and others
>
> The cause for this unrendered area is as follows:
>
> A large multipolygon (larger than the maximum size for a level 1
> subdiv) exists, and is broken into some similar size pieces and some
> smaller pieces to expose inners/holes. The same problem can be caused
> by any polygons having these size properties.
>
> Option --order-by-decreasing-area is not in effect (with this option
> the problem goes away).
>
> At the outermost level, the large pieces are split into the grid of
> subdivs necessary to be within size limits. Small pieces that fit
> within a subdiv are allocated to the correct one. Intermediate pieces
> that extend out of the nominal subdiv bounds, but don't exceed the
> actual addressing limits, are allocated to an existing subdiv based
> on
> their centre. Larger pieces that fit in a subdiv but would cause size
> problems if added to an existing subdiv are given a subdiv of their
> own.
>
> At the next level down, each of the above subdivs will required
> splitting to fit within the addressing limits. The logic that did
> this
> used the subdiv bounds and split this into a grid. Then every element
> in the outer MapArea is processed as above (ie split, safely placed,
> placed with overlap or own subdiv)
>
> The problem is that the splitting algorithm simply goes through the
> child subdiv, clips the polygon to this size and saves the bits that
> are within the area. Polygon parts that are outside the defined outer
> level never get noticed!
>
> There are various possible solutions:
>
> Method 1: use the rigorous polygon splitting into subdivs that -
> -order
> -by-decreasing-area uses for levels above level 0. This is simple to
> implement, safe, mergeShapes might recombine more cut fragments as
> they
> are all together. Disadvantages are that, for a normal map, more
> polygons might be split, leading to larger RGN size (but not for bad
> -map-split.osm.pbf). The overall size is still less that with --order
> -by...
>
> Method 2: When the child subdiv grid is created, use any expanded
> size
> of the parent subdiv. This stops overhanging bits of polygons being
> lost. Again, simple to implement. It results in overlapping subdivs
> at
> lower levels and I don't know this causes other problems, but
> probably
> not; this used to be done and still does for some sizes of polygons
> and
> lines. Some shape-merging won't happen because the joining bits are
> in
> a different subdiv.
>
> Method 3: Allocated oversize polygons to their own subdiv. Again,
> simple to implement, but I see no advantage over Method 2. Even more
> shape-merging might not happen.
>
> Method 4: Detect when an object will have bits missed and semi-cut
> rather than clip them to continue having an oversize part in the
> child
> subdiv. This is more complicated to implement but, if done, could
> replace the clipping code and be more efficient. If a parent subDiv
> is
> divided into 2 children, it already happens like this.
>
> Although I prefer Method 1, I suspect Method 2 is what should be done
> in the short-term and so I've attached a patch that is configured for
> Method 2, but, with a couple of edits to change some flag handling,
> does Method 1.
>
> Ticker
>
> ___
> mkgmap-dev mailing list
> mkgmap-dev@lists.mkgmap.org.uk
> https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-devIndex: src/uk/me/parabola/mkgmap/build/MapArea.java
===
--- src/uk/me/parabola/mkgmap/build/MapArea.java (revision 4687)
+++ src/uk/me/parabola/mkgmap/build/MapArea.java (working copy)
@@ -257,14 +257,16 @@
continue;
}
int areaIndex = pickArea(mapAreas, e, xbaseHp, ybaseHp, nx, ny, dxHp, dyHp);
-if ((shapeBounds.getHeight() > maxHeight || shapeBounds.getWidth() > maxWidth) &&
-!areas[areaIndex].contains(shapeBounds)) {
+
Re: [mkgmap-dev] Empty rectangles in map
Hi Ticker, please create two separate patches for method 1 and 2. It's not obvious to me what changes are needed to get method 1. Gerd Von: mkgmap-dev im Auftrag von Ticker Berkin Gesendet: Dienstag, 27. April 2021 13:11 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Empty rectangles in map Hi Gerd and others The cause for this unrendered area is as follows: A large multipolygon (larger than the maximum size for a level 1 subdiv) exists, and is broken into some similar size pieces and some smaller pieces to expose inners/holes. The same problem can be caused by any polygons having these size properties. Option --order-by-decreasing-area is not in effect (with this option the problem goes away). At the outermost level, the large pieces are split into the grid of subdivs necessary to be within size limits. Small pieces that fit within a subdiv are allocated to the correct one. Intermediate pieces that extend out of the nominal subdiv bounds, but don't exceed the actual addressing limits, are allocated to an existing subdiv based on their centre. Larger pieces that fit in a subdiv but would cause size problems if added to an existing subdiv are given a subdiv of their own. At the next level down, each of the above subdivs will required splitting to fit within the addressing limits. The logic that did this used the subdiv bounds and split this into a grid. Then every element in the outer MapArea is processed as above (ie split, safely placed, placed with overlap or own subdiv) The problem is that the splitting algorithm simply goes through the child subdiv, clips the polygon to this size and saves the bits that are within the area. Polygon parts that are outside the defined outer level never get noticed! There are various possible solutions: Method 1: use the rigorous polygon splitting into subdivs that --order -by-decreasing-area uses for levels above level 0. This is simple to implement, safe, mergeShapes might recombine more cut fragments as they are all together. Disadvantages are that, for a normal map, more polygons might be split, leading to larger RGN size (but not for bad -map-split.osm.pbf). The overall size is still less that with --order -by... Method 2: When the child subdiv grid is created, use any expanded size of the parent subdiv. This stops overhanging bits of polygons being lost. Again, simple to implement. It results in overlapping subdivs at lower levels and I don't know this causes other problems, but probably not; this used to be done and still does for some sizes of polygons and lines. Some shape-merging won't happen because the joining bits are in a different subdiv. Method 3: Allocated oversize polygons to their own subdiv. Again, simple to implement, but I see no advantage over Method 2. Even more shape-merging might not happen. Method 4: Detect when an object will have bits missed and semi-cut rather than clip them to continue having an oversize part in the child subdiv. This is more complicated to implement but, if done, could replace the clipping code and be more efficient. If a parent subDiv is divided into 2 children, it already happens like this. Although I prefer Method 1, I suspect Method 2 is what should be done in the short-term and so I've attached a patch that is configured for Method 2, but, with a couple of edits to change some flag handling, does Method 1. Ticker ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Empty rectangles in map
Hi Gerd I had to zoom in to < 10miles, with detail set to "Highest", before the forest appeared. It was difficult to know where to start from. Then, at that level, it is very tedious to scroll around trying to finds the holes. Ticker On Tue, 2021-04-27 at 12:48 +, Gerd Petermann wrote: > Hi Ticker, > > thanks for investigating. I've used the patch with trunk r4680 and > just --gmapi option. > I see that GpsMapEdit shows no hole, but Mapsource and Basecamp still > don't show the map. Any idea why? > > Gerd > > > Von: mkgmap-dev im Auftrag > von Ticker Berkin > Gesendet: Dienstag, 27. April 2021 13:11 > An: Development list for mkgmap > Betreff: Re: [mkgmap-dev] Empty rectangles in map > > Hi Gerd and others > > The cause for this unrendered area is as follows: > > A large multipolygon (larger than the maximum size for a level 1 > subdiv) exists, and is broken into some similar size pieces and some > smaller pieces to expose inners/holes. The same problem can be caused > by any polygons having these size properties. > > Option --order-by-decreasing-area is not in effect (with this option > the problem goes away). > > At the outermost level, the large pieces are split into the grid of > subdivs necessary to be within size limits. Small pieces that fit > within a subdiv are allocated to the correct one. Intermediate pieces > that extend out of the nominal subdiv bounds, but don't exceed the > actual addressing limits, are allocated to an existing subdiv based > on > their centre. Larger pieces that fit in a subdiv but would cause size > problems if added to an existing subdiv are given a subdiv of their > own. > > At the next level down, each of the above subdivs will required > splitting to fit within the addressing limits. The logic that did > this > used the subdiv bounds and split this into a grid. Then every element > in the outer MapArea is processed as above (ie split, safely placed, > placed with overlap or own subdiv) > > The problem is that the splitting algorithm simply goes through the > child subdiv, clips the polygon to this size and saves the bits that > are within the area. Polygon parts that are outside the defined outer > level never get noticed! > > There are various possible solutions: > > Method 1: use the rigorous polygon splitting into subdivs that - > -order > -by-decreasing-area uses for levels above level 0. This is simple to > implement, safe, mergeShapes might recombine more cut fragments as > they > are all together. Disadvantages are that, for a normal map, more > polygons might be split, leading to larger RGN size (but not for bad > -map-split.osm.pbf). The overall size is still less that with --order > -by... > > Method 2: When the child subdiv grid is created, use any expanded > size > of the parent subdiv. This stops overhanging bits of polygons being > lost. Again, simple to implement. It results in overlapping subdivs > at > lower levels and I don't know this causes other problems, but > probably > not; this used to be done and still does for some sizes of polygons > and > lines. Some shape-merging won't happen because the joining bits are > in > a different subdiv. > > Method 3: Allocated oversize polygons to their own subdiv. Again, > simple to implement, but I see no advantage over Method 2. Even more > shape-merging might not happen. > > Method 4: Detect when an object will have bits missed and semi-cut > rather than clip them to continue having an oversize part in the > child > subdiv. This is more complicated to implement but, if done, could > replace the clipping code and be more efficient. If a parent subDiv > is > divided into 2 children, it already happens like this. > > Although I prefer Method 1, I suspect Method 2 is what should be done > in the short-term and so I've attached a patch that is configured for > Method 2, but, with a couple of edits to change some flag handling, > does Method 1. > > Ticker > > ___ > mkgmap-dev mailing list > mkgmap-dev@lists.mkgmap.org.uk > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Empty rectangles in map
Hi Ticker, thanks for investigating. I've used the patch with trunk r4680 and just --gmapi option. I see that GpsMapEdit shows no hole, but Mapsource and Basecamp still don't show the map. Any idea why? Gerd Von: mkgmap-dev im Auftrag von Ticker Berkin Gesendet: Dienstag, 27. April 2021 13:11 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Empty rectangles in map Hi Gerd and others The cause for this unrendered area is as follows: A large multipolygon (larger than the maximum size for a level 1 subdiv) exists, and is broken into some similar size pieces and some smaller pieces to expose inners/holes. The same problem can be caused by any polygons having these size properties. Option --order-by-decreasing-area is not in effect (with this option the problem goes away). At the outermost level, the large pieces are split into the grid of subdivs necessary to be within size limits. Small pieces that fit within a subdiv are allocated to the correct one. Intermediate pieces that extend out of the nominal subdiv bounds, but don't exceed the actual addressing limits, are allocated to an existing subdiv based on their centre. Larger pieces that fit in a subdiv but would cause size problems if added to an existing subdiv are given a subdiv of their own. At the next level down, each of the above subdivs will required splitting to fit within the addressing limits. The logic that did this used the subdiv bounds and split this into a grid. Then every element in the outer MapArea is processed as above (ie split, safely placed, placed with overlap or own subdiv) The problem is that the splitting algorithm simply goes through the child subdiv, clips the polygon to this size and saves the bits that are within the area. Polygon parts that are outside the defined outer level never get noticed! There are various possible solutions: Method 1: use the rigorous polygon splitting into subdivs that --order -by-decreasing-area uses for levels above level 0. This is simple to implement, safe, mergeShapes might recombine more cut fragments as they are all together. Disadvantages are that, for a normal map, more polygons might be split, leading to larger RGN size (but not for bad -map-split.osm.pbf). The overall size is still less that with --order -by... Method 2: When the child subdiv grid is created, use any expanded size of the parent subdiv. This stops overhanging bits of polygons being lost. Again, simple to implement. It results in overlapping subdivs at lower levels and I don't know this causes other problems, but probably not; this used to be done and still does for some sizes of polygons and lines. Some shape-merging won't happen because the joining bits are in a different subdiv. Method 3: Allocated oversize polygons to their own subdiv. Again, simple to implement, but I see no advantage over Method 2. Even more shape-merging might not happen. Method 4: Detect when an object will have bits missed and semi-cut rather than clip them to continue having an oversize part in the child subdiv. This is more complicated to implement but, if done, could replace the clipping code and be more efficient. If a parent subDiv is divided into 2 children, it already happens like this. Although I prefer Method 1, I suspect Method 2 is what should be done in the short-term and so I've attached a patch that is configured for Method 2, but, with a couple of edits to change some flag handling, does Method 1. Ticker ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Empty rectangles in map
Hi Gerd and others
The cause for this unrendered area is as follows:
A large multipolygon (larger than the maximum size for a level 1
subdiv) exists, and is broken into some similar size pieces and some
smaller pieces to expose inners/holes. The same problem can be caused
by any polygons having these size properties.
Option --order-by-decreasing-area is not in effect (with this option
the problem goes away).
At the outermost level, the large pieces are split into the grid of
subdivs necessary to be within size limits. Small pieces that fit
within a subdiv are allocated to the correct one. Intermediate pieces
that extend out of the nominal subdiv bounds, but don't exceed the
actual addressing limits, are allocated to an existing subdiv based on
their centre. Larger pieces that fit in a subdiv but would cause size
problems if added to an existing subdiv are given a subdiv of their
own.
At the next level down, each of the above subdivs will required
splitting to fit within the addressing limits. The logic that did this
used the subdiv bounds and split this into a grid. Then every element
in the outer MapArea is processed as above (ie split, safely placed,
placed with overlap or own subdiv)
The problem is that the splitting algorithm simply goes through the
child subdiv, clips the polygon to this size and saves the bits that
are within the area. Polygon parts that are outside the defined outer
level never get noticed!
There are various possible solutions:
Method 1: use the rigorous polygon splitting into subdivs that --order
-by-decreasing-area uses for levels above level 0. This is simple to
implement, safe, mergeShapes might recombine more cut fragments as they
are all together. Disadvantages are that, for a normal map, more
polygons might be split, leading to larger RGN size (but not for bad
-map-split.osm.pbf). The overall size is still less that with --order
-by...
Method 2: When the child subdiv grid is created, use any expanded size
of the parent subdiv. This stops overhanging bits of polygons being
lost. Again, simple to implement. It results in overlapping subdivs at
lower levels and I don't know this causes other problems, but probably
not; this used to be done and still does for some sizes of polygons and
lines. Some shape-merging won't happen because the joining bits are in
a different subdiv.
Method 3: Allocated oversize polygons to their own subdiv. Again,
simple to implement, but I see no advantage over Method 2. Even more
shape-merging might not happen.
Method 4: Detect when an object will have bits missed and semi-cut
rather than clip them to continue having an oversize part in the child
subdiv. This is more complicated to implement but, if done, could
replace the clipping code and be more efficient. If a parent subDiv is
divided into 2 children, it already happens like this.
Although I prefer Method 1, I suspect Method 2 is what should be done
in the short-term and so I've attached a patch that is configured for
Method 2, but, with a couple of edits to change some flag handling,
does Method 1.
Ticker
Index: src/uk/me/parabola/mkgmap/build/MapArea.java
===
--- src/uk/me/parabola/mkgmap/build/MapArea.java (revision 4685)
+++ src/uk/me/parabola/mkgmap/build/MapArea.java (working copy)
@@ -257,14 +257,16 @@
continue;
}
int areaIndex = pickArea(mapAreas, e, xbaseHp, ybaseHp, nx, ny, dxHp, dyHp);
-if ((shapeBounds.getHeight() > maxHeight || shapeBounds.getWidth() > maxWidth) &&
-!areas[areaIndex].contains(shapeBounds)) {
+if (areas[areaIndex].contains(shapeBounds)) {
+ mapAreas[areaIndex].addShape(e);
+} else if (shapeBounds.getHeight() <= maxHeight && shapeBounds.getWidth() <= maxWidth) {
+ // this polygon is partially outside the subdivision, but won't exceed the allowable offsets
+ mapAreas[areaIndex].addShape(e);
+} else {
MapArea largeObjectArea = new MapArea(shapeBounds, areaResolution, true); // use splitIntoAreas to deal with overflow
largeObjectArea.addShape(e);
addedAreas.add(largeObjectArea);
- continue;
}
-mapAreas[areaIndex].addShape(e);
}
}
Index: src/uk/me/parabola/mkgmap/build/MapBuilder.java
===
--- src/uk/me/parabola/mkgmap/build/MapBuilder.java (revision 4685)
+++ src/uk/me/parabola/mkgmap/build/MapBuilder.java (working copy)
@@ -803,11 +803,15 @@
List nextList = new ArrayList<>();
Zoom zoom = map.createZoom(linfo.getLevel(), linfo.getBits());
+ //%%%mbs see also MapSpltter.split()
+ // method 1: true at levels > 0, depends on --order-by for level 9
+ // method 2: depends on --order-by for all levels
+ boolean splitPolygonsIntoArea = /* linfo.getLevel() != 0 ? true : */ orderByDecreasingArea;
for (SourceSubdiv srcDivPair : srcList) {
MapSplitter splitter = new MapSplitter(srcDivPair.getSource(), zoom);
-MapArea[]
Re: [mkgmap-dev] Empty rectangles in map
Hi Gerd I think I'm getting somewhere with this and will try and have a proper fix in a day or so. It is related to subdivision splitting. Ticker ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Empty rectangles in map
Hi Gerd A few more things I've discovered. GPSMapEdit will show bands of emptyness for a thin, correct, slice when you zoom out but with the view zoom level locked at a higher resolution than it expects. This confused some of my previous findings. Changing some sizes changes the behaviour and I sometimes get the holes at level 1 but level 2 is OK. 3 of the edges of the hole correspond to cut-lines to get at the cluster of 'islands', but the 4th corresponds to the subdivision max -size splitting, so it looks like the problem might be related to MapBuilder/MapSplitter/MapArea logic. With option --x-no-mergeshapes (and current trunk) it appears that cutting to this island group happens twice from the left, with 1 line continuing to the right and twice from the top, with 1 line continuing to the bottom. Ticker On Sun, 2021-04-25 at 13:50 +0100, Ticker Berkin wrote: > Hi Gerd > > More more testing with standard style / options etc. As well as - > -order > -by, I had some level params that confused. > > With GPSMapEdit at Zoom level 2, there is a wide cut from the LHS > forest triangle to the holes around 54.9953,-58.2209. It seems to be > the total height of the holes. > > Similar shows in MapSource, but it much more difficult to find. > Resolution needs to be <= 7mi before forest kicks-in. I didn't > investigate how far left the blank area went. > > Looking more closely on Basecamp, the blank area is a rectangle > approx > 54.975,-58.302 to 55.0178,-58.6247, ie it doesn't go to the edge of > the > forest triangle. Also it only shows when detail-level is set to > "highest" > > Ticker > > On Sun, 2021-04-25 at 11:03 +0100, Ticker Berkin wrote: > > Hi Gerd > > > > Just tried this with latest trunk and my standard environment > > (mainly > > --order-by-decreasing-area > > and get very inconsistent results. > > > > On GPSMapEdit seems reasonable - shows forest triangle and, within, > > a > > small area with a number of holes. > > > > MapSource shows a white square, no forest colour and I can't move > > the > > map around, also it doesn't seem to zoom out enough. First time I > > looked I saw 2 white squares. > > > > Basecamp shows the forest triangle, but I can't find the > > islands/holes > > > > I've had problems before with MapSource or Basecamp caches, so I'll > > delete these. Also try with simple options etc > > > > Ticker > > > > > > On Sun, 2021-04-25 at 07:31 +, Gerd Petermann wrote: > > > Hi Experts, > > > > > > while working on the faster-mp branch I experimented with the > > > monster > > > relation r9488835. I added tag landuse=forest to it so that it is > > > actually rendered and found huge (wrong) empty rectangles in the > > > forest. > > > The original file is very complex but the same problem also > > > occurs > > > with a simplified file, see > > > http://files.mkgmap.org.uk/download/505/bad-map-split.osm.pbf > > > Just use e.g. > > > java -jar mkgmap.jar --gmapi bad-map-split.osm.pbf > > > Problem: Basecamp and Mapsource don't show this map, GpsMapEdit > > > shows > > > a large white rectangle near 54.97743 -58.30292 > > > > > > I assume that we hit some unknown limit , possibly in > > > LinePreparer > > > or > > > MapSplitter. > > > I've also tried some older versions, so far they all show the > > > problem. > > > Any idea where to look? > > > > > > RgnDisplay shows this data for the problemat area: > > > - Level 0, Subdiv 279 --- > > > -- > > > -- > > > --- > > > || | final at 265f, (end > > > 25e2) > > > || | polygon start 2634 > > > to > > > 265f > > > 2634 | 00 | 4b | Polygon 1 > > > || | Type 0x4b > > > 2635 | 01 | 00 00 00| Label offset: > > > 0x00 > > > () > > > 2638 | 04 | d0 3b | Long delta 15312 > > > 263a | 06 | 2a 3a | Lat delta 14890 > > > || | Start point > > > 55.24913, > > > -61.91139 2574796/-2885280 > > > 263c | 08 | 0c | Bitstream length 12 > > > 263d | 09 | bb | Base bb > > > 263e | 0a | 06 43 04 00 00 00 4c d1 | Bitstream (len: 12, > > > 0xc) > > > 2646 | 12 | 41 ef 00 00 | > > > || | xsame false, xneg > > > false > > > || | ysame true, yneg > > > true > > > || | xbase 16, ybase 15 > > > || | Coord 55.24913, > > > -62.56851 2574796/-2915904 [-30624,+0] > > > || | Coord 54.61014, > > > -62.56851 2545017/-2915904 [+0,-29779] > > > || | Coord 54.61014, > > > -61.91139 2545017/-2885280 [+30624,+0] > > >
Re: [mkgmap-dev] Empty rectangles in map
Hi Gerd More more testing with standard style / options etc. As well as --order -by, I had some level params that confused. With GPSMapEdit at Zoom level 2, there is a wide cut from the LHS forest triangle to the holes around 54.9953,-58.2209. It seems to be the total height of the holes. Similar shows in MapSource, but it much more difficult to find. Resolution needs to be <= 7mi before forest kicks-in. I didn't investigate how far left the blank area went. Looking more closely on Basecamp, the blank area is a rectangle approx 54.975,-58.302 to 55.0178,-58.6247, ie it doesn't go to the edge of the forest triangle. Also it only shows when detail-level is set to "highest" Ticker On Sun, 2021-04-25 at 11:03 +0100, Ticker Berkin wrote: > Hi Gerd > > Just tried this with latest trunk and my standard environment (mainly > --order-by-decreasing-area > and get very inconsistent results. > > On GPSMapEdit seems reasonable - shows forest triangle and, within, a > small area with a number of holes. > > MapSource shows a white square, no forest colour and I can't move the > map around, also it doesn't seem to zoom out enough. First time I > looked I saw 2 white squares. > > Basecamp shows the forest triangle, but I can't find the > islands/holes > > I've had problems before with MapSource or Basecamp caches, so I'll > delete these. Also try with simple options etc > > Ticker > > > On Sun, 2021-04-25 at 07:31 +, Gerd Petermann wrote: > > Hi Experts, > > > > while working on the faster-mp branch I experimented with the > > monster > > relation r9488835. I added tag landuse=forest to it so that it is > > actually rendered and found huge (wrong) empty rectangles in the > > forest. > > The original file is very complex but the same problem also occurs > > with a simplified file, see > > http://files.mkgmap.org.uk/download/505/bad-map-split.osm.pbf > > Just use e.g. > > java -jar mkgmap.jar --gmapi bad-map-split.osm.pbf > > Problem: Basecamp and Mapsource don't show this map, GpsMapEdit > > shows > > a large white rectangle near 54.97743 -58.30292 > > > > I assume that we hit some unknown limit , possibly in LinePreparer > > or > > MapSplitter. > > I've also tried some older versions, so far they all show the > > problem. > > Any idea where to look? > > > > RgnDisplay shows this data for the problemat area: > > - Level 0, Subdiv 279 - > > -- > > --- > > || | final at 265f, (end > > 25e2) > > || | polygon start 2634 to > > 265f > > 2634 | 00 | 4b | Polygon 1 > > || | Type 0x4b > > 2635 | 01 | 00 00 00| Label offset: > > 0x00 > > () > > 2638 | 04 | d0 3b | Long delta 15312 > > 263a | 06 | 2a 3a | Lat delta 14890 > > || | Start point 55.24913, > > -61.91139 2574796/-2885280 > > 263c | 08 | 0c | Bitstream length 12 > > 263d | 09 | bb | Base bb > > 263e | 0a | 06 43 04 00 00 00 4c d1 | Bitstream (len: 12, > > 0xc) > > 2646 | 12 | 41 ef 00 00 | > > || | xsame false, xneg > > false > > || | ysame true, yneg true > > || | xbase 16, ybase 15 > > || | Coord 55.24913, > > -62.56851 2574796/-2915904 [-30624,+0] > > || | Coord 54.61014, > > -62.56851 2545017/-2915904 [+0,-29779] > > || | Coord 54.61014, > > -61.91139 2545017/-2885280 [+30624,+0] > > || | 0 bits left, 0 > > || | > > 264a | 16 | 50 | Polygon 2 > > || | Type 0x50 > > 264b | 17 | 00 00 00| Label offset: > > 0x00 > > () > > 264e | 1a | d0 3b | Long delta 15312 > > 2650 | 1c | b4 08 | Lat delta 2228 > > || | Start point 54.97743, > > -61.91139 2562134/-2885280 > > 2652 | 1e | 0b | Bitstream length 11 > > 2653 | 1f | 9b | Base 9b > > 2654 | 20 | f2 8d 04 40 a7 fe d0 4b | Bitstream (len: 11, > > 0xb) > > 265c | 28 | e7 00 00| > > || | xsame false, xneg > > false > > || | ysame true, yneg > > false > > || | xbase 16, ybase 11 > > || | Coord 54.97743, > > -62.51706 2562134/-2913506
Re: [mkgmap-dev] Empty rectangles in map
Hi Ticker, yes, install the pbf plugin. Gerd Von: mkgmap-dev im Auftrag von Ticker Berkin Gesendet: Sonntag, 25. April 2021 12:20 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Empty rectangles in map Hi Gerd Is there a simple way to look at an .osm.pbf file with JOSM? Ticker ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Empty rectangles in map
Hi Gerd Is there a simple way to look at an .osm.pbf file with JOSM? Ticker ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Re: [mkgmap-dev] Empty rectangles in map
Hi Gerd Just tried this with latest trunk and my standard environment (mainly --order-by-decreasing-area and get very inconsistent results. On GPSMapEdit seems reasonable - shows forest triangle and, within, a small area with a number of holes. MapSource shows a white square, no forest colour and I can't move the map around, also it doesn't seem to zoom out enough. First time I looked I saw 2 white squares. Basecamp shows the forest triangle, but I can't find the islands/holes I've had problems before with MapSource or Basecamp caches, so I'll delete these. Also try with simple options etc Ticker On Sun, 2021-04-25 at 07:31 +, Gerd Petermann wrote: > Hi Experts, > > while working on the faster-mp branch I experimented with the monster > relation r9488835. I added tag landuse=forest to it so that it is > actually rendered and found huge (wrong) empty rectangles in the > forest. > The original file is very complex but the same problem also occurs > with a simplified file, see > http://files.mkgmap.org.uk/download/505/bad-map-split.osm.pbf > Just use e.g. > java -jar mkgmap.jar --gmapi bad-map-split.osm.pbf > Problem: Basecamp and Mapsource don't show this map, GpsMapEdit shows > a large white rectangle near 54.97743 -58.30292 > > I assume that we hit some unknown limit , possibly in LinePreparer or > MapSplitter. > I've also tried some older versions, so far they all show the > problem. > Any idea where to look? > > RgnDisplay shows this data for the problemat area: > - Level 0, Subdiv 279 --- > --- > || | final at 265f, (end > 25e2) > || | polygon start 2634 to > 265f > 2634 | 00 | 4b | Polygon 1 > || | Type 0x4b > 2635 | 01 | 00 00 00| Label offset: 0x00 > () > 2638 | 04 | d0 3b | Long delta 15312 > 263a | 06 | 2a 3a | Lat delta 14890 > || | Start point 55.24913, > -61.91139 2574796/-2885280 > 263c | 08 | 0c | Bitstream length 12 > 263d | 09 | bb | Base bb > 263e | 0a | 06 43 04 00 00 00 4c d1 | Bitstream (len: 12, > 0xc) > 2646 | 12 | 41 ef 00 00 | > || | xsame false, xneg false > || | ysame true, yneg true > || | xbase 16, ybase 15 > || | Coord 55.24913, > -62.56851 2574796/-2915904 [-30624,+0] > || | Coord 54.61014, > -62.56851 2545017/-2915904 [+0,-29779] > || | Coord 54.61014, > -61.91139 2545017/-2885280 [+30624,+0] > || | 0 bits left, 0 > || | > 264a | 16 | 50 | Polygon 2 > || | Type 0x50 > 264b | 17 | 00 00 00| Label offset: 0x00 > () > 264e | 1a | d0 3b | Long delta 15312 > 2650 | 1c | b4 08 | Lat delta 2228 > || | Start point 54.97743, > -61.91139 2562134/-2885280 > 2652 | 1e | 0b | Bitstream length 11 > 2653 | 1f | 9b | Base 9b > 2654 | 20 | f2 8d 04 40 a7 fe d0 4b | Bitstream (len: 11, > 0xb) > 265c | 28 | e7 00 00| > || | xsame false, xneg false > || | ysame true, yneg false > || | xbase 16, ybase 11 > || | Coord 54.97743, > -62.51706 2562134/-2913506 [-28226,+0] > || | Coord 55.01732, > -62.54665 2563993/-2914885 [-1379,+1859] > || | Coord 55.01732, > -61.91139 2563993/-2885280 [+29605,+0] > || | 4 bits left, 0 > || | > > > Gerd > ___ > mkgmap-dev mailing list > mkgmap-dev@lists.mkgmap.org.uk > https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev ___ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
