[Git][debian-gis-team/mkgmap-splitter][experimental] 4 commits: New upstream version 0.0.0+svn615
Bas Couwenberg (@sebastic)
gitlab at salsa.debian.org
Thu Jul 1 06:29:14 BST 2021
Bas Couwenberg pushed to branch experimental 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
- - - - -
0b721c33 by Bas Couwenberg at 2021-07-01T07:20:28+02:00
Update upstream source from tag 'upstream/0.0.0+svn615'
Update to upstream version '0.0.0+svn615'
with Debian dir 1ea580756f0d7f82c7e4ef7176aaef2340c3eef1
- - - - -
6639fe5b by Bas Couwenberg at 2021-07-01T07:20:47+02:00
New upstream SVN snapshot.
- - - - -
2ab41c7c by Bas Couwenberg at 2021-07-01T07:22:08+02:00
Set distribution to experimental.
- - - - -
5 changed files:
- debian/changelog
- 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:
=====================================
debian/changelog
=====================================
@@ -1,3 +1,9 @@
+mkgmap-splitter (0.0.0+svn615-1~exp1) experimental; urgency=medium
+
+ * New upstream SVN snapshot.
+
+ -- Bas Couwenberg <sebastic at debian.org> Thu, 01 Jul 2021 07:21:55 +0200
+
mkgmap-splitter (0.0.0+svn602-1~exp1) experimental; urgency=medium
* New upstream SVN snapshot.
=====================================
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/-/compare/c2d6f64c7966e054b6c03a0f41ec1235ab8f76da...2ab41c7c57b9ec9b74cba5281c5f6acf409a0e7b
--
View it on GitLab: https://salsa.debian.org/debian-gis-team/mkgmap-splitter/-/compare/c2d6f64c7966e054b6c03a0f41ec1235ab8f76da...2ab41c7c57b9ec9b74cba5281c5f6acf409a0e7b
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/72476dd5/attachment-0001.htm>
More information about the Pkg-grass-devel
mailing list