[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