This patch to the splitter that makes this warning MUCH more rare. With this patch, I can split the entire planet into 17219 areas with max-nodes=50000 resolution=14 without a single 'too many areas' warning among the the first 25 of 68 passes. Without this patch, a max-nodes=500000 split has dozens of such warnings.
This patch can also allow larger overlaps at a cost of more passes. The fix works by reordering the list of generated tiles. The trick is that the real limit in the splitter is that a node cannot be in more than 4 distinct areas PER PASS (A limit that remains unchanged with this patch.) If a node occurs in 10 tiles, but no single pass contains more than 4 of those tiles, everything works. If there are still 'too many areas' warnings, they can be handled by reducing --max-areas. Note that my patch depends on some other bug fixes; there are several infinite recursion bugs in the current code that trigger when having the splitter generate such small tiles. Some of these were fixed in the trunk, but not all are. In addition, my fixes/cleanups try harder at getting a good split. Scott
From d808c1595db564515c349c397eb36e20dd255d0f Mon Sep 17 00:00:00 2001 From: Scott Crosby <[email protected]> Date: Fri, 19 Mar 2010 10:56:34 -0500 Subject: [PATCH 7/8] Fix infinite recursion bugs when finding tiles with the density map. When running with a small node count limit, we hit various infinite recursions. This fixes those bugs when splitting all the way down to a leaf. --- .../parabola/splitter/SplittableDensityArea.java | 103 ++++++++++++++------ 1 files changed, 75 insertions(+), 28 deletions(-) diff --git a/src/uk/me/parabola/splitter/SplittableDensityArea.java b/src/uk/me/parabola/splitter/SplittableDensityArea.java index 75c3aba..7d67e8e 100644 --- a/src/uk/me/parabola/splitter/SplittableDensityArea.java +++ b/src/uk/me/parabola/splitter/SplittableDensityArea.java @@ -35,44 +35,71 @@ public class SplittableDensityArea implements SplittableArea { return densities.getBounds(); } + + public double getAspectRatio() { + Area bounds = densities.getBounds(); + int width1 = (int) (densities.getWidth() * Math.cos(Math.toRadians(Utils.toDegrees(bounds.getMinLat())))); + int width2 = (int) (densities.getWidth() * Math.cos(Math.toRadians(Utils.toDegrees(bounds.getMaxLat())))); + int width = Math.max(width1, width2); + int height = densities.getHeight(); + double ratio = ((double)width)/height; + return ratio; + } + + @Override public List<Area> split(int maxNodes) { if (densities == null || densities.getNodeCount() == 0) return Collections.emptyList(); Area bounds = densities.getBounds(); - if (densities.getNodeCount() <= maxNodes) { + if (densities.getNodeCount() < maxNodes) { densities = null; return Collections.singletonList(bounds); } - // Decide whether to split vertically or horizontally and go ahead with the split - int width1 = (int) (densities.getWidth() * Math.cos(Math.toRadians(Utils.toDegrees(bounds.getMinLat())))); - int width2 = (int) (densities.getWidth() * Math.cos(Math.toRadians(Utils.toDegrees(bounds.getMaxLat())))); - int width = Math.max(width1, width2); - - SplittableDensityArea[] splitResult; - if (densities.getHeight() > 2 && (densities.getHeight() > width || densities.getWidth() <= 2)) { - splitResult = splitVert(); - } else if (densities.getWidth() > 2) { - splitResult = splitHoriz(); - } else { + if (densities.getWidth() < 4 && densities.getHeight() < 4) { System.out.println("Area " + bounds + " contains " + Utils.format(densities.getNodeCount()) + " nodes but is already at the minimum size so can't be split further"); return Collections.singletonList(bounds); } - densities = null; + List<Area> results = new ArrayList<Area>(); + + // Decide whether to split vertically or horizontally and go ahead with the split + + + SplittableDensityArea[] splitResult = null; + // Try to split it based on dimension. + if (getAspectRatio() > 1.0 && densities.getHeight() >= 4) { + splitResult = splitVert(getSplitVert()); + } + // Either the natural split is horizontal, or no good vertical split. Try horizontal. + if (splitResult == null && densities.getWidth() >= 4) { + splitResult = splitHoriz(getSplitHoriz()); + } + // If the natural horizontal split failed. Try vertical. + if (getAspectRatio() < 1.0 && splitResult == null && densities.getHeight() >= 4) { + splitResult = splitVert(getSplitHoriz()); + } + // No dice. Use this as-is. + if (splitResult == null) { + System.out.println("Area " + bounds + " contains " + Utils.format(densities.getNodeCount()) + + " nodes but is already at the minimum size so can't be split further"); + return Collections.singletonList(bounds); + } + densities = null; results.addAll(splitResult[0].split(maxNodes)); results.addAll(splitResult[1].split(maxNodes)); return results; } /** - * Split into left and right areas + * Split into left and right areas. Requires width >= 4 (so that we can have a even midpoint. */ - protected SplittableDensityArea[] splitHoriz() { + protected Integer getSplitHoriz() { long sum = 0, weightedSum = 0; + Integer splitX; for (int x = 0; x < densities.getWidth(); x++) { for (int y = 0; y < densities.getHeight(); y++) { @@ -81,8 +108,15 @@ public class SplittableDensityArea implements SplittableArea { weightedSum += (count * x); } } - int splitX = limit(0, densities.getWidth(), (int) (weightedSum / sum)); - + splitX = limit(0, densities.getWidth(), (int) (weightedSum / sum)); + if (splitX == null) + return null; + return splitX; + } + + /** Get the actual split areas */ + protected SplittableDensityArea[] splitHoriz(int splitX) { + Area bounds = densities.getBounds(); int mid = bounds.getMinLong() + (splitX << densities.getShift()); Area leftArea = new Area(bounds.getMinLat(), bounds.getMinLong(), bounds.getMaxLat(), mid); @@ -93,8 +127,12 @@ public class SplittableDensityArea implements SplittableArea { return new SplittableDensityArea[] {new SplittableDensityArea(left), new SplittableDensityArea(right)}; } - protected SplittableDensityArea[] splitVert() { + /** + * Split into top and bottom areas. Requires height >= 4 (so that we can have a even midpoint. + */ + protected Integer getSplitVert() { long sum = 0, weightedSum = 0; + Integer splitY; for (int y = 0; y < densities.getHeight(); y++) { for (int x = 0; x < densities.getWidth(); x++) { @@ -103,8 +141,15 @@ public class SplittableDensityArea implements SplittableArea { weightedSum += (count * y); } } - int splitY = limit(0, densities.getHeight(), (int) (weightedSum / sum)); + splitY = limit(0, densities.getHeight(), (int) (weightedSum / sum)); + if (splitY == null) + return null; + return splitY; + } + /** Get the actual split areas */ + protected SplittableDensityArea[] splitVert(int splitY) { + Area bounds = densities.getBounds(); int mid = bounds.getMinLat() + (splitY << densities.getShift()); Area bottomArea = new Area(bounds.getMinLat(), bounds.getMinLong(), mid, bounds.getMaxLong()); @@ -115,18 +160,20 @@ public class SplittableDensityArea implements SplittableArea { return new SplittableDensityArea[]{new SplittableDensityArea(bottom), new SplittableDensityArea(top)}; } - private static int limit(int first, int second, int calcOffset) { - int mid = first + calcOffset; - int limitoff = Math.max((second - first) / 5, 2); - if (mid < first + limitoff) + /** return calcOffset if it is in the middle three quantiles, use the first or last quantile otherwise. */ + private Integer limit(int first, int second, long calcOffset) { + int mid = first + (int) calcOffset; + int limitoff = (second - first) / 5; + if (mid - first < limitoff) mid = first + limitoff; - else if (mid > second - limitoff) + else if (second - mid < limitoff) mid = second - limitoff; - if (mid % 2 != 0) { + + if (mid % 2 != 0) mid--; - if (mid < first + 2) - mid = first + 2; - } + if (mid == first || mid == second) + return null; + return mid; } } -- 1.7.1
From 3a91620115a581d50234c0085acc273afadf3528 Mon Sep 17 00:00:00 2001 From: Scott Crosby <[email protected]> Date: Tue, 18 May 2010 21:14:15 -0500 Subject: [PATCH 8/8] Reorder the order in which areas are output. Minimize the chances that we will generate >4 areas in geographic proximity to minimize 'node cannot be in >4 areas' error messages. --- .../parabola/splitter/SplittableDensityArea.java | 29 +++++++++++++++++--- 1 files changed, 25 insertions(+), 4 deletions(-) diff --git a/src/uk/me/parabola/splitter/SplittableDensityArea.java b/src/uk/me/parabola/splitter/SplittableDensityArea.java index 7d67e8e..1cb912e 100644 --- a/src/uk/me/parabola/splitter/SplittableDensityArea.java +++ b/src/uk/me/parabola/splitter/SplittableDensityArea.java @@ -15,6 +15,7 @@ package uk.me.parabola.splitter; import java.util.ArrayList; import java.util.Collections; +import java.util.Iterator; import java.util.List; /** @@ -64,8 +65,6 @@ public class SplittableDensityArea implements SplittableArea { return Collections.singletonList(bounds); } - List<Area> results = new ArrayList<Area>(); - // Decide whether to split vertically or horizontally and go ahead with the split @@ -89,8 +88,30 @@ public class SplittableDensityArea implements SplittableArea { return Collections.singletonList(bounds); } densities = null; - results.addAll(splitResult[0].split(maxNodes)); - results.addAll(splitResult[1].split(maxNodes)); + return mixResults( + splitResult[0].split(maxNodes), + splitResult[1].split(maxNodes)); + } + + /** Merge two result lists of regions */ + List<Area> mixResults(List<Area> a1, List<Area> a2) { + List<Area> results = new ArrayList<Area>(); + + Iterator<Area> i0 = a1.iterator(); + Iterator<Area> i1 = a2.iterator(); + + while (i0.hasNext() && i1.hasNext()) { + results.add(i0.next()); + results.add(i1.next()); + } + + while (i0.hasNext()) { + results.add(i0.next()); + } + while (i1.hasNext()) { + results.add(i1.next()); + } + Collections.reverse(results); return results; } -- 1.7.1
_______________________________________________ mkgmap-dev mailing list [email protected] http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
