[mkgmap-splitter] 01/03: Imported Upstream version 0.0.0+svn418
Bas Couwenberg
sebastic at xs4all.nl
Fri Jan 9 15:57:55 UTC 2015
This is an automated email from the git hooks/post-receive script.
sebastic-guest pushed a commit to branch master
in repository mkgmap-splitter.
commit 59c34c55fd6db8e9b00318ed9f3bc9524a9a4fdd
Author: Bas Couwenberg <sebastic at xs4all.nl>
Date: Fri Jan 9 16:52:47 2015 +0100
Imported Upstream version 0.0.0+svn418
---
resources/splitter-version.properties | 4 +-
.../osmosis/core/OsmosisRuntimeException.java | 8 +-
src/uk/me/parabola/splitter/Main.java | 5 ++
src/uk/me/parabola/splitter/Solution.java | 21 +++--
.../parabola/splitter/SplittableDensityArea.java | 94 ++++++++--------------
5 files changed, 61 insertions(+), 71 deletions(-)
diff --git a/resources/splitter-version.properties b/resources/splitter-version.properties
index 9107c3d..a01dfa8 100644
--- a/resources/splitter-version.properties
+++ b/resources/splitter-version.properties
@@ -1,2 +1,2 @@
-svn.version: 416
-build.timestamp: 2014-12-01T15:25:48+0000
+svn.version: 418
+build.timestamp: 2015-01-08T09:10:44+0000
diff --git a/src/org/openstreetmap/osmosis/core/OsmosisRuntimeException.java b/src/org/openstreetmap/osmosis/core/OsmosisRuntimeException.java
index e00244f..c121654 100644
--- a/src/org/openstreetmap/osmosis/core/OsmosisRuntimeException.java
+++ b/src/org/openstreetmap/osmosis/core/OsmosisRuntimeException.java
@@ -1,7 +1,7 @@
-// License: GPL. Copyright 2007-2008 by Brett Henderson and other contributors.
-package org.openstreetmap.osmosis.core;
-
-
+// This software is released into the Public Domain. See copying.txt for details.
+package org.openstreetmap.osmosis.core;
+
+
/**
* The root of the unchecked exception hierarchy for the application. All typed
* runtime exceptions subclass this exception.
diff --git a/src/uk/me/parabola/splitter/Main.java b/src/uk/me/parabola/splitter/Main.java
index 012f11a..fe4b9aa 100644
--- a/src/uk/me/parabola/splitter/Main.java
+++ b/src/uk/me/parabola/splitter/Main.java
@@ -366,6 +366,11 @@ public class Main {
System.err.println("The --mapid parameter must have less than 9 digits. Resetting to " + mapId + ".");
}
maxNodes = params.getMaxNodes();
+ if (maxNodes < 10000){
+ System.err.println("Error: Invalid number "+ params.getMaxNodes() +
+ ". The --max-nodes parameter must be an integer value of 10000 or higher.");
+ throw new IllegalArgumentException();
+ }
String numTilesParm = params.getNumTiles();
if (numTilesParm != null){
try{
diff --git a/src/uk/me/parabola/splitter/Solution.java b/src/uk/me/parabola/splitter/Solution.java
index 4b71701..7956d39 100644
--- a/src/uk/me/parabola/splitter/Solution.java
+++ b/src/uk/me/parabola/splitter/Solution.java
@@ -58,7 +58,6 @@ class Solution {
/**
* Combine this solution with the other.
* @param other
- * @param mergeAtDepth
*/
public void merge(Solution other){
if (other.tiles.isEmpty())
@@ -111,12 +110,24 @@ class Solution {
if (isNice() != other.isNice())
return isNice() ? -1 : 1;
-// if (depth != other.depth)
-// return (depth < other.depth) ? -1 : 1;
- if (worstMinNodes != other.worstMinNodes)
- return (worstMinNodes > other.worstMinNodes) ? -1 : 1;
+ if (worstMinNodes != other.worstMinNodes){
+ // ignore minNodes when both are bad
+ if (Math.max(worstMinNodes, other.worstMinNodes) > 1000)
+ return (worstMinNodes > other.worstMinNodes) ? -1 : 1;
+ }
+ // if aspect ratio is very different and tile sizes are almost equal,
+ // favour better aspect ratio
+ double tileRatio = (double) tiles.size() / other.tiles.size();
+ double arRatio = worstAspectRatio / other.worstAspectRatio;
+ if (tileRatio < 1 && tileRatio > 0.99 && arRatio > 1.5)
+ return 1;
+ if (tileRatio < 1.01 && tileRatio > 1 && arRatio < 0.66666)
+ return -1;
+
if (tiles.size() != other.tiles.size())
return tiles.size() < other.tiles.size() ? -1 : 1;
+ if (worstAspectRatio != other.worstAspectRatio)
+ return worstAspectRatio < other.worstAspectRatio ? -1 : 1;
return 0;
}
diff --git a/src/uk/me/parabola/splitter/SplittableDensityArea.java b/src/uk/me/parabola/splitter/SplittableDensityArea.java
index 3ab6921..51a5564 100644
--- a/src/uk/me/parabola/splitter/SplittableDensityArea.java
+++ b/src/uk/me/parabola/splitter/SplittableDensityArea.java
@@ -50,8 +50,6 @@ public class SplittableDensityArea {
private final DensityMap allDensities;
private EnhancedDensityMap extraDensityInfo;
- private boolean tryOptimize = false;
-
private boolean beQuiet = false;
private long maxNodes;
private final int shift;
@@ -70,6 +68,7 @@ public class SplittableDensityArea {
private boolean trimTiles;
private boolean allowEmptyPart = false;
private int currMapId;
+ private boolean hasEmptyPart;
public SplittableDensityArea(DensityMap densities, int startSearchLimit) {
this.shift = densities.getShift();
@@ -118,9 +117,11 @@ public class SplittableDensityArea {
List<Tile> startTiles = checkForEmptyClusters(0, startTile, true);
Solution fullSolution = new Solution(maxNodes);
- int countNoSol = 0;
+ int countNoSol;
while (true){
+ countNoSol = 0;
for (Tile tile: startTiles){
+ hasEmptyPart = false;
if (!beQuiet)
System.out.println("Solving partition " + tile.toString());
Solution solution = solveRectangularArea(tile);
@@ -134,15 +135,16 @@ public class SplittableDensityArea {
}
if (countNoSol == 0)
break;
- if (allowEmptyPart)
+ if (allowEmptyPart || hasEmptyPart == false)
break;
allowEmptyPart = true;
fullSolution = new Solution(maxNodes);
}
+ if(countNoSol > 0)
+ throw new SplitFailedException("Failed to find a correct split");
System.out.println("Final solution: " + fullSolution.toString());
if (fullSolution.isNice())
System.out.println("This seems to be nice.");
-
return getAreas(fullSolution, null);
}
@@ -572,8 +574,10 @@ public class SplittableDensityArea {
private Solution findSolution(int depth, final Tile tile, Tile parent, TileMetaInfo smiParent){
boolean addAndReturn = false;
if (tile.count == 0){
- if (!allowEmptyPart)
+ if (!allowEmptyPart){
+ hasEmptyPart = true;
return null;
+ }
if (tile.width * tile.height <= 4)
return null;
return new Solution(maxNodes); // allow empty part of the world
@@ -612,7 +616,6 @@ public class SplittableDensityArea {
if (cached != null){
return cached;
}
-
// we have to split the tile
Integer alreadyDone = null;
if (countBad == 0 && incomplete.size() > 0){
@@ -653,6 +656,10 @@ public class SplittableDensityArea {
continue;
}
int splitPos = todoList.getInt(usedTestPos++);
+// if (tested.get(splitPos)){
+// continue;
+// }
+// tested.set(splitPos);
// create the two parts of the tile
boolean ok = false;
if (axis == AXIS_HOR){
@@ -699,15 +706,6 @@ public class SplittableDensityArea {
if (countOK == 2){
Solution sol = sols[0];
sol.merge(sols[1]);
- if (tryOptimize && searchAll == false){
- if(sol.getTiles().size() <= 32 && sol.getWorstMinNodes() < VERY_NICE_FILL_RATIO * maxNodes){
- Solution optSol = solveSmallTile(depth, tile, smi, (long) (VERY_NICE_FILL_RATIO * maxNodes));
- if (sol.compareTo(optSol) > 0){
- System.out.println("found better solution for part " + tile + " : " + optSol);
- sol = optSol;
- }
- }
- }
bestSol = sol;
break; // we found a valid split and searched the direct neighbours
}
@@ -741,7 +739,6 @@ public class SplittableDensityArea {
// start values for optimization process: we make little steps towards a good solution
// spread = 7;
searchLimit = startSearchLimit;
- tryOptimize = false;
minNodes = Math.max(Math.min((long)(0.05 * maxNodes), extraDensityInfo.getNodeCount()), 1);
if (extraDensityInfo.getNodeCount() / maxNodes < 4){
@@ -792,7 +789,6 @@ public class SplittableDensityArea {
factor = Math.min(1.30,(double)bestSolution.getWorstMinNodes() / prevBest.getWorstMinNodes());
minNodes = Math.max(maxNodes /3, (long) (bestSolution.getWorstMinNodes() * factor));
}
-
if (bestSolution.size() == 1){
if (!beQuiet)
System.out.println("This can't be improved.");
@@ -809,23 +805,38 @@ public class SplittableDensityArea {
}
}
}
- if (tryOptimize)
- break;
maxAspectRatio = Math.max(bestSolution.getWorstAspectRatio()/2, NICE_MAX_ASPECT_RATIO);
maxAspectRatio = Math.min(32,maxAspectRatio);
-
if (bestSolution.isEmpty() == false && bestSolution.getWorstMinNodes() > VERY_NICE_FILL_RATIO * maxNodes)
break;
if (minNodes > VERY_NICE_FILL_RATIO * maxNodes)
minNodes = (long) (VERY_NICE_FILL_RATIO * maxNodes);
if (saveMaxAspectRatio == maxAspectRatio && saveMinNodes == minNodes){
if (bestSolution.isEmpty() || bestSolution.getWorstMinNodes() < 0.5 * maxNodes){
- if (searchLimit < 5_000_000){
+ if (countBad > searchLimit && searchLimit < 5_000_000){
searchLimit *= 2;
resetCaches();
System.out.println("No good solution found, duplicated search-limit to " + searchLimit);
continue;
}
+ if (bestSolution.isEmpty() && minNodes > 1){
+ minNodes = 1;
+ resetCaches();
+ searchLimit = startSearchLimit;
+ // sanity check
+ System.out.println("No good solution found, trying to find one accepting anything");
+ int highestCount = extraDensityInfo.getMaxNodesInDensityMapGridElement();
+ // inform user about possible better options?
+ double ratio = (double) highestCount / maxNodes;
+ if (ratio > 4)
+ System.err.printf("max-nodes value %d is far below highest node count %d in single grid element, consider using a higher resolution.\n", maxNodes , highestCount);
+ else if (ratio > 1)
+ System.err.printf("max-nodes value %d is below highest node count %d in single grid element, consider using a higher resolution.\n", maxNodes , highestCount);
+ else if (ratio < 0.25)
+ System.err.printf("max-nodes value %d is far above highest node count %d in single grid element, consider using a lower resolution.\n", maxNodes , highestCount);
+
+ continue;
+ }
if (searchAll){
searchAll = false;
if (bestSolution.isEmpty() == false)
@@ -836,12 +847,6 @@ public class SplittableDensityArea {
continue;
}
}
- if (tryOptimize == false && searchAll == false && bestSolution.isEmpty() == false){
- System.out.println("Trying to optimize parts of the best solution...");
- tryOptimize = true;
- resetCaches();
- continue;
- }
break;
}
@@ -853,6 +858,7 @@ public class SplittableDensityArea {
private void resetCaches(){
knownBad = new HashSet<>();
+
// incomplete = new LinkedHashMap<>();
// System.out.println("resetting caches");
}
@@ -1003,38 +1009,6 @@ public class SplittableDensityArea {
}
return tests;
}
-
- /**
- * This can be called to optimise a part of the start tile or to verify if a better solution is possible
- * @param depth
- * @param tile
- * @param smi
- * @param testMinNodes
- * @return
- */
- Solution solveSmallTile(int depth, Tile tile, TileMetaInfo smi, long testMinNodes){
- if (searchAll)
- return null;
- double saveMaxRatio = maxAspectRatio;
- long saveBad = countBad;
- long saveMinNodes = minNodes;
- minNodes = testMinNodes;
- countBad = 0;
- searchAll = true;
- beQuiet = true;
- knownBad.remove(tile);
-// long t1 = System.currentTimeMillis();
- Solution sol = findSolution(depth+1, tile, tile, smi);
-// long dt = System.currentTimeMillis() - t1;
- beQuiet = false;
-// if (dt > 20)
-// System.out.println("optimization took long and returned " + sol + " for " + tile);
- searchAll = false;
- countBad = saveBad;
- minNodes = saveMinNodes;
- maxAspectRatio = saveMaxRatio;
- return sol;
- }
}
--
Alioth's /usr/local/bin/git-commit-notice on /srv/git.debian.org/git/pkg-grass/mkgmap-splitter.git
More information about the Pkg-grass-devel
mailing list