[Git][debian-gis-team/mkgmap-splitter][upstream] New upstream version 0.0.0+svn615

Bas Couwenberg (@sebastic) gitlab at salsa.debian.org
Thu Jul 1 06:29:23 BST 2021



Bas Couwenberg pushed to branch upstream at Debian GIS Project / mkgmap-splitter


Commits:
fbfad6b2 by Bas Couwenberg at 2021-07-01T07:20:26+02:00
New upstream version 0.0.0+svn615
- - - - -


4 changed files:

- resources/splitter-version.properties
- src/uk/me/parabola/splitter/solver/AreasCalculator.java
- src/uk/me/parabola/splitter/solver/DensityMap.java
- src/uk/me/parabola/splitter/solver/SplittableDensityArea.java


Changes:

=====================================
resources/splitter-version.properties
=====================================
@@ -1,2 +1,2 @@
-svn.version: 602
-build.timestamp: 2021-05-07T15:00:54+0100
+svn.version: 615
+build.timestamp: 2021-06-30T10:03:46+0100


=====================================
src/uk/me/parabola/splitter/solver/AreasCalculator.java
=====================================
@@ -169,8 +169,8 @@ public class AreasCalculator {
 			if (exactArea != null)
 				System.out.println("Exact map coverage after applying bounding box of polygon-file is " + exactArea);
 			else {
-				System.out.println("Exact map coverage after applying bounding box of polygon-file is an empty area");
-				return;
+				throw new SplitFailedException(
+						"Exact map coverage after applying bounding box of polygon-file is an empty area");
 			}
 		}
 		


=====================================
src/uk/me/parabola/splitter/solver/DensityMap.java
=====================================
@@ -13,6 +13,7 @@
 
 package uk.me.parabola.splitter.solver;
 
+import java.awt.Point;
 import java.awt.Rectangle;
 import java.io.File;
 import java.io.FileInputStream;
@@ -21,6 +22,7 @@ import java.io.IOException;
 import java.io.InputStream;
 import java.io.InputStreamReader;
 import java.io.LineNumberReader;
+import java.util.List;
 import java.util.regex.Pattern;
 
 import uk.me.parabola.splitter.Area;
@@ -63,17 +65,17 @@ public class DensityMap {
 	 * @param polygonArea the polygon area 
 	 * @return an area with rectilinear shape that approximates the polygon area 
 	 */
-	public java.awt.geom.Area rasterPolygon(java.awt.geom.Area polygonArea){
+	public java.awt.geom.Area rasterPolygon(java.awt.geom.Area polygonArea) {
 		if (polygonArea == null)
 			return null;
 		java.awt.geom.Area simpleArea = new java.awt.geom.Area();
 		if (polygonArea.intersects(Utils.area2Rectangle(bounds, 0)) == false)
 			return simpleArea;
 		int gridElemWidth = bounds.getWidth() / width;
-		int gridElemHeight= bounds.getHeight()/ height;
+		int gridElemHeight = bounds.getHeight() / height;
 		Rectangle polygonBbox = polygonArea.getBounds();
-		int minLat = Math.max((int)polygonBbox.getMinY(), bounds.getMinLat());
-		int maxLat = Math.min((int)polygonBbox.getMaxY(), bounds.getMaxLat());
+		int minLat = Math.max((int) polygonBbox.getMinY(), bounds.getMinLat());
+		int maxLat = Math.min((int) polygonBbox.getMaxY(), bounds.getMaxLat());
 		int minY = latToY(minLat);
 		int maxY = latToY(maxLat);
 		assert minY >= 0 && minY <= height;
@@ -82,7 +84,7 @@ public class DensityMap {
 			int lon = xToLon(x);
 			if (lon + gridElemWidth < polygonBbox.getMinX() 
 					|| lon > polygonBbox.getMaxX()
-					|| polygonArea.intersects(lon, polygonBbox.getMinY(), gridElemWidth, polygonBbox.getHeight()) == false){
+					|| !polygonArea.intersects(lon, polygonBbox.getMinY(), gridElemWidth, polygonBbox.getHeight())) {
 				continue;
 			}
 			int firstY = -1;
@@ -103,6 +105,14 @@ public class DensityMap {
 				simpleArea.add(new java.awt.geom.Area(new Rectangle(x,firstY,1,height-firstY)));
 			}
 		}
+		if (!simpleArea.isSingular()) {
+			List<List<Point>> shapes = Utils.areaToShapes(simpleArea);
+			if (shapes.removeIf(s -> !Utils.clockwise(s))) {
+				System.out.println("Warning: Rastered polaygon area contains holes, polygon is probably concave, trying to fix this");
+				simpleArea.reset();
+				shapes.forEach(s -> simpleArea.add(Utils.shapeToArea(s)));
+			}
+		}
 		return simpleArea;
 	}
 	
@@ -147,11 +157,11 @@ public class DensityMap {
 		return nodeMap[x] != null ? nodeMap[x][y] : 0;
 	}
 
-	public int[][] getyxMap(){
+	public int[][] getyxMap() {
 		int[][] yxMap = new int[height][];
 		for (int y = 0; y < height; y++) {
 			for (int x = 0; x < width; x++) {
-				int count = (nodeMap[x] == null) ? 0:nodeMap[x][y];
+				int count = (nodeMap[x] == null) ? 0 : nodeMap[x][y];
 				if (count > 0) {
 					if (yxMap[y] == null)
 						yxMap[y] = new int[width];


=====================================
src/uk/me/parabola/splitter/solver/SplittableDensityArea.java
=====================================
@@ -13,12 +13,6 @@
 
 package uk.me.parabola.splitter.solver;
 
-import it.unimi.dsi.fastutil.ints.IntArrayList;
-import uk.me.parabola.splitter.Area;
-import uk.me.parabola.splitter.RoundingUtils;
-import uk.me.parabola.splitter.SplitFailedException;
-import uk.me.parabola.splitter.Utils;
-
 import java.awt.Point;
 import java.awt.Rectangle;
 import java.util.ArrayList;
@@ -28,24 +22,30 @@ import java.util.HashSet;
 import java.util.LinkedHashMap;
 import java.util.List;
 
+import it.unimi.dsi.fastutil.ints.IntArrayList;
+import uk.me.parabola.splitter.Area;
+import uk.me.parabola.splitter.RoundingUtils;
+import uk.me.parabola.splitter.SplitFailedException;
+import uk.me.parabola.splitter.Utils;
+
 /**
- * Splits a density map into multiple areas, none of which
- * exceed the desired threshold.
+ * Splits a density map into multiple areas, none of which exceed the desired
+ * threshold.
  *
-* @author Chris Miller, Gerd Petermann
+ * @author Chris Miller, Gerd Petermann
  */
 public class SplittableDensityArea {
 	private static final int MAX_LAT_DEGREES = 85;
 	private static final int MAX_LON_DEGREES = 90;
 	public static final int MAX_SINGLE_POLYGON_VERTICES = 40;
-	private static final int MAX_LOOPS = 100;	// number of loops to find better solution for one rectangular area
-	private static final int AXIS_HOR = 0; 
-	private static final int AXIS_VERT = 1; 
+	private static final int MAX_LOOPS = 100; // number of loops to find better solution for one rectangular area
+	private static final int AXIS_HOR = 0;
+	private static final int AXIS_VERT = 1;
 	public static final double NICE_MAX_ASPECT_RATIO = 4;
 	private static final double VERY_NICE_FILL_RATIO = 0.93;
 	private static final long LARGE_MAX_NODES = 10_000_000;
 	private static final int GOOD_SOL_INIT_SIZE = 1_000_000;
-	
+
 	private double maxAspectRatio;
 	private long minNodes;
 	private final int startSearchLimit;
@@ -54,30 +54,30 @@ public class SplittableDensityArea {
 
 	private final DensityMap allDensities;
 	private EnhancedDensityMap extraDensityInfo;
-	
+
 	private boolean beQuiet = false;
 	private long maxNodes;
 	private final int shift;
-	
+
 	private HashSet<Tile> knownBad;
 	private LinkedHashMap<Tile, Integer> incomplete;
 	private long countBad;
-	
+
 	/** if true enables an alternative algorithm */
 	private boolean searchAll = false;
-	
+
 	final int maxTileHeight;
 	final int maxTileWidth;
-	
-	private HashMap<Tile,Solution> goodSolutions;
-	private double goodRatio; 
+
+	private HashMap<Tile, Solution> goodSolutions;
+	private double goodRatio;
 	private boolean trimShape;
 	private boolean trimTiles;
 	private boolean allowEmptyPart = false;
 	private int currMapId;
 	private boolean hasEmptyPart;
 	private boolean ignoreSize;
-	
+
 	public SplittableDensityArea(DensityMap densities, int startSearchLimit) {
 		this.shift = densities.getShift();
 		this.searchLimit = this.startSearchLimit = startSearchLimit;
@@ -85,9 +85,11 @@ public class SplittableDensityArea {
 		maxTileWidth = Utils.toMapUnit(MAX_LON_DEGREES) / (1 << shift);
 		allDensities = densities;
 	}
+
 	public DensityMap getAllDensities() {
 		return allDensities;
 	}
+
 	public void setMapId(int mapId) {
 		currMapId = mapId;
 	}
@@ -96,51 +98,52 @@ public class SplittableDensityArea {
 		this.maxNodes = maxNodes;
 	}
 
-
 	public void setTrim(boolean trim) {
 		this.trimShape = trim;
 	}
 
-	public boolean hasData(){
+	public boolean hasData() {
 		return allDensities != null && allDensities.getNodeCount() > 0;
 	}
 
 	/**
 	 * @return the area that this splittable area represents
-	 */ 	
+	 */
 	public Area getBounds() {
 		return allDensities.getBounds();
 	}
 
 	/**
-	 * @param maxNodes the maximum number of nodes per area
+	 * Create the list of areas.
+	 * 
 	 * @return a list of areas, each containing no more than {@code maxNodes} nodes.
-	 * Each area returned must be aligned to the appropriate overview map resolution.
-	 */ 	
+	 *         Each area returned must be aligned to the appropriate overview map
+	 *         resolution.
+	 */
 	private List<Area> split() {
 		if (allDensities == null || allDensities.getNodeCount() == 0)
 			return Collections.emptyList();
 		prepare(null);
 		Tile startTile = new Tile(extraDensityInfo);
 		List<Tile> startTiles = new ArrayList<>();
-		if (trimShape || allDensities.getBounds().getWidth() >= 0x1000000){
-			// if trim is wanted or tile spans over planet 
-			// we try first to find large empty areas (sea) 
+		if (trimShape || allDensities.getBounds().getWidth() >= 0x1000000) {
+			// if trim is wanted or tile spans over planet
+			// we try first to find large empty areas (sea)
 			startTiles.addAll(checkForEmptyClusters(0, startTile, true));
-		}
-		else 
+		} else {
 			startTiles.add(startTile);
-		
+		}
+
 		Solution fullSolution = new Solution(maxNodes);
 		int countNoSol;
-		while (true){
+		while (true) {
 			countNoSol = 0;
-			for (Tile tile: startTiles){
+			for (Tile tile : startTiles) {
 				hasEmptyPart = false;
 				if (!beQuiet)
 					System.out.println("Solving partition " + tile.toString());
 				Solution solution = solveRectangularArea(tile);
-				if (solution != null && solution.isEmpty() == false)
+				if (solution != null && !solution.isEmpty())
 					fullSolution.merge(solution);
 				else {
 					countNoSol++;
@@ -150,42 +153,47 @@ public class SplittableDensityArea {
 			}
 			if (countNoSol == 0)
 				break;
-			if (allowEmptyPart || hasEmptyPart == false)
+			if (allowEmptyPart || !hasEmptyPart)
 				break;
 			allowEmptyPart = true;
 			fullSolution = new Solution(maxNodes);
 		}
-		if(countNoSol > 0)
+		if (countNoSol > 0)
 			throw new SplitFailedException("Failed to find a correct split");
-		System.out.println("Final solution: " +  fullSolution.toString());
+		System.out.println("Final solution: " + fullSolution.toString());
 		if (fullSolution.isNice())
 			System.out.println("This seems to be nice.");
 		return getAreas(fullSolution, null);
 	}
 
 	/**
-	 * Split with a given polygon and max nodes threshold. If the polygon
-	 * is not singular, it is divided into singular areas.
-	 * @param maxNodes
+	 * Split with a given polygon and max nodes threshold. If the polygon is not
+	 * singular, it is divided into singular areas.
+	 * 
 	 * @param polygonArea
-	 * @return
+	 * @return list of areas
 	 */
 	private List<Area> split(java.awt.geom.Area polygonArea) {
 		if (polygonArea == null)
 			return split();
-		if (polygonArea.isSingular()){
+		if (polygonArea.isSingular()) {
 			java.awt.geom.Area rasteredArea = allDensities.rasterPolygon(polygonArea);
-			if (rasteredArea.isEmpty()){
+			if (rasteredArea.isEmpty()) {
 				System.err.println("Bounding polygon doesn't intersect with the bounding box of the input file(s)");
 				return Collections.emptyList();
 			}
-			
-			prepare(polygonArea);
-			Tile tile = new Tile(extraDensityInfo, rasteredArea.getBounds());
-			Solution solution = findSolutionWithSinglePolygon(0, tile, rasteredArea);
-			return getAreas(solution, polygonArea);
+			if (rasteredArea.isSingular()) {
+				prepare(polygonArea);
+				Tile tile = new Tile(extraDensityInfo, rasteredArea.getBounds());
+				Solution solution = findSolutionWithSinglePolygon(0, tile, rasteredArea);
+				if (solution == null && rasteredArea.isRectangular())
+					return split();
+				if (solution != null) { 
+					return getAreas(solution, polygonArea);
+				}
+			}
 		}
-		if (polygonArea.intersects(Utils.area2Rectangle(allDensities.getBounds(),0)))
+		if (polygonArea.intersects(Utils.area2Rectangle(allDensities.getBounds(), 0)))
 			return splitPolygon(polygonArea);
 		System.err.println("Bounding polygon doesn't intersect with the bounding box of the input file(s)");
 		return Collections.emptyList();
@@ -193,10 +201,10 @@ public class SplittableDensityArea {
 
 	/**
 	 * Split a list of named polygons. Overlapping areas of the polygons are
-	 * extracted and each one is split for itself. A polygon may not be singular. 
-	 * @param maxNodes 
+	 * extracted and each one is split for itself. A polygon may not be singular.
+	 * 
 	 * @param namedPolygons
-	 * @return
+	 * @return list of areas
 	 */
 	public List<Area> split(List<PolygonDesc> namedPolygons) {
 		if (namedPolygons.isEmpty())
@@ -207,19 +215,19 @@ public class SplittableDensityArea {
 			final IntArrayList sharedBy = new IntArrayList();
 		}
 		List<ShareInfo> sharedParts = new ArrayList<>();
-		for (int i = 0; i < namedPolygons.size(); i++){
+		for (int i = 0; i < namedPolygons.size(); i++) {
 			boolean wasDistinct = true;
 			PolygonDesc namedPart = namedPolygons.get(i);
-			java.awt.geom.Area distinctPart = new java.awt.geom.Area (namedPart.getArea());
-			for(int j = 0; j < namedPolygons.size(); j++){
+			java.awt.geom.Area distinctPart = new java.awt.geom.Area(namedPart.getArea());
+			for (int j = 0; j < namedPolygons.size(); j++) {
 				if (j == i)
 					continue;
 				java.awt.geom.Area test = new java.awt.geom.Area(namedPart.getArea());
 				test.intersect(namedPolygons.get(j).getArea());
-				if (test.isEmpty() == false){
+				if (!test.isEmpty()) {
 					wasDistinct = false;
 					distinctPart.subtract(namedPolygons.get(j).getArea());
-					if (j > i){
+					if (j > i) {
 						ShareInfo si = new ShareInfo();
 						si.area = test;
 						si.sharedBy.add(i);
@@ -228,27 +236,27 @@ public class SplittableDensityArea {
 					}
 				}
 			}
-			if (distinctPart.isEmpty() == false && distinctPart.intersects(Utils.area2Rectangle(allDensities.getBounds(),0))){
-//				KmlWriter.writeKml("e:/ld_sp/distinct_"+namedPart.name, "distinct", distinctPart);
-				if (wasDistinct == false)
+			if (!distinctPart.isEmpty() && distinctPart.intersects(Utils.area2Rectangle(allDensities.getBounds(), 0))) {
+//				KmlWriter.writeKml("e:/ld_sp/distinct_"+namedPart.getName(), "distinct", distinctPart);
+				if (!wasDistinct)
 					System.out.println("splitting distinct part of " + namedPart.getName());
-				else 
+				else
 					System.out.println("splitting " + namedPart.getName());
 				result.addAll(split(distinctPart));
 			}
 		}
-		
-		for (int i = 0; i < sharedParts.size(); i++){
+
+		for (int i = 0; i < sharedParts.size(); i++) {
 			ShareInfo si = sharedParts.get(i);
 			int last = namedPolygons.size(); // list is extended in the loop
-			for (int j = 0; j < last; j++){
+			for (int j = 0; j < last; j++) {
 				if (si.sharedBy.contains(j))
 					continue;
 				java.awt.geom.Area test = new java.awt.geom.Area(si.area);
 				test.intersect(namedPolygons.get(j).getArea());
-				if (test.isEmpty() == false){
+				if (!test.isEmpty()) {
 					si.area.subtract(test);
-					if (j > si.sharedBy.getInt(si.sharedBy.size()-1)){
+					if (j > si.sharedBy.getInt(si.sharedBy.size() - 1)) {
 						ShareInfo si2 = new ShareInfo();
 						si2.area = test;
 						si2.sharedBy.addAll(si.sharedBy);
@@ -259,11 +267,11 @@ public class SplittableDensityArea {
 				if (si.area.isEmpty())
 					break;
 			}
-			if (si.area.isEmpty() == false && si.area.intersects(Utils.area2Rectangle(allDensities.getBounds(),0))){
+			if (!si.area.isEmpty() && si.area.intersects(Utils.area2Rectangle(allDensities.getBounds(), 0))) {
 				String desc = "";
 				for (int pos : si.sharedBy)
 					desc += namedPolygons.get(pos).getName() + " and ";
-				desc = desc.substring(0,desc.lastIndexOf(" and"));
+				desc = desc.substring(0, desc.lastIndexOf(" and"));
 				System.out.println("splitting area shared by exactly " + si.sharedBy.size() + " polygons: " + desc);
 //				KmlWriter.writeKml("e:/ld_sp/shared_"+desc.replace(" " , "_"), desc, si.area);
 				result.addAll(split(si.area));
@@ -273,21 +281,21 @@ public class SplittableDensityArea {
 	}
 
 	/**
-	 * Split a list of named polygons into a given number of tiles.
-	 * This is probably only useful with an empty list of polygons
-	 * or a list containing one polygon.
+	 * Split a list of named polygons into a given number of tiles. This is probably
+	 * only useful with an empty list of polygons or a list containing one polygon.
+	 * 
 	 * @param wantedTiles
-	 * @return
+	 * @return list of areas
 	 */
 	public List<Area> split(int wantedTiles) {
 		long currMaxNodes = this.allDensities.getNodeCount() / wantedTiles;
 		class Pair {
 			long maxNodes;
 			int numTiles;
-			
-			Pair(long maxNodes, int numTiles){
+
+			Pair(long maxNodes, int numTiles) {
 				this.maxNodes = maxNodes;
-				this.numTiles = numTiles;  
+				this.numTiles = numTiles;
 			}
 		}
 		Pair bestBelow = null;
@@ -296,55 +304,53 @@ public class SplittableDensityArea {
 		ignoreSize = true;
 		while (true) {
 			setMaxNodes(currMaxNodes);
-			System.out.println("Trying a max-nodes value of " + currMaxNodes + " to split " + allDensities.getNodeCount() + " nodes into " + wantedTiles + " areas");
+			System.out.println("Trying a max-nodes value of " + currMaxNodes + " to split "
+					+ allDensities.getNodeCount() + " nodes into " + wantedTiles + " areas");
 			List<Area> res = split();
-			if (res.isEmpty() || res.size() == wantedTiles){
+			if (res.isEmpty() || res.size() == wantedTiles) {
 				beQuiet = false;
 				res = split();
 				return res;
 			}
 			goodSolutions = new HashMap<>(GOOD_SOL_INIT_SIZE);
 			Pair pair = new Pair(currMaxNodes, res.size());
-			if (res.size() > wantedTiles){
-				if (bestAbove == null)
-					bestAbove = pair;
-				else if (bestAbove.numTiles > pair.numTiles)
-					bestAbove = pair;
-				else  if (bestAbove.numTiles == pair.numTiles && pair.maxNodes < bestAbove.maxNodes)
+			if (res.size() > wantedTiles) {
+				if (bestAbove == null || bestAbove.numTiles > pair.numTiles
+						|| (bestAbove.numTiles == pair.numTiles && pair.maxNodes < bestAbove.maxNodes))
 					bestAbove = pair;
 			} else {
-				if (bestBelow == null)
-					bestBelow = pair;
-				else if (bestBelow.numTiles < pair.numTiles)
-					bestBelow = pair;
-				else  if (bestBelow.numTiles == pair.numTiles && pair.maxNodes > bestBelow.maxNodes)
+				if (bestBelow == null || bestBelow.numTiles < pair.numTiles
+						|| (bestBelow.numTiles == pair.numTiles && pair.maxNodes > bestBelow.maxNodes))
 					bestBelow = pair;
 			}
 			long testMaxNodes;
 			if (bestBelow == null || bestAbove == null)
-				testMaxNodes = Math.min(Math.round((double) currMaxNodes * res.size() / wantedTiles), this.allDensities.getNodeCount()-1);
-			else 
+				testMaxNodes = Math.min(Math.round((double) currMaxNodes * res.size() / wantedTiles),
+						this.allDensities.getNodeCount() - 1);
+			else
 				testMaxNodes = (bestBelow.maxNodes + bestAbove.maxNodes) / 2;
-			if (testMaxNodes == currMaxNodes){
+			if (testMaxNodes == currMaxNodes) {
 				System.err.println("Cannot find a good split with exactly " + wantedTiles + " areas");
 				return res;
 			}
 			currMaxNodes = testMaxNodes;
-		} 
+		}
 	}
 
-	/** 
-	 * Filter the density data, calculate once complex trigonometric results 
+	/**
+	 * Filter the density data, calculate once complex trigonometric results
+	 * 
 	 * @param polygonArea
 	 */
-	private void prepare(java.awt.geom.Area polygonArea){
+	private void prepare(java.awt.geom.Area polygonArea) {
 		extraDensityInfo = new EnhancedDensityMap(allDensities, polygonArea);
-		if (!beQuiet){
+		if (!beQuiet) {
 			System.out.println("Highest node count in a single grid element is "
 					+ Utils.format(extraDensityInfo.getMaxNodesInDensityMapGridElement()));
-			if (polygonArea != null)
-			System.out.println("Highest node count in a single grid element within the bounding polygon is "
-					+ Utils.format(extraDensityInfo.getMaxNodesInDensityMapGridElementInPoly()));
+			if (polygonArea != null) {
+				System.out.println("Highest node count in a single grid element within the bounding polygon is "
+						+ Utils.format(extraDensityInfo.getMaxNodesInDensityMapGridElementInPoly()));
+			}
 		}
 		if (polygonArea != null)
 			trimTiles = true;
@@ -352,27 +358,27 @@ public class SplittableDensityArea {
 	}
 
 	/**
-	 * Check if the solution should be stored in the map of partial good solutions 
+	 * Check if the solution should be stored in the map of partial good solutions
+	 * 
 	 * @param tile the tile for which the solution was found
-	 * @param sol the solution for the tile
+	 * @param sol  the solution for the tile
 	 */
-	private void checkIfGood(Tile tile, Solution sol){
-		if (sol.isNice() == false || sol.getTiles().size() < 2)
-			return;
-		if (sol.getWorstMinNodes() > (goodRatio * maxNodes)){
+	private void checkIfGood(Tile tile, Solution sol) {
+		if (sol.isNice() && sol.getTiles().size() >= 2 && sol.getWorstMinNodes() > (goodRatio * maxNodes)) {
 			Solution good = sol.copy();
-			// add new or replace worse solution 
-			goodSolutions.compute(tile, (k,v) -> v == null || v.getWorstMinNodes() < good.getWorstMinNodes() ? good : v);
+			// add new or replace worse solution
+			goodSolutions.compute(tile,
+					(k, v) -> v == null || v.getWorstMinNodes() < good.getWorstMinNodes() ? good : v);
 		}
-		
 	}
 
 	/**
-	 * Remove entries from the map of partial good solutions which
-	 * cannot help to improve the best solution. 
+	 * Remove entries from the map of partial good solutions which cannot help to
+	 * improve the best solution.
+	 * 
 	 * @param best the best known solution
 	 */
-	private void filterGoodSolutions(Solution best){
+	private void filterGoodSolutions(Solution best) {
 		if (best == null || best.isEmpty())
 			return;
 		goodSolutions.entrySet().removeIf(entry -> entry.getValue().getWorstMinNodes() <= best.getWorstMinNodes());
@@ -380,29 +386,30 @@ public class SplittableDensityArea {
 	}
 
 	/**
-	 * Search a solution for the given tile in the map of partial good solutions 
+	 * Search a solution for the given tile in the map of partial good solutions
+	 * 
 	 * @param tile the tile to split
 	 * @return a copy of the best known solution or null
 	 */
-	private Solution searchGoodSolutions(Tile tile){
+	private Solution searchGoodSolutions(Tile tile) {
 		Solution sol = goodSolutions.get(tile);
-		if (sol != null){
+		if (sol != null) {
 			if (sol.getWorstMinNodes() < minNodes)
 				return null;
 			sol = sol.copy();
 		}
 		return sol;
 	}
-	
-	
+
 	/**
 	 * Try to find empty areas. This will fail if the empty area is enclosed by a
 	 * non-empty area.
-	 * @param depth recursion depth
-	 * @param tile the tile that might contain an empty area
+	 * 
+	 * @param depth      recursion depth
+	 * @param tile       the tile that might contain an empty area
 	 * @param splitHoriz true: search horizontal, else vertical
-	 * @return a list containing one or more tiles, cut from the original tile, or 
-	 * just the original tile
+	 * @return a list containing one or more tiles, cut from the original tile, or
+	 *         just the original tile
 	 */
 	private ArrayList<Tile> checkForEmptyClusters(int depth, final Tile tile, boolean splitHoriz) {
 		java.awt.geom.Area area = new java.awt.geom.Area(tile);
@@ -410,17 +417,20 @@ public class SplittableDensityArea {
 		int countEmpty = 0;
 		long countLastPart = 0;
 		long countRemaining = tile.getCount();
-		long maxEmpty = Utils.toMapUnit(30) / (1 << shift);
-		if (splitHoriz){
-			for (int i = 0; i < tile.width; i++){
+		int maxEmpty = Utils.toMapUnit(30) / (1 << shift);
+		int minEmpty = Utils.toMapUnit(10) / (1 << shift);
+		if (splitHoriz) {
+			for (int i = 0; i < tile.width; i++) {
 				long count = tile.getColSum(i);
-				if (count == 0){
+				if (count == 0) {
 					if (firstEmpty < 0)
 						firstEmpty = i;
 					countEmpty++;
 				} else {
-					if (countEmpty > maxEmpty || (countEmpty > 10 && countLastPart > maxNodes/3 && countRemaining > maxNodes/3)){
-						java.awt.geom.Area empty = new java.awt.geom.Area(new Rectangle(firstEmpty,tile.y,countEmpty,tile.height));
+					if (countEmpty > maxEmpty
+							|| (countEmpty > minEmpty && countLastPart > maxNodes / 3 && countRemaining > maxNodes / 3)) {
+						java.awt.geom.Area empty = new java.awt.geom.Area(
+								new Rectangle(firstEmpty, tile.y, countEmpty, tile.height));
 						area.subtract(empty);
 						countLastPart = 0;
 					}
@@ -431,15 +441,17 @@ public class SplittableDensityArea {
 				}
 			}
 		} else {
-			for (int i = 0; i < tile.height; i++){
+			for (int i = 0; i < tile.height; i++) {
 				long count = tile.getRowSum(i);
-				if (count == 0){
+				if (count == 0) {
 					if (firstEmpty < 0)
 						firstEmpty = i;
 					countEmpty++;
 				} else {
-					if (countEmpty > maxEmpty || (countEmpty > 10 && countLastPart > maxNodes/3 && countRemaining > maxNodes/3)){
-						java.awt.geom.Area empty = new java.awt.geom.Area(new Rectangle(tile.x,firstEmpty,tile.width,countEmpty));
+					if (countEmpty > maxEmpty
+							|| (countEmpty > minEmpty && countLastPart > maxNodes / 3 && countRemaining > maxNodes / 3)) {
+						java.awt.geom.Area empty = new java.awt.geom.Area(
+								new Rectangle(tile.x, firstEmpty, tile.width, countEmpty));
 						area.subtract(empty);
 						countLastPart = 0;
 					}
@@ -451,19 +463,19 @@ public class SplittableDensityArea {
 			}
 		}
 		ArrayList<Tile> clusters = new ArrayList<>();
-		if (depth == 0 && area.isSingular()){
-			// try also the other split axis 
-			clusters.addAll(checkForEmptyClusters(depth + 1, tile.trim(), !splitHoriz ));
+		if (depth == 0 && area.isSingular()) {
+			// try also the other split axis
+			clusters.addAll(checkForEmptyClusters(depth + 1, tile.trim(), !splitHoriz));
 		} else {
-			if (area.isSingular()){
+			if (area.isSingular()) {
 				clusters.add(tile.trim());
 			} else {
 				List<List<Point>> shapes = Utils.areaToShapes(area);
-				for (List<Point> shape: shapes){
+				for (List<Point> shape : shapes) {
 					java.awt.geom.Area part = Utils.shapeToArea(shape);
 					Tile t = new Tile(extraDensityInfo, part.getBounds());
 					if (t.getCount() > 0)
-						clusters.addAll(checkForEmptyClusters(depth + 1, t.trim(), !splitHoriz ));
+						clusters.addAll(checkForEmptyClusters(depth + 1, t.trim(), !splitHoriz));
 				}
 			}
 		}
@@ -472,30 +484,33 @@ public class SplittableDensityArea {
 
 	/**
 	 * Split, handling a polygon that may contain multiple distinct areas.
+	 * 
 	 * @param polygonArea
 	 * @return a list of areas that cover the polygon
 	 */
 	private List<Area> splitPolygon(final java.awt.geom.Area polygonArea) {
 		List<Area> result = new ArrayList<>();
 		List<List<Point>> shapes = Utils.areaToShapes(polygonArea);
-		for (int i = 0; i < shapes.size(); i++){
+		for (int i = 0; i < shapes.size(); i++) {
 			List<Point> shape = shapes.get(i);
-			if (Utils.clockwise(shape) == false)
+			if (!Utils.clockwise(shape))
 				continue;
 			java.awt.geom.Area shapeArea = Utils.shapeToArea(shape);
 			Rectangle rShape = shapeArea.getBounds();
-			if (shape.size() > MAX_SINGLE_POLYGON_VERTICES){
+			if (shape.size() > MAX_SINGLE_POLYGON_VERTICES) {
 				shapeArea = new java.awt.geom.Area(rShape);
-				System.out.println("Warning: shape is too complex, using rectangle " + rShape+ " instead");
+				System.out.println("Warning: shape is too complex, using rectangle " + rShape + " instead");
 			}
-			Area shapeBounds = new Area(rShape.y, rShape.x,(int)rShape.getMaxY(), (int)rShape.getMaxX());
-			int resolution = 24-allDensities.getShift();
-			shapeBounds  = RoundingUtils.round(shapeBounds, resolution);
-			SplittableDensityArea splittableArea = new SplittableDensityArea(allDensities.subset(shapeBounds), startSearchLimit);
+			Area shapeBounds = new Area(rShape.y, rShape.x, (int) rShape.getMaxY(), (int) rShape.getMaxX());
+			int resolution = 24 - allDensities.getShift();
+			shapeBounds = RoundingUtils.round(shapeBounds, resolution);
+			SplittableDensityArea splittableArea = new SplittableDensityArea(allDensities.subset(shapeBounds),
+					startSearchLimit);
 			splittableArea.setMaxNodes(maxNodes);
-			if (splittableArea.hasData() == false){
-				System.out.println("Warning: a part of the bounding polygon would be empty and is ignored:" + shapeBounds);
-				//result.add(shapeBounds);
+			if (!splittableArea.hasData()) {
+				System.out.println(
+						"Warning: a part of the bounding polygon would be empty and is ignored:" + shapeBounds);
+				// result.add(shapeBounds);
 				continue;
 			}
 			List<Area> partResult = splittableArea.split(shapeArea);
@@ -504,97 +519,102 @@ public class SplittableDensityArea {
 		}
 		return result;
 	}
-	
 
 	/**
-	 * Split the given tile using the given (singular) polygon area. The routine splits the polygon into parts
-	 * and calls itself recursively for each part that is not rectangular.
-	 * @param depth recursion depth
-	 * @param tile the tile to split
+	 * Split the given tile using the given (singular) polygon area. The routine
+	 * splits the polygon into parts and calls itself recursively for each part that
+	 * is not rectangular.
+	 * 
+	 * @param depth               recursion depth
+	 * @param tile                the tile to split
 	 * @param rasteredPolygonArea an area describing a rectilinear shape
-	 * @return a solution (maybe empty)
+	 * @return a solution (maybe empty), or null if rasteredPolygon is not rectangular
 	 */
 	private Solution findSolutionWithSinglePolygon(int depth, final Tile tile, java.awt.geom.Area rasteredPolygonArea) {
-		assert rasteredPolygonArea.isSingular();
-		if (rasteredPolygonArea.isRectangular()){
+		if (!rasteredPolygonArea.isSingular()) {
+			return null;
+		}
+		if (rasteredPolygonArea.isRectangular()) {
 			Tile part = new Tile(extraDensityInfo, rasteredPolygonArea.getBounds());
 			return solveRectangularArea(part);
 		}
 		List<List<Point>> shapes = Utils.areaToShapes(rasteredPolygonArea);
 		List<Point> shape = shapes.get(0);
-		
-		if (shape.size() > MAX_SINGLE_POLYGON_VERTICES){
+
+		if (shape.size() > MAX_SINGLE_POLYGON_VERTICES) {
 			Tile part = new Tile(extraDensityInfo, rasteredPolygonArea.getBounds());
 			System.out.println("Warning: shape is too complex, using rectangle " + part + " instead");
 			return solveRectangularArea(part);
 		}
-		
+
 		Rectangle pBounds = rasteredPolygonArea.getBounds();
 		int lastPoint = shape.size() - 1;
 		if (shape.get(0).equals(shape.get(lastPoint)))
 			--lastPoint;
-		for (int i = 0; i <= lastPoint; i++){
+		for (int i = 0; i <= lastPoint; i++) {
 			Point point = shape.get(i);
 			if (i > 0 && point.equals(shape.get(0)))
 				continue;
 			int cutX = point.x;
 			int cutY = point.y;
-			Solution part0Sol = null,part1Sol = null;
-			for (int axis = 0; axis < 2; axis++){
-				Rectangle r1,r2;
-				if (axis == AXIS_HOR){
-					r1 = new Rectangle(pBounds.x,pBounds.y,cutX-pBounds.x,pBounds.height);
-					r2 = new Rectangle(cutX,pBounds.y,(int)(pBounds.getMaxX()-cutX),pBounds.height);
+			Solution part0Sol = null, part1Sol = null;
+			for (int axis = 0; axis < 2; axis++) {
+				Rectangle r1, r2;
+				if (axis == AXIS_HOR) {
+					r1 = new Rectangle(pBounds.x, pBounds.y, cutX - pBounds.x, pBounds.height);
+					r2 = new Rectangle(cutX, pBounds.y, (int) (pBounds.getMaxX() - cutX), pBounds.height);
 				} else {
-					r1 = new Rectangle(pBounds.x,pBounds.y,pBounds.width,cutY-pBounds.y);
-					r2 = new Rectangle(pBounds.x,cutY,pBounds.width,(int)(pBounds.getMaxY()-cutY));
+					r1 = new Rectangle(pBounds.x, pBounds.y, pBounds.width, cutY - pBounds.y);
+					r2 = new Rectangle(pBounds.x, cutY, pBounds.width, (int) (pBounds.getMaxY() - cutY));
 				}
 
-				if (r1.width * r1.height> r2.width * r2.height){
+				if (r1.width * r1.height > r2.width * r2.height) {
 					Rectangle help = r1;
 					r1 = r2;
 					r2 = help;
 				}
-				if (r1.isEmpty() == false && r2.isEmpty() == false){
+				if (!r1.isEmpty() && !r2.isEmpty()) {
 					java.awt.geom.Area area = new java.awt.geom.Area(r1);
 					area.intersect(rasteredPolygonArea);
-					
-					part0Sol = findSolutionWithSinglePolygon(depth+1, tile, area);
-					if (part0Sol != null && part0Sol.isEmpty() == false){
+
+					part0Sol = findSolutionWithSinglePolygon(depth + 1, tile, area);
+					if (part0Sol != null && !part0Sol.isEmpty()) {
 						area = new java.awt.geom.Area(r2);
 						area.intersect(rasteredPolygonArea);
-						part1Sol = findSolutionWithSinglePolygon(depth+1, tile, area);
-						if (part1Sol != null && part1Sol.isEmpty() == false)
+						part1Sol = findSolutionWithSinglePolygon(depth + 1, tile, area);
+						if (part1Sol != null && !part1Sol.isEmpty())
 							break;
 					}
 				}
 			}
-			if (part1Sol != null){
+			if (part0Sol != null && part1Sol != null) {
 				part0Sol.merge(part1Sol);
 				return part0Sol;
 			}
 		}
 		return new Solution(maxNodes);
 	}
-	
+
 	/**
-	 * Try to split the tile into nice parts recursively. 
+	 * Try to split the tile into nice parts recursively.
+	 * 
 	 * @param depth the recursion depth
-	 * @param tile the tile to be split
-	 * @return a solution instance or null 
+	 * @param tile  the tile to be split
+	 * @param smiParent meta info for parent tile
+	 * @return a solution instance or null
 	 */
-	private Solution findSolution(int depth, final Tile tile, Tile parent, TileMetaInfo smiParent){
+	private Solution findSolution(int depth, final Tile tile, Tile parent, TileMetaInfo smiParent) {
 		boolean addAndReturn = false;
-		if (tile.getCount() == 0){
-			if (!allowEmptyPart){
-				hasEmptyPart  = true;
+		if (tile.getCount() == 0) {
+			if (!allowEmptyPart) {
+				hasEmptyPart = true;
 				return null;
 			}
-			if  (tile.width * tile.height <= 4) 
+			if (tile.width * tile.height <= 4)
 				return null;
 			return new Solution(maxNodes); // allow empty part of the world
 		} else if (tile.getCount() > maxNodes && tile.width == 1 && tile.height == 1) {
-			addAndReturn = true;  // can't split further
+			addAndReturn = true; // can't split further
 		} else if (tile.getCount() < minNodes && depth == 0) {
 			addAndReturn = true; // nothing to do
 		} else if (tile.getCount() < minNodes) {
@@ -603,59 +623,56 @@ public class SplittableDensityArea {
 			double ratio = tile.getAspectRatio();
 			if (ratio < 1.0)
 				ratio = 1.0 / ratio;
-			if (ratio < maxAspectRatio){ 
+			if (ratio <= maxAspectRatio) {
 				if (ignoreSize || maxNodes >= LARGE_MAX_NODES || checkSize(tile))
 					addAndReturn = true;
 			}
 		} else if (tile.width < 2 && tile.height < 2) {
 			return null;
-		} 
-		if (tile.outsidePolygon()){
-			return new Solution(maxNodes);
 		}
-		if (addAndReturn){
+		if (addAndReturn) {
 			double outsidePolygonRatio = tile.calcOutsidePolygonRatio();
-			if (outsidePolygonRatio > maxOutsidePolygonRatio ){
+			if (outsidePolygonRatio > maxOutsidePolygonRatio) {
 				return null;
 			}
 			Solution solution = new Solution(maxNodes);
-			solution.add(tile);  // can't split further
+			solution.add(tile); // can't split further
 			return solution;
 		}
-		if (tile.getCount() < minNodes * 2){
+		if (tile.getCount() < minNodes * 2) {
 			return null;
 		}
 		Solution cached = searchGoodSolutions(tile);
-		if (cached != null){
+		if (cached != null) {
 			return cached;
-		} 
+		}
 		// we have to split the tile
 		Integer alreadyDone = null;
-		if (countBad == 0 && incomplete.size() > 0){
+		if (countBad == 0 && incomplete.size() > 0) {
 			alreadyDone = incomplete.remove(tile);
 			if (alreadyDone == null)
 				incomplete.clear(); // rest is not useful
 		}
-		
-		if (alreadyDone == null && depth > 0 && tile.width * tile.height > 100){
+
+		if (alreadyDone == null && depth > 0 && tile.width * tile.height > 100) {
 			if (knownBad.contains(tile))
 				return null;
 		}
 
-		// copy the existing density info from parent 
+		// copy the existing density info from parent
 		// typically, at least one half can be re-used
 		TileMetaInfo smi = new TileMetaInfo(tile, parent, smiParent);
-		
+
 		// we have to split the tile
-		int axis = (tile.getAspectRatio() >= 1.0) ? AXIS_HOR:AXIS_VERT;
-		
+		int axis = (tile.getAspectRatio() >= 1.0) ? AXIS_HOR : AXIS_VERT;
+
 		IntArrayList todoList = generateTestCases(axis, tile, smi);
 		int countAxis = 0;
 		int usedTestPos = 0;
 		int countDone = 0;
 		Solution bestSol = null;
-		while(true){
-			if (usedTestPos >= todoList.size()){
+		while (true) {
+			if (usedTestPos >= todoList.size()) {
 				countAxis++;
 				if (countAxis > 1)
 					break;
@@ -665,13 +682,14 @@ public class SplittableDensityArea {
 				continue;
 			}
 			countDone++;
-			if (alreadyDone != null && countDone <= alreadyDone.intValue()){
+			if (alreadyDone != null && countDone <= alreadyDone.intValue()) {
+				usedTestPos++; // we already checked this split before
 				continue;
 			}
 			int splitPos = todoList.getInt(usedTestPos++);
-			// create the two parts of the tile 
+			// create the two parts of the tile
 			boolean ok = false;
-			if (axis == AXIS_HOR){
+			if (axis == AXIS_HOR) {
 				ok = tile.splitHoriz(splitPos, smi);
 			} else {
 				ok = tile.splitVert(splitPos, smi);
@@ -680,28 +698,30 @@ public class SplittableDensityArea {
 				continue;
 
 			Tile[] parts = smi.getParts();
-			if (trimTiles){
+			if (trimTiles) {
 				parts[0] = parts[0].trim();
 				parts[1] = parts[1].trim();
 			}
-			if (parts[0].getCount() > parts[1].getCount()){
+			if (parts[0].getCount() > parts[1].getCount()) {
 				// first try the less populated part
 				Tile help = parts[0];
 				parts[0] = parts[1];
 				parts[1] = help;
 			}
-			Solution [] sols = new Solution[2];
+			Solution[] sols = new Solution[2];
 			int countOK = 0;
-			for (int i = 0; i < 2; i++){
+			for (int i = 0; i < 2; i++) {
+				if (i == 0 && alreadyDone != null)
+					continue;
 				// depth first recursive search
 //				long t1 = System.currentTimeMillis();
 				sols[i] = findSolution(depth + 1, parts[i], tile, smi);
 //				long dt = System.currentTimeMillis() - t1;
 //				if (dt > 100 && tile.getCount() < 8 * maxNodes)
 //					System.out.println("took " + dt + " ms to find " + sols[i] + " for "+ parts[i]);
-				if (sols[i] == null){
+				if (sols[i] == null) {
 					countBad++;
-//					if (countBad >= searchLimit){
+//					if (countBad >= searchLimit) {
 //						if (countBad == searchLimit)
 //							System.out.println("giving up at depth " + depth + " with currX = " + currX + " and currY = "+ currY + " at tile " + tile + " bad: " + saveCountBad );
 //						else 
@@ -712,48 +732,50 @@ public class SplittableDensityArea {
 				checkIfGood(parts[i], sols[i]);
 				countOK++;
 			}
-			if (countOK == 2){
+			if (countOK == 2) {
 				Solution sol = sols[0];
 				sol.merge(sols[1]);
 				bestSol = sol;
 				break; // we found a valid split and searched the direct neighbours
 			}
-			if (countBad >= searchLimit){
-				incomplete.put(tile, countDone-1); 
+			if (countBad >= searchLimit) {
+				incomplete.put(tile, countDone - 1);
 				break;
 			}
 		}
-		
+
 		smi.propagateToParent(smiParent, tile, parent);
-			
-		if (bestSol == null && countBad < searchLimit && depth > 0 && tile.width * tile.height > 100){
+
+		if (bestSol == null && countBad < searchLimit && depth > 0 && tile.width * tile.height > 100) {
 			knownBad.add(tile);
 		}
 		return bestSol;
 	}
-	
+
 	private boolean checkSize(Tile tile) {
-		return tile.height <= maxTileHeight && tile.width <= maxTileWidth; 
+		return tile.height <= maxTileHeight && tile.width <= maxTileWidth;
 	}
-	
+
 	/**
-	 * Get a first solution and search for better ones until
-	 * either a nice solution is found or no improvement was
-	 * found.
+	 * Get a first solution and search for better ones until either a nice solution
+	 * is found or no improvement was found.
+	 * 
 	 * @param startTile the tile to split
 	 * @return a solution (maybe be empty)
 	 */
-	private Solution solveRectangularArea(Tile startTile){
-		// start values for optimization process: we make little steps towards a good solution
-//		spread = 7;
-	    if (startTile.getCount() == 0)
-	        return new Solution(maxNodes);
+	private Solution solveRectangularArea(Tile startTile) {
+		// start values for optimization process: we make little steps towards a good
+		// solution
+		if (startTile.getCount() == 0)
+			return new Solution(maxNodes);
 		searchLimit = startSearchLimit;
-		minNodes = Math.max(Math.min((long)(0.05 * maxNodes), extraDensityInfo.getNodeCount()), 1); 
-
-		if (extraDensityInfo.getNodeCount() / maxNodes < 4){
+		
+		final long startMinNodes = Math.max(Math.min((long) (0.05 * maxNodes), extraDensityInfo.getNodeCount()), 1);
+		minNodes = startMinNodes;
+		
+		if (extraDensityInfo.getNodeCount() / maxNodes < 4) {
 			maxAspectRatio = 32;
-		} else { 
+		} else {
 			maxAspectRatio = startTile.getAspectRatio();
 			if (maxAspectRatio < 1)
 				maxAspectRatio = 1 / maxAspectRatio;
@@ -763,51 +785,58 @@ public class SplittableDensityArea {
 		goodSolutions = new HashMap<>(GOOD_SOL_INIT_SIZE);
 		goodRatio = 0.5;
 		TileMetaInfo smiStart = new TileMetaInfo(startTile, null, null);
-		if (startTile.getCount() < 300 * maxNodes && (checkSize(startTile) || startTile.getCount() < 10 * maxNodes) ){
+		if (!ignoreSize && startTile.getCount() < 300 * maxNodes && (checkSize(startTile) || startTile.getCount() < 10 * maxNodes)) {
 			searchAll = true;
 		}
-		
+		boolean algorithmnWasSwitched = false;
+
 		if (!beQuiet)
 			System.out.println("Trying to find nice split for " + startTile);
 		Solution bestSolution = new Solution(maxNodes);
-		Solution prevBest = new Solution(maxNodes);
 		long t1 = System.currentTimeMillis();
 		incomplete = new LinkedHashMap<>();
 		resetCaches();
-		for (int numLoops = 0; numLoops < MAX_LOOPS; numLoops++){
-			double saveMaxAspectRatio = maxAspectRatio; 
+		boolean clearIncomplete = false;
+		Solution firstSolution = new Solution(maxNodes);
+		for (int numLoops = 0; numLoops < MAX_LOOPS; numLoops++) {
+			if (clearIncomplete)
+				incomplete.clear();
+			clearIncomplete = true;
+			double saveMaxAspectRatio = maxAspectRatio;
 			long saveMinNodes = minNodes;
 			boolean foundBetter = false;
 			Solution solution = null;
 			countBad = 0;
-			if (!beQuiet){
-				System.out.println("searching for split with min-nodes " + minNodes + ", learned " + goodSolutions.size() + " good partial solutions");
+			if (!beQuiet) {
+				System.out.println("searching for split with min-nodes " + minNodes + ", learned "
+						+ goodSolutions.size() + " good partial solutions");
 			}
 			smiStart.setMinNodes(minNodes);
 			solution = findSolution(0, startTile, startTile, smiStart);
-			if (solution != null){
+			if (solution != null) {
 				foundBetter = bestSolution.compareTo(solution) > 0;
-				if (foundBetter){
-					prevBest = bestSolution;
+				if (foundBetter) {
+					Solution prevBest = bestSolution;
 					bestSolution = solution;
-					
-					System.out.println("Best solution until now: " + bestSolution.toString() + ", elapsed search time: " + (System.currentTimeMillis() - t1) / 1000 + " s");
+					if (bestSolution.compareTo(firstSolution) < 0) {
+						System.out.println("Best solution until now: " + bestSolution.toString() + ", elapsed search time: "
+								+ (System.currentTimeMillis() - t1) / 1000 + " s");
+					}
 					filterGoodSolutions(bestSolution);
 					// change criteria to find a better(nicer) result
 					double factor = 1.10;
-					if (prevBest.isEmpty() == false && prevBest.isNice() )
-						factor = Math.min(1.30,(double)bestSolution.getWorstMinNodes() / prevBest.getWorstMinNodes());
-					minNodes = Math.max(maxNodes /3, (long) (bestSolution.getWorstMinNodes() * factor));
+					if (!prevBest.isEmpty() && prevBest.isNice())
+						factor = Math.min(1.30, (double) bestSolution.getWorstMinNodes() / prevBest.getWorstMinNodes());
+					minNodes = Math.max(maxNodes / 3, (long) (bestSolution.getWorstMinNodes() * factor));
 				}
-				if (bestSolution.size() == 1){
+				if (bestSolution.size() == 1) {
 					if (!beQuiet)
 						System.out.println("This can't be improved.");
 					break;
 				}
-			} 
-			else {
-				if (bestSolution.isEmpty() == false){
-					if (minNodes > bestSolution.getWorstMinNodes() + 1){
+			} else {
+				if (!bestSolution.isEmpty()) {
+					if (minNodes > bestSolution.getWorstMinNodes() + 1) {
 						// reduce minNodes
 						minNodes = (bestSolution.getWorstMinNodes() + minNodes) / 2;
 						if (minNodes < bestSolution.getWorstMinNodes() * 1.001)
@@ -815,21 +844,23 @@ public class SplittableDensityArea {
 					}
 				}
 			}
-			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)
+			maxAspectRatio = Math.max(bestSolution.getWorstAspectRatio() / 2, NICE_MAX_ASPECT_RATIO);
+			maxAspectRatio = Math.min(32, maxAspectRatio);
+			if (!bestSolution.isEmpty() && 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 (countBad > searchLimit && searchLimit < 5_000_000){
+			if (saveMaxAspectRatio == maxAspectRatio && saveMinNodes == minNodes) {
+				// no improvement found
+				if (bestSolution.isEmpty() || bestSolution.getWorstMinNodes() < 0.5 * maxNodes) {
+					if (countBad > searchLimit && searchLimit < 5_000_000) {
 						searchLimit *= 2;
+						clearIncomplete = false;
 						resetCaches();
 						System.out.println("No good solution found, duplicated search-limit to " + searchLimit);
 						continue;
 					}
-					if (bestSolution.isEmpty() && minNodes > 1){
+					if (bestSolution.isEmpty() && minNodes > 1) {
 						minNodes = 1;
 						resetCaches();
 						searchLimit = startSearchLimit;
@@ -839,54 +870,65 @@ public class SplittableDensityArea {
 						// 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);
+							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);
+							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);
-						
+							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)
-							minNodes = bestSolution.getWorstMinNodes() + 1;
-						else 
-							minNodes = maxNodes / 100;
-						System.out.println("Still no good solution found, trying alternate algorithm");
+					if (!algorithmnWasSwitched) {
+						System.out.println("Still no good solution found, trying alternative algorithm");
+						firstSolution = bestSolution;
+						bestSolution = new Solution(maxNodes);
+						minNodes = startMinNodes;
+						searchLimit = startSearchLimit;
+						searchAll = !searchAll;
+						algorithmnWasSwitched = true;
 						continue;
 					}
-				}  
+				}
 				break;
 			}
-
-		} 
+		}
+		if (bestSolution.compareTo(firstSolution) > 0)
+			bestSolution = firstSolution;
 		if (!beQuiet)
 			printFinishMsg(bestSolution);
 		return bestSolution;
 	}
 
-	private void resetCaches(){
+	private void resetCaches() {
 		knownBad = new HashSet<>(50_000);
 	}
-	
-	private void printFinishMsg(Solution solution){
-		if (!beQuiet){
-			if (solution.isEmpty() == false){
+
+	private void printFinishMsg(Solution solution) {
+		if (!beQuiet) {
+			if (!solution.isEmpty()) {
 				if (solution.getWorstMinNodes() > VERY_NICE_FILL_RATIO * maxNodes && solution.isNice())
-					System.out.println("Solution is very nice. No need to search for a better solution: " + solution.toString());
-				else 
-					System.out.println("Solution is " + (solution.isNice() ? "":"not ") + "nice. Can't find a better solution with search-limit " + searchLimit + ": " + solution.toString());
+					System.out.println(
+							"Solution is very nice. No need to search for a better solution: " + solution.toString());
+				else
+					System.out.println("Solution is " + (solution.isNice() ? "" : "not ")
+							+ "nice. Can't find a better solution with search-limit " + searchLimit + ": "
+							+ solution.toString());
 			}
 		}
-		return;
 	}
-	
+
 	/**
-	 * Convert the list of Tile instances of a solution to Area instances, report some
-	 * statistics.
-	 * @param sol the solution
-	 * @param polygonArea 
+	 * Convert the list of Tile instances of a solution to Area instances, report
+	 * some statistics.
+	 * 
+	 * @param sol         the solution
+	 * @param polygonArea the split polygon
 	 * 
 	 * @return list of areas
 	 */
@@ -894,46 +936,46 @@ public class SplittableDensityArea {
 		List<Area> result = new ArrayList<>();
 		int minLat = getAllDensities().getBounds().getMinLat();
 		int minLon = getAllDensities().getBounds().getMinLong();
-		
-		if (polygonArea != null){
+
+		if (polygonArea != null) {
 			System.out.println("Trying to cut the areas so that they fit into the polygon ...");
 		} else {
 			if (trimShape)
 				sol.trimOuterTiles();
 		}
-		
-		boolean fits  = true;
+
+		boolean fits = true;
 		for (Tile tile : sol.getTiles()) {
 			if (tile.getCount() == 0)
 				continue;
-			if (tile.verify() == false)
+			if (!tile.verify())
 				throw new SplitFailedException("found invalid tile");
-			Rectangle r = new Rectangle(minLon + (tile.x << shift), minLat + (tile.y << shift), 
-					tile.width << shift, tile.height << shift);
-			
-			if (polygonArea != null){
+			Rectangle r = new Rectangle(minLon + (tile.x << shift), minLat + (tile.y << shift), tile.width << shift,
+					tile.height << shift);
+
+			if (polygonArea != null) {
 				java.awt.geom.Area cutArea = new java.awt.geom.Area(r);
 				cutArea.intersect(polygonArea);
-				if (cutArea.isEmpty() == false && cutArea.isRectangular() )
+				if (!cutArea.isEmpty() && cutArea.isRectangular()) {
 					r = cutArea.getBounds();
-				else {
+				} else {
 					fits = false;
 				}
 			}
-			Area area = new Area(r.y,r.x,(int)r.getMaxY(),(int)r.getMaxX());
-			if (!beQuiet){
+			Area area = new Area(r.y, r.x, (int) r.getMaxY(), (int) r.getMaxX());
+			if (!beQuiet) {
 				String note;
 				if (tile.getCount() > maxNodes)
 					note = " but is already at the minimum size so can't be split further";
 				else
 					note = "";
 				long percentage = 100 * tile.getCount() / maxNodes;
-				System.out.println("Area " + currMapId++ + " covers " + area 
-						+ " and contains " + tile.getCount() + " nodes (" + percentage + " %)" + note);
+				System.out.println("Area " + currMapId++ + " covers " + area + " and contains " + tile.getCount()
+						+ " nodes (" + percentage + " %)" + note);
 			}
 			result.add(area);
 		}
-		if (fits == false){
+		if (!fits) {
 			System.out.println("One or more areas do not exactly fit into the bounding polygon");
 		}
 		return result;
@@ -941,16 +983,16 @@ public class SplittableDensityArea {
 	}
 
 	/**
-	 * Generate a list of split positions. 
-	 * This is essential: The shorter the list, the faster the search, so we try to
-	 * put only good candidates into the list. 
-	 * @param axis
-	 * @param tile
-	 * @param smi
-	 * @return
+	 * Generate a list of split positions. This is essential: The shorter the list,
+	 * the faster the search, so we try to put only good candidates into the list.
+	 * 
+	 * @param axis horizontal or vertical
+	 * @param tile the tile
+	 * @param smi  the meta info
+	 * @return list of split positions
 	 */
 	private IntArrayList generateTestCases(int axis, Tile tile, TileMetaInfo smi) {
-		if (searchAll){
+		if (searchAll) {
 			return (axis == AXIS_HOR) ? tile.genXTests(smi) : tile.genYTests(smi);
 		}
 		double ratio = tile.getAspectRatio();
@@ -960,47 +1002,48 @@ public class SplittableDensityArea {
 		int start = (axis == AXIS_HOR) ? tile.findValidStartX(smi) : tile.findValidStartY(smi);
 		int end = (axis == AXIS_HOR) ? tile.findValidEndX(smi) : tile.findValidEndY(smi);
 		int range = end - start;
-		if (range < 0){
+		if (range < 0) {
 			// can't split tile without having one part that has too few nodes
 			return tests;
 		}
-		if (range > 1024 && (axis == AXIS_HOR && tile.width >= maxTileWidth || axis == AXIS_VERT && tile.height >= maxTileWidth)){
-			// large tile, just split at a few valid positions 
+		if (range > 1024 && (axis == AXIS_HOR && tile.width >= maxTileWidth
+				|| axis == AXIS_VERT && tile.height >= maxTileHeight)) {
+			// large tile, just split at a few valid positions
 			for (int i = 5; i > 1; --i)
 				tests.add(start + range / i);
-		}
-		else if (tile.getCount() < maxNodes * 4 && range > 256){
+		} else if (tile.getCount() < maxNodes * 4 && range > 256) {
 			// large tile with rather few nodes, allow more tests
 			int step = (range) / 20;
 			for (int pos = start; pos <= end; pos += step)
 				tests.add(pos);
-		}
-		else if (tile.getCount() > maxNodes * 4){
+		} else if (tile.getCount() > maxNodes * 4) {
 			int step = range / 7; // 7 turned out to be a good value here
 			if (step < 1)
 				step = 1;
 			for (int pos = start; pos <= end; pos += step)
 				tests.add(pos);
 		} else {
-			// this will be one of the last splits 
+			// this will be one of the last splits
 			long nMax = tile.getCount() / minNodes;
 			if (nMax * minNodes < tile.getCount())
 				nMax++;
 			long nMin = tile.getCount() / maxNodes;
 			if (nMin * maxNodes < tile.getCount())
 				nMin++;
-			if (nMin > 2 && nMin * maxNodes - minNodes < tile.getCount() && ratio > 0.125 && ratio < 8){
-				// count is near (but below) a multiple of max-nodes, we have to test all candidates  
-				// to make sure that we don't miss a good split 
+			if (nMin > 2 && nMin * maxNodes - minNodes < tile.getCount() && ratio > 0.125 && ratio < 8) {
+				// count is near (but below) a multiple of max-nodes, we have to test all
+				// candidates
+				// to make sure that we don't miss a good split
 				return (axis == AXIS_HOR) ? tile.genXTests(smi) : tile.genYTests(smi);
 			}
-			if (nMax == 2 || nMin == 2){
+			if (nMax == 2 || nMin == 2) {
 				tests.add((axis == AXIS_HOR) ? tile.findHorizontalMiddle(smi) : tile.findVerticalMiddle(smi));
-				int pos = (axis == AXIS_HOR) ? tile.findFirstXHigher(smi, minNodes) + 1 : tile.findFirstYHigher(smi, minNodes) + 1;
+				int pos = (axis == AXIS_HOR) ? tile.findFirstXHigher(smi, minNodes) + 1
+						: tile.findFirstYHigher(smi, minNodes) + 1;
 				if (tests.get(0) != pos)
 					tests.add(pos);
 				pos = (axis == AXIS_HOR) ? tile.findFirstXHigher(smi, maxNodes) : tile.findFirstYHigher(smi, maxNodes);
-				if (tests.contains(pos) == false)
+				if (!tests.contains(pos))
 					tests.add(pos);
 			} else {
 				if (range == 0) {
@@ -1008,9 +1051,9 @@ public class SplittableDensityArea {
 				} else {
 					if (nMax != 3)
 						tests.add((axis == AXIS_HOR) ? tile.findHorizontalMiddle(smi) : tile.findVerticalMiddle(smi));
-					if (tests.contains(start) == false)
+					if (!tests.contains(start))
 						tests.add(start);
-					if (tests.contains(end) == false)
+					if (!tests.contains(end))
 						tests.add(end);
 				}
 			}
@@ -1018,5 +1061,3 @@ public class SplittableDensityArea {
 		return tests;
 	}
 }
-
-



View it on GitLab: https://salsa.debian.org/debian-gis-team/mkgmap-splitter/-/commit/fbfad6b2f357bfc3e13f836f14a658892ae19d53

-- 
View it on GitLab: https://salsa.debian.org/debian-gis-team/mkgmap-splitter/-/commit/fbfad6b2f357bfc3e13f836f14a658892ae19d53
You're receiving this email because of your account on salsa.debian.org.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://alioth-lists.debian.net/pipermail/pkg-grass-devel/attachments/20210701/bb029593/attachment-0001.htm>


More information about the Pkg-grass-devel mailing list