[Git][debian-gis-team/mkgmap-splitter][upstream] New upstream version 0.0.0+svn645
Bas Couwenberg (@sebastic)
gitlab at salsa.debian.org
Wed Dec 1 06:58:43 GMT 2021
Bas Couwenberg pushed to branch upstream at Debian GIS Project / mkgmap-splitter
Commits:
f8f0ee8b by Bas Couwenberg at 2021-12-01T07:46:56+01:00
New upstream version 0.0.0+svn645
- - - - -
22 changed files:
- build.xml
- resources/splitter-version.properties
- src/uk/me/parabola/splitter/BackgroundInputStream.java
- src/uk/me/parabola/splitter/Element.java
- src/uk/me/parabola/splitter/Main.java
- src/uk/me/parabola/splitter/MultiTileProcessor.java
- src/uk/me/parabola/splitter/Utils.java
- src/uk/me/parabola/splitter/args/ParamConverter.java
- src/uk/me/parabola/splitter/args/ParamParser.java
- src/uk/me/parabola/splitter/args/ReflectionUtils.java
- src/uk/me/parabola/splitter/geo/CityLoader.java
- src/uk/me/parabola/splitter/geo/DefaultCityFinder.java
- src/uk/me/parabola/splitter/solver/AreasCalculator.java
- src/uk/me/parabola/splitter/solver/DensityMap.java
- src/uk/me/parabola/splitter/solver/DensityMapCollector.java
- src/uk/me/parabola/splitter/solver/EnhancedDensityMap.java
- src/uk/me/parabola/splitter/solver/Solution.java
- src/uk/me/parabola/splitter/solver/SplittableDensityArea.java
- src/uk/me/parabola/splitter/solver/Tile.java
- src/uk/me/parabola/splitter/solver/TileMetaInfo.java
- test/func/lib/Outputs.java
- test/func/lib/TestUtils.java
Changes:
=====================================
build.xml
=====================================
@@ -216,6 +216,9 @@
<javac srcdir="${src}" destdir="${build.classes}" debug="yes" includeantruntime="false">
<include name="**/*.java"/>
<classpath refid="classpath"/>
+ <compilerarg value="-Xlint:all"/>
+ <compilerarg value="-Xlint:-serial"/>
+ <compilerarg value="-Xlint:-path"/>
</javac>
</target>
@@ -223,6 +226,9 @@
<javac srcdir="${test}" destdir="${build.test-classes}" debug="yes" includeantruntime="false">
<include name="**/*.java"/>
<classpath refid="test.classpath"/>
+ <compilerarg value="-Xlint:all"/>
+ <compilerarg value="-Xlint:-serial"/>
+ <compilerarg value="-Xlint:-path"/>
</javac>
</target>
=====================================
resources/splitter-version.properties
=====================================
@@ -1,2 +1,2 @@
-svn.version: 642
-build.timestamp: 2021-08-10T14:31:18+0100
+svn.version: 645
+build.timestamp: 2021-11-25T05:43:23+0000
=====================================
src/uk/me/parabola/splitter/BackgroundInputStream.java
=====================================
@@ -39,10 +39,9 @@ public class BackgroundInputStream extends InputStream {
this(source, QUEUE_SIZE, BUFFER_SIZE);
}
- public BackgroundInputStream(InputStream source, int queueSize, int bufferSize)
- {
- inQueue = new ArrayBlockingQueue<byte[]>(queueSize);
- recycleQueue = new ArrayBlockingQueue<byte[]>(queueSize + 1);
+ public BackgroundInputStream(InputStream source, int queueSize, int bufferSize) {
+ inQueue = new ArrayBlockingQueue<>(queueSize);
+ recycleQueue = new ArrayBlockingQueue<>(queueSize + 1);
sourceStream = source;
this.bufferSize = bufferSize;
}
=====================================
src/uk/me/parabola/splitter/Element.java
=====================================
@@ -41,20 +41,25 @@ public abstract class Element {
}
public static class Tag {
- public Tag(String key,String value) {
+ public final String key, value;
+
+ public Tag(String key, String value) {
this.key = key;
this.value = value;
}
+
public String getKey() {
return key;
}
+
public String getValue() {
return value;
}
- public String toString (){
+
+ @Override
+ public String toString() {
return key + "=" + value;
}
- final public String key,value;
}
public void addTag(String key, String value) {
=====================================
src/uk/me/parabola/splitter/Main.java
=====================================
@@ -228,8 +228,12 @@ public class Main {
if (areaList.getAreas().isEmpty()) {
System.err.println("Failed to calculate areas. See stdout messages for details.");
System.out.println("Failed to calculate areas.");
- System.out.println("Sorry. Cannot split the file without creating huge, almost empty, tiles.");
- System.out.println("Please specify a bounding polygon with the --polygon-file parameter.");
+ if (numTiles < 2) {
+ System.out.println("Sorry. Cannot split the file without creating huge, almost empty, tiles.");
+ System.out.println("Please specify a bounding polygon with the --polygon-file parameter.");
+ } else {
+ System.out.println("Probably the number of tiles is too high for the given resolution.");
+ }
throw new SplitFailedException("");
}
int mapId = mainOptions.getMapid();
=====================================
src/uk/me/parabola/splitter/MultiTileProcessor.java
=====================================
@@ -813,7 +813,7 @@ class MultiTileProcessor extends AbstractMapProcessor {
}
}
boolean complainedAboutSize = false;
- Rectangle mpBbox = null;
+ Rectangle mpBbox;
boolean hasMissingWays = false;
while (wayMembers.size() > 0){
polygonWays.clear();
=====================================
src/uk/me/parabola/splitter/Utils.java
=====================================
@@ -49,6 +49,10 @@ public class Utils {
public static final int MIN_LON_MAP_UNITS = toMapUnit(-180);
public static final int MAX_LON_MAP_UNITS = toMapUnit(180);
+ private Utils() {
+ // avoid implicit public constructor
+ }
+
public static String format(int number) {
return FORMATTER.format(number);
}
=====================================
src/uk/me/parabola/splitter/args/ParamConverter.java
=====================================
@@ -27,7 +27,7 @@ public class ParamConverter {
private final Map<Class<?>, Object> primitiveDefaults;
public ParamConverter() {
- converterMap = new HashMap<Class<?>, Converter<?>>(10);
+ converterMap = new HashMap<>(10);
converterMap.put(String.class, new Converter<String>() { @Override String convert(String value) { return value; } });
converterMap.put(Boolean.class, new Converter<Boolean>() { @Override Boolean convert(String value) { return Boolean.valueOf(value); } });
converterMap.put(Integer.class, new IntegerConverter());
@@ -35,7 +35,7 @@ public class ParamConverter {
converterMap.put(File.class, new Converter<File>() { @Override File convert(String value) { return new File(value); } });
converterMap.put(ThreadCount.class, new ThreadCountConverter());
- primitiveDefaults = new HashMap<Class<?>, Object>(10);
+ primitiveDefaults = new HashMap<>(10);
primitiveDefaults.put(Boolean.TYPE, Boolean.FALSE);
primitiveDefaults.put(Byte.TYPE, Byte.valueOf((byte) 0));
primitiveDefaults.put(Character.TYPE, Character.valueOf('\u0000'));
=====================================
src/uk/me/parabola/splitter/args/ParamParser.java
=====================================
@@ -64,6 +64,7 @@ public class ParamParser {
return errors;
}
+ @SuppressWarnings("unchecked")
private <P> P createProxy(Class<P> paramInterface, String... args) {
Map<String, MethodParamPair> params = new HashMap<>();
@@ -177,7 +178,7 @@ public class ParamParser {
return result;
}
- public <P> void displayUsage() {
+ public void displayUsage() {
System.out.println("Usage: java [JAVA_OPTIONS] -jar splitter.jar [OPTIONS] input_file (*.osm or *.pbf or *.o5m)");
System.out.println("Options:");
@@ -222,7 +223,7 @@ public class ParamParser {
return String.format("%1$-" + wantedLen + "s", s);
}
- private static <P> String getParameterName(Method method, Option option) {
+ private static String getParameterName(Method method, Option option) {
return option.name().length() == 0 ? ReflectionUtils.getParamName(method) : option.name();
}
=====================================
src/uk/me/parabola/splitter/args/ReflectionUtils.java
=====================================
@@ -23,7 +23,7 @@ import java.util.Map;
* @author Chris Miller
*/
public class ReflectionUtils {
- private static final Map<Class<?>, Class<?>> boxedMappings = new HashMap<Class<?>, Class<?>>(15);
+ private static final Map<Class<?>, Class<?>> boxedMappings = new HashMap<>(15);
static {
boxedMappings.put(Boolean.TYPE, Boolean.class);
=====================================
src/uk/me/parabola/splitter/geo/CityLoader.java
=====================================
@@ -56,7 +56,7 @@ public class CityLoader {
}
public List<City> load(BufferedReader reader) throws IOException {
- List<City> cities = new ArrayList<City>(1000);
+ List<City> cities = new ArrayList<>(1000);
String line;
int lineNumber = 0;
while ((line = reader.readLine()) != null) {
=====================================
src/uk/me/parabola/splitter/geo/DefaultCityFinder.java
=====================================
@@ -15,7 +15,6 @@ package uk.me.parabola.splitter.geo;
import java.util.Arrays;
import java.util.Collections;
-import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
@@ -42,12 +41,7 @@ public class DefaultCityFinder implements CityFinder {
lons = new int[cities.size()];
citiesByLat = new City[cities.size()];
- Collections.sort(cities, new Comparator<City>() {
- @Override
- public int compare(City c1, City c2) {
- return c1.getLat() < c2.getLat() ? -1 : c1.getLat() == c2.getLat() ? 0 : 1;
- }
- });
+ cities.sort((c1,c2) -> Integer.compare(c1.getLat(), c2.getLat()));
int i = 0;
for (City city : cities) {
lats[i] = city.getLat();
@@ -76,7 +70,7 @@ public class DefaultCityFinder implements CityFinder {
if (minLatIndex > maxLatIndex)
return Collections.emptySet();
- Set<City> hits = new HashSet<City>(100);
+ Set<City> hits = new HashSet<>(100);
for (int i = minLatIndex; i <= maxLatIndex; i++) {
City city = citiesByLat[i];
=====================================
src/uk/me/parabola/splitter/solver/AreasCalculator.java
=====================================
@@ -205,14 +205,16 @@ public class AreasCalculator {
*/
public List<Area> calcAreas () {
Area roundedBounds = RoundingUtils.round(exactArea, mainOptions.getResolution());
- SplittableDensityArea splittableArea = pass1Collector.getSplitArea(mainOptions.getSearchLimit(), roundedBounds);
+ DensityMap densityMap = pass1Collector.getDensityMap();
+ boolean trim = !mainOptions.isNoTrim();
+ SplittableDensityArea splittableArea = new SplittableDensityArea(densityMap.subset(roundedBounds), mainOptions.getSearchLimit(), trim);
+ pass1Collector.getDensityMap().clear();
if (splittableArea.hasData() == false) {
System.out.println("input file(s) have no data inside calculated bounding box");
return Collections.emptyList();
}
System.out.println("Rounded map coverage is " + splittableArea.getBounds());
- splittableArea.setTrim(mainOptions.isNoTrim() == false);
splittableArea.setMapId(mainOptions.getMapid());
long startSplit = System.currentTimeMillis();
List<Area> areas;
=====================================
src/uk/me/parabola/splitter/solver/DensityMap.java
=====================================
@@ -42,7 +42,7 @@ import uk.me.parabola.splitter.Utils;
public class DensityMap {
private static final int SEA_NODE_FACTOR = 2;
private final int width, height, shift;
- private final int[][] nodeMap;
+ private int[][] nodeMap;
private Area bounds;
private long totalNodeCount;
@@ -52,7 +52,7 @@ public class DensityMap {
* @param resolution the resolution of the density map. This must be a value between 1 and 24.
*/
public DensityMap(Area area, int resolution) {
- assert resolution >=1 && resolution <= 24;
+ assert resolution >= 1 && resolution <= 24;
shift = 24 - resolution;
bounds = RoundingUtils.round(area, resolution);
@@ -69,7 +69,7 @@ public class DensityMap {
if (polygonArea == null)
return null;
java.awt.geom.Area simpleArea = new java.awt.geom.Area();
- if (polygonArea.intersects(Utils.area2Rectangle(bounds, 0)) == false)
+ if (!polygonArea.intersects(Utils.area2Rectangle(bounds, 0)))
return simpleArea;
int gridElemWidth = bounds.getWidth() / width;
int gridElemHeight = bounds.getHeight() / height;
@@ -90,25 +90,24 @@ public class DensityMap {
int firstY = -1;
for (int y = 0; y < height; y++) {
int lat = yToLat(y);
- if (y < minY || y > maxY
- || polygonArea.intersects(lon, lat, gridElemWidth, gridElemHeight) == false){
- if (firstY >= 0){
- simpleArea.add(new java.awt.geom.Area(new Rectangle(x,firstY,1,y-firstY)));
- firstY = -1;
+ if (y < minY || y > maxY || !polygonArea.intersects(lon, lat, gridElemWidth, gridElemHeight)) {
+ if (firstY >= 0) {
+ simpleArea.add(new java.awt.geom.Area(new Rectangle(x, firstY, 1, y - firstY)));
+ firstY = -1;
}
} else {
if (firstY < 0)
- firstY = y;
+ firstY = y;
}
}
if (firstY >= 0){
- simpleArea.add(new java.awt.geom.Area(new Rectangle(x,firstY,1,height-firstY)));
+ 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");
+ System.out.println("Warning: Rastered polygon area contains holes, polygon is probably concave, trying to fix this");
simpleArea.reset();
shapes.forEach(s -> simpleArea.add(Utils.shapeToArea(s)));
}
@@ -157,21 +156,6 @@ public class DensityMap {
return nodeMap[x] != null ? nodeMap[x][y] : 0;
}
- 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];
- if (count > 0) {
- if (yxMap[y] == null)
- yxMap[y] = new int[width];
- yxMap[y][x] = count;
- }
- }
- }
- return yxMap;
- }
-
public DensityMap subset(final Area subsetBounds) {
int minLat = Math.max(bounds.getMinLat(), subsetBounds.getMinLat());
int minLon = Math.max(bounds.getMinLong(), subsetBounds.getMinLong());
@@ -244,7 +228,6 @@ public class DensityMap {
f.write(collectorBounds.getMinLat() + "," + collectorBounds.getMinLong() + "," + collectorBounds.getMaxLat() + "," + collectorBounds.getMaxLong() + '\n');
else
f.write("no_bounds_in_input\n");
- //f.write(bounds.getMinLat() + "," + bounds.getMinLong() + "," + bounds.getMaxLat() + "," + bounds.getMaxLong() + '\n');
for (int x=0; x<width; x++){
if (nodeMap[x] != null){
for (int y=0; y<height; y++){
@@ -282,9 +265,8 @@ public class DensityMap {
inLine = problemReader.readLine();
if (inLine != null){
items = csvSplitter.split(inLine);
- if (items.length != 4){
- System.out.println("Error: Invalid format in map file, line number " + problemReader.getLineNumber() + ": "
- + inLine);
+ if (items.length != 4) {
+ reportErrorLine(problemReader.getLineNumber(), inLine);
return null;
}
details.addToBounds(Integer.parseInt(items[0]), Integer.parseInt(items[1]));
@@ -294,8 +276,7 @@ public class DensityMap {
if (inLine != null && !"no_bounds_in_input".equals(inLine)) {
items = csvSplitter.split(inLine);
if (items.length != 4) {
- System.out.println("Error: Invalid format in map file, line number " + problemReader.getLineNumber()
- + ": " + inLine);
+ reportErrorLine(problemReader.getLineNumber(), inLine);
return null;
}
collectorBounds = new Area(Integer.parseInt(items[0]), Integer.parseInt(items[1]),
@@ -304,22 +285,20 @@ public class DensityMap {
while ((inLine = problemReader.readLine()) != null) {
items = csvSplitter.split(inLine);
if (items.length != 3) {
- System.out.println("Error: Invalid format in map file, line number " + problemReader.getLineNumber() + ": "
- + inLine);
+ reportErrorLine(problemReader.getLineNumber(), inLine);
return null;
}
int x,y,sum;
- try{
+ try {
x = Integer.parseInt(items[0]);
y = Integer.parseInt(items[1]);
sum = Integer.parseInt(items[2]);
- if (x < 0 || x >= width || y < 0 || y>=height){
- System.out.println("Error: Invalid data in map file, line number " + + problemReader.getLineNumber() + ": "
- + inLine);
+ if (x < 0 || x >= width || y < 0 || y >= height) {
+ System.out.println("Error: Invalid data in map file, line number "
+ + problemReader.getLineNumber() + ": " + inLine);
- }
- else{
+ } else {
if (nodeMap[x] == null)
nodeMap[x] = new int[height];
nodeMap[x][y] = sum;
@@ -339,6 +318,10 @@ public class DensityMap {
return collectorBounds;
}
+ private static void reportErrorLine(int lineNo, String inLine) {
+ System.out.println("Error: Invalid format in map file, line number " + lineNo + ": " + inLine);
+ }
+
public Area getArea(int x, int y, int width2, int height2) {
assert x >= 0;
assert y >= 0;
@@ -355,8 +338,7 @@ public class DensityMap {
*/
public void mergeSeaData(DensityMap seaData, Area area, boolean trim) {
if (this.shift != seaData.shift
- || Utils.area2Rectangle(bounds, 0).equals(
- Utils.area2Rectangle(seaData.getBounds(), 0)) == false) {
+ || !Utils.area2Rectangle(bounds, 0).equals(Utils.area2Rectangle(seaData.getBounds(), 0))) {
throw new SplitFailedException("cannot merge density maps");
}
if (trim && totalNodeCount == 0)
@@ -369,69 +351,47 @@ public class DensityMap {
maxX = width - 1;
if (maxY >= height)
maxY = height - 1;
- if (trim){
- for (int x = minX; x <= width; x++) {
- if (nodeMap[x] != null){
- minX = x;
- break;
- }
- }
- for (int x = maxX; x >= 0; x--) {
- if (nodeMap[x] != null){
- maxX = x;
- break;
- }
- }
- boolean done = false;
- for (int y = minY; y < height; y++) {
- for (int x = minX; x < width; x++) {
- if (nodeMap[x] == null)
- continue;
- if (nodeMap[x][y] > 0){
- minY = y;
- done = true;
- break;
- }
- }
- if (done)
- break;
- }
- done = false;
- for (int y = maxY; y >= 0; y--) {
- for (int x = minX; x < width; x++) {
- if (nodeMap[x] == null)
- continue;
-
- if (nodeMap[x][y] > 0){
- maxY = y;
- done = true;
- break;
- }
- }
- if (done)
- break;
- }
+ if (trim) {
+ while (minX < width && nodeMap[minX] == null)
+ minX++;
+ while (maxX > 0 && nodeMap[maxX] == null)
+ maxX--;
+ while (minY < height && rowAllZero(minY, minX, maxX))
+ minY++;
+ while (maxY > 0 && rowAllZero(maxY, minX, maxX))
+ maxY--;
}
long addedSeaNodes = 0;
- for (int x = minX; x <= maxX; x++){
+ for (int x = minX; x <= maxX; x++) {
int[] seaCol = seaData.nodeMap[x];
if (seaCol == null)
continue;
int[] col = nodeMap[x];
if (col == null)
- col = new int[height+1];
- for (int y = minY; y <= maxY; y++){
- if (col[y] == 0){
+ col = new int[height + 1];
+ for (int y = minY; y <= maxY; y++) {
+ if (col[y] == 0) {
int seaCount = seaCol[y] * SEA_NODE_FACTOR;
- if (seaCount > 0){
- col[y] = seaCount;
- totalNodeCount += seaCount;
- addedSeaNodes += seaCount;
- }
+ col[y] = seaCount;
+ totalNodeCount += seaCount;
+ addedSeaNodes += seaCount;
}
}
}
System.out.println("Added " + addedSeaNodes + " nodes from precompiled sea data.");
}
+
+ boolean rowAllZero(int row, int minX, int maxX) {
+ for (int x = minX; x <= maxX; x++) {
+ if (nodeMap[x] != null && nodeMap[x][row] > 0) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ public void clear() {
+ nodeMap = null;
+ }
}
=====================================
src/uk/me/parabola/splitter/solver/DensityMapCollector.java
=====================================
@@ -94,10 +94,6 @@ class DensityMapCollector extends AbstractMapProcessor{
return details.getBounds();
}
- public SplittableDensityArea getSplitArea(int searchLimit, Area roundedBounds) {
- return new SplittableDensityArea(densityMap.subset(roundedBounds), searchLimit);
- }
-
public void mergeSeaData(DensityMapCollector seaData, boolean trim, int resolution) {
Area roundedBounds = RoundingUtils.round(getExactArea(), resolution);
densityMap.mergeSeaData(seaData.densityMap, roundedBounds, trim);
@@ -111,4 +107,8 @@ class DensityMapCollector extends AbstractMapProcessor{
bounds = densityMap.readMap(fileName, details);
}
+ public DensityMap getDensityMap() {
+ return densityMap;
+ }
+
}
=====================================
src/uk/me/parabola/splitter/solver/EnhancedDensityMap.java
=====================================
@@ -30,7 +30,7 @@ public class EnhancedDensityMap {
private final DensityMap densityMap;
private int[][] xyMap;
private int[][] yxMap;
- private BitSet xyInPolygon;
+ private BitSet xyOutsidePolygon = new BitSet();
private double[] aspectRatioFactor;
private int minAspectRatioFactorPos;
private int maxNodesInDensityMapGridElement = Integer.MIN_VALUE;
@@ -41,113 +41,128 @@ public class EnhancedDensityMap {
this.densityMap = densities;
this.polygonArea = polygonArea;
prepare();
+ densityMap.clear();
}
-
/**
* If a polygon is given, filter the density data Compute once complex
* trigonometric results for needed for proper aspect ratio calculations.
*
*/
- private void prepare(){
+ private void prepare() {
// performance: calculate only once the needed complex math results
- aspectRatioFactor = new double[densityMap.getHeight()+1];
- int minLat = densityMap.getBounds().getMinLat();
+ aspectRatioFactor = new double[densityMap.getHeight() + 1];
+ int minLat = densityMap.getBounds().getMinLat();
int maxLat = densityMap.getBounds().getMaxLat();
int lat = 0;
double maxAspectRatioFactor = Double.MIN_VALUE;
int minPos = Integer.MAX_VALUE;
- for (int i = 0; i < aspectRatioFactor.length; i++ ){
+ for (int i = 0; i < aspectRatioFactor.length; i++) {
lat = minLat + i * (1 << densityMap.getShift());
assert lat <= maxLat;
- aspectRatioFactor[i] = Math.cos(Math.toRadians(Utils.toDegrees(lat))) ;
- if (maxAspectRatioFactor < aspectRatioFactor[i]){
+ aspectRatioFactor[i] = Math.cos(Math.toRadians(Utils.toDegrees(lat)));
+ if (maxAspectRatioFactor < aspectRatioFactor[i]) {
maxAspectRatioFactor = aspectRatioFactor[i];
minPos = i;
}
}
minAspectRatioFactorPos = minPos;
assert lat == maxLat;
-
- // filter the density map and populate xyMap
+
+ // filter the density map and populate xyMap
int width = densityMap.getWidth();
int height = densityMap.getHeight();
- xyMap = new int [width][height];
- if (polygonArea != null)
- xyInPolygon = new BitSet(width * height);
+ xyMap = new int[width][];
int shift = densityMap.getShift();
- for (int x = 0; x < width; x++){
- int polyXPos = densityMap.getBounds().getMinLong() + (x << shift);
- int[] xCol = xyMap[x];
- for(int y = 0; y < height; y++){
+ for (int x = 0; x < width; x++) {
+ int polyXPos = densityMap.getBounds().getMinLong() + (x << shift);
+ int[] xCol = null;
+ xCol = new int[height];
+ boolean colNeeded = false;
+ for (int y = 0; y < height; y++) {
int count = densityMap.getNodeCount(x, y);
- if (polygonArea != null){
+ if (polygonArea != null) {
int polyYPos = densityMap.getBounds().getMinLat() + (y << shift);
- if (polygonArea.intersects(polyXPos, polyYPos, 1<<shift, 1<<shift)){
- xyInPolygon.set(x * height + y);
- if (count > maxNodesInDensityMapGridElementInPoly){
- maxNodesInDensityMapGridElementInPoly = count;
- }
+ if (polygonArea.intersects(polyXPos, polyYPos, 1 << shift, 1 << shift)) {
+ maxNodesInDensityMapGridElementInPoly = Math.max(count, maxNodesInDensityMapGridElementInPoly);
+ } else {
+ xyOutsidePolygon.set(x * height + y);
}
}
- if (count > 0){
- if (count > maxNodesInDensityMapGridElement)
- maxNodesInDensityMapGridElement = count;
-
+ if (count > 0) {
+ maxNodesInDensityMapGridElement = Math.max(count, maxNodesInDensityMapGridElement);
xCol[y] = count;
+ colNeeded = true;
}
}
+ if (colNeeded)
+ xyMap[x] = xCol;
}
+
// create and populate yxMap, this helps to speed up row access
- yxMap = new int [height][width];
- for(int y = 0; y < height; y++){
- int[] yRow = yxMap[y];
- for (int x = 0; x < width; x++){
- yRow[x] = xyMap[x][y];
+ yxMap = new int[height][];
+ for (int y = 0; y < height; y++) {
+ boolean rowNeeded = false;
+ int[] yRow = new int[width];
+ for (int x = 0; x < width; x++) {
+ int count = 0;
+ if (xyMap[x] != null)
+ count = xyMap[x][y];
+ if (count > 0) {
+ rowNeeded = true;
+ yRow[x] = count;
+ }
}
+ if (rowNeeded)
+ yxMap[y] = yRow;
}
}
- public boolean isGridElemInPolygon (int x, int y){
- if (polygonArea == null)
+ public boolean isGridElemInPolygon(int x, int y) {
+ if (polygonArea == null || xyOutsidePolygon.isEmpty())
return true;
- return xyInPolygon.get(x* densityMap.getHeight() + y);
+ return !xyOutsidePolygon.get(x * densityMap.getHeight() + y);
}
-
+
// calculate aspect ratio of a tile which is a view on the densityMap
public double getAspectRatio(Rectangle r) {
double ratio;
- double maxWidth ;
- if (r.y < minAspectRatioFactorPos && r.y+r.height > minAspectRatioFactorPos){
+ double maxWidth;
+ if (r.y < minAspectRatioFactorPos && r.y + r.height > minAspectRatioFactorPos) {
maxWidth = r.width; // tile crosses equator
- }else {
+ } else {
double width1 = r.width * aspectRatioFactor[r.y];
double width2 = r.width * aspectRatioFactor[r.y + r.height];
- maxWidth = Math.max(width1, width2);
+ maxWidth = Math.max(width1, width2);
}
- ratio = maxWidth/r.height;
+ ratio = maxWidth / r.height;
return ratio;
}
-
+
public Area getBounds() {
return densityMap.getBounds();
}
+
public DensityMap getDensityMap() {
return densityMap;
}
-
- public long getNodeCount(){
+
+ public long getNodeCount() {
return densityMap.getNodeCount();
}
+
public int[] getMapRow(int mapRow) {
return yxMap[mapRow];
}
+
public int[] getMapCol(int mapCol) {
return xyMap[mapCol];
}
+
public double[] getAspectRatioFactor() {
return aspectRatioFactor;
}
+
public int getMinAspectRatioFactorPos() {
return minAspectRatioFactorPos;
}
@@ -163,5 +178,9 @@ public class EnhancedDensityMap {
public java.awt.geom.Area getPolygonArea() {
return polygonArea;
}
+
+ public boolean allInsidePolygon() {
+ return polygonArea == null || xyOutsidePolygon.isEmpty();
+ }
}
=====================================
src/uk/me/parabola/splitter/solver/Solution.java
=====================================
@@ -31,6 +31,7 @@ public class Solution {
private final List<Tile> tiles;
private final long maxNodes;
private double worstAspectRatio = -1;
+ private int numLowCount;
private long worstMinNodes = Long.MAX_VALUE;
public Solution(long maxNodes) {
@@ -40,8 +41,7 @@ public class Solution {
public Solution copy() {
Solution s = new Solution(this.maxNodes);
- for (Tile t : tiles)
- s.add(t);
+ tiles.forEach(s::add);
return s;
}
@@ -51,7 +51,9 @@ public class Solution {
if (aspectRatio < 1.0)
aspectRatio = 1.0 / aspectRatio;
worstAspectRatio = Math.max(aspectRatio, worstAspectRatio);
- worstMinNodes = Math.min(tile.getCount(), worstMinNodes);
+ worstMinNodes = Math.min(tile.getCount(), worstMinNodes);
+ if (tile.getCount() < maxNodes / 3)
+ numLowCount++;
return true;
}
@@ -72,6 +74,7 @@ public class Solution {
if (worstMinNodes > other.worstMinNodes)
worstMinNodes = other.worstMinNodes;
}
+ numLowCount += other.numLowCount;
tiles.addAll(other.tiles);
}
@@ -107,8 +110,9 @@ public class Solution {
return 0;
if (isEmpty() != other.isEmpty())
return isEmpty() ? 1 : -1;
- if (isNice() != other.isNice())
- return isNice() ? -1 : 1;
+ int d = Boolean.compare(isNice(), other.isNice());
+ if (d != 0)
+ return -d; // prefer this if nice
if (worstMinNodes != other.worstMinNodes) {
// ignore minNodes when both are bad
@@ -247,28 +251,43 @@ public class Solution {
/**
* A solution is considered to be nice when aspect
* ratios are not extreme and every tile is filled
- * with at least 33% of the max-nodes value.
+ * with at least 33% of the max-nodes value or almost all tiles are filled much better.
* @return
*/
public boolean isNice() {
- if (isEmpty())
- return false;
- if (worstAspectRatio > SplittableDensityArea.NICE_MAX_ASPECT_RATIO)
+ if (isEmpty() || worstAspectRatio > SplittableDensityArea.NICE_MAX_ASPECT_RATIO)
return false;
- if (tiles.size() == 1)
+ final long low = maxNodes / 3;
+ if (tiles.size() == 1 || worstMinNodes >= low || (numLowCount <= 2 && tiles.size() > 20)
+ || (numLowCount == 1 && tiles.size() > 4))
return true;
- if (worstMinNodes < maxNodes / 3)
- return false;
- return true;
+ double lowRatio = 100.0 * numLowCount / tiles.size();
+ return lowRatio < 3; // less then 3 percent of the tiles are not well filled
}
@Override
public String toString() {
- double ratio = (double) Math.round(worstAspectRatio * 100) / 100;
- long percentage = 100 * worstMinNodes / maxNodes;
if (isEmpty())
return "is empty";
- return tiles.size() + " tile(s). The smallest node count is " + worstMinNodes + " (" + percentage + " %), the worst aspect ratio is near " + ratio;
+ long percentage = 100 * worstMinNodes / maxNodes;
+ return tiles.size() + " tile(s). The smallest node count is " + worstMinNodes + " (" + percentage + " %)";
}
+
+ /**
+ * Returns true if this solution is smaller or better than the other.
+ * @param other the other solution
+ * @return true if this solution is smaller or better than the other
+ */
+ public boolean isSmallerOrBetter(Solution other) {
+ if (isEmpty())
+ return false;
+ if (other == null || other.isEmpty() && !isEmpty())
+ return true;
+ if (other.size() > this.size())
+ return true;
+ if (other.size() == this.size())
+ return compareTo(other) < 0;
+ return false;
+ }
}
=====================================
src/uk/me/parabola/splitter/solver/SplittableDensityArea.java
=====================================
@@ -15,12 +15,20 @@ package uk.me.parabola.splitter.solver;
import java.awt.Point;
import java.awt.Rectangle;
+import java.time.Duration;
+import java.time.Instant;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
-import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
+import java.util.Map;
+import java.util.Optional;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Executors;
+import java.util.concurrent.Future;
import it.unimi.dsi.fastutil.ints.IntArrayList;
import uk.me.parabola.splitter.Area;
@@ -39,50 +47,39 @@ public class SplittableDensityArea {
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;
+ static final int AXIS_HOR = 0;
+ 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 double VERY_NICE_FILL_RATIO = 0.94;
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 static final double MAX_OUTSIDE_RATIO = 0.5;
+ private static final int MIN_TILE_AREA_BAD_CACHE = 100;
+ private static final int MAX_DEPTH_STATS = 10;
+ private boolean enableExtraOpt = true; // option ?
+
private final int startSearchLimit;
- private int searchLimit;
- private double maxOutsidePolygonRatio = 0.5; // TODO: maybe reduce it when a good solution was found
+
private final DensityMap allDensities;
private EnhancedDensityMap extraDensityInfo;
- private boolean beQuiet = false;
+ private boolean beQuiet;
+ private static final boolean DEBUG = false;
private long maxNodes;
+ private int stopNumber;
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 boolean trimShape;
+
+ private final boolean trimShape;
private boolean trimTiles;
- private boolean allowEmptyPart = false;
+ private boolean allowEmptyPart;
private int currMapId;
private boolean hasEmptyPart;
- private boolean ignoreSize;
+ private int solverId;
- public SplittableDensityArea(DensityMap densities, int startSearchLimit) {
+ public SplittableDensityArea(DensityMap densities, int startSearchLimit, boolean trim) {
this.shift = densities.getShift();
- this.searchLimit = this.startSearchLimit = startSearchLimit;
- maxTileHeight = Utils.toMapUnit(MAX_LAT_DEGREES) / (1 << shift);
- maxTileWidth = Utils.toMapUnit(MAX_LON_DEGREES) / (1 << shift);
+ this.startSearchLimit = startSearchLimit;
+ this.trimShape = trim;
allDensities = densities;
}
@@ -98,10 +95,6 @@ public class SplittableDensityArea {
this.maxNodes = maxNodes;
}
- public void setTrim(boolean trim) {
- this.trimShape = trim;
- }
-
public boolean hasData() {
return allDensities != null && allDensities.getNodeCount() > 0;
}
@@ -114,15 +107,14 @@ public class SplittableDensityArea {
}
/**
- * Create the list of areas.
+ * Calculate a solution (list of areas that either matches the given criteria or is empty)
*
- * @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.
+ * @return solution (can be empty if none was found with the given criteria)
*/
- private List<Area> split() {
+ private Solution split() {
+ Solution fullSolution = new Solution(maxNodes);
if (allDensities == null || allDensities.getNodeCount() == 0)
- return Collections.emptyList();
+ return fullSolution;
prepare(null);
Tile startTile = new Tile(extraDensityInfo);
List<Tile> startTiles = new ArrayList<>();
@@ -134,12 +126,11 @@ public class SplittableDensityArea {
startTiles.add(startTile);
}
- Solution fullSolution = new Solution(maxNodes);
int countNoSol;
while (true) {
countNoSol = 0;
for (Tile tile : startTiles) {
- hasEmptyPart = false;
+ hasEmptyPart = false; // possibly overwritten in solveRectangularArea
if (!beQuiet)
System.out.println("Solving partition " + tile.toString());
Solution solution = solveRectangularArea(tile);
@@ -158,12 +149,12 @@ public class SplittableDensityArea {
allowEmptyPart = true;
fullSolution = new Solution(maxNodes);
}
- if (countNoSol > 0)
+ if (countNoSol > 0 && stopNumber == 0)
throw new SplitFailedException("Failed to find a correct split");
- System.out.println("Final solution: " + fullSolution.toString());
- if (fullSolution.isNice())
- System.out.println("This seems to be nice.");
- return getAreas(fullSolution, null);
+ if (!beQuiet) {
+ printFinalSplitMsg(fullSolution);
+ }
+ return fullSolution;
}
/**
@@ -175,7 +166,7 @@ public class SplittableDensityArea {
*/
private List<Area> split(java.awt.geom.Area polygonArea) {
if (polygonArea == null)
- return split();
+ return getAreas(split(), null);
if (polygonArea.isSingular()) {
java.awt.geom.Area rasteredArea = allDensities.rasterPolygon(polygonArea);
if (rasteredArea.isEmpty()) {
@@ -186,8 +177,8 @@ public class SplittableDensityArea {
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 && rasteredArea.isRectangular())
+ solution = split();
if (solution != null) {
return getAreas(solution, polygonArea);
}
@@ -203,12 +194,13 @@ 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 namedPolygons
+ * @param namedPolygons list of polygons, if empty the tile bounds are used
* @return list of areas
*/
public List<Area> split(List<PolygonDesc> namedPolygons) {
- if (namedPolygons.isEmpty())
- return split();
+ if (namedPolygons.isEmpty()) {
+ return getAreas(split(), null);
+ }
List<Area> result = new ArrayList<>();
class ShareInfo {
java.awt.geom.Area area;
@@ -281,57 +273,58 @@ 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 into a given number of tiles.
*
* @param wantedTiles
* @return list of areas
*/
public List<Area> split(int wantedTiles) {
- long currMaxNodes = this.allDensities.getNodeCount() / wantedTiles;
+ this.stopNumber = wantedTiles;
+ long currMaxNodes = (long) (this.allDensities.getNodeCount() / (wantedTiles * 0.95));
class Pair {
- long maxNodes;
+ long myMaxNodes;
int numTiles;
Pair(long maxNodes, int numTiles) {
- this.maxNodes = maxNodes;
+ this.myMaxNodes = maxNodes;
this.numTiles = numTiles;
}
}
Pair bestBelow = null;
Pair bestAbove = null;
beQuiet = true;
- ignoreSize = true;
while (true) {
- setMaxNodes(currMaxNodes);
+ this.setMaxNodes(currMaxNodes);
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) {
+ Solution sol = split();
+
+ if (sol.isEmpty() || sol.size() == wantedTiles) {
beQuiet = false;
- res = split();
- return res;
+ printFinalSplitMsg(sol);
+ return getAreas(sol, null);
}
- goodSolutions = new HashMap<>(GOOD_SOL_INIT_SIZE);
- Pair pair = new Pair(currMaxNodes, res.size());
- if (res.size() > wantedTiles) {
+
+ Pair pair = new Pair(currMaxNodes, sol.size());
+ if (sol.size() > wantedTiles) {
if (bestAbove == null || bestAbove.numTiles > pair.numTiles
- || (bestAbove.numTiles == pair.numTiles && pair.maxNodes < bestAbove.maxNodes))
+ || (bestAbove.numTiles == pair.numTiles && pair.myMaxNodes < bestAbove.myMaxNodes))
bestAbove = pair;
} else {
if (bestBelow == null || bestBelow.numTiles < pair.numTiles
- || (bestBelow.numTiles == pair.numTiles && pair.maxNodes > bestBelow.maxNodes))
+ || (bestBelow.numTiles == pair.numTiles && pair.myMaxNodes > bestBelow.myMaxNodes))
bestBelow = pair;
}
long testMaxNodes;
if (bestBelow == null || bestAbove == null)
- testMaxNodes = Math.min(Math.round((double) currMaxNodes * res.size() / wantedTiles),
+ testMaxNodes = Math.min(Math.round((double) currMaxNodes * sol.size() / wantedTiles),
this.allDensities.getNodeCount() - 1);
else
- testMaxNodes = (bestBelow.maxNodes + bestAbove.maxNodes) / 2;
+ testMaxNodes = (bestBelow.myMaxNodes + bestAbove.myMaxNodes) / 2;
if (testMaxNodes == currMaxNodes) {
System.err.println("Cannot find a good split with exactly " + wantedTiles + " areas");
- return res;
+ printFinalSplitMsg(sol);
+ return getAreas(sol, null);
}
currMaxNodes = testMaxNodes;
}
@@ -357,50 +350,6 @@ public class SplittableDensityArea {
}
- /**
- * 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
- */
- 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);
- }
- }
-
- /**
- * 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) {
- if (best == null || best.isEmpty())
- return;
- goodSolutions.entrySet().removeIf(entry -> entry.getValue().getWorstMinNodes() <= best.getWorstMinNodes());
- goodRatio = Math.max(0.5, (double) best.getWorstMinNodes() / maxNodes);
- }
-
- /**
- * 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) {
- Solution sol = goodSolutions.get(tile);
- 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.
@@ -505,7 +454,7 @@ public class SplittableDensityArea {
int resolution = 24 - allDensities.getShift();
shapeBounds = RoundingUtils.round(shapeBounds, resolution);
SplittableDensityArea splittableArea = new SplittableDensityArea(allDensities.subset(shapeBounds),
- startSearchLimit);
+ startSearchLimit, trimShape);
splittableArea.setMaxNodes(maxNodes);
if (!splittableArea.hasData()) {
System.out.println(
@@ -543,7 +492,7 @@ public class SplittableDensityArea {
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");
+ System.out.println("Warning: rastered shape is too complex, using rectangle " + part + " instead");
return solveRectangularArea(part);
}
@@ -595,165 +544,90 @@ public class SplittableDensityArea {
return new Solution(maxNodes);
}
+ private Solution solveRectangularArea(Tile startTile) {
+ int bestPossible = stopNumber > 0 ? stopNumber : startTile.getMinParts(maxNodes);
+ System.out.println("Splitting tile " + startTile + ", goal is to get near " + bestPossible + " tiles");
+ return solveRectangularAreaParallel(startTile, 0);
+ }
+
/**
- * Try to split the tile into nice parts recursively.
- *
- * @param depth the recursion depth
- * @param tile the tile to be split
- * @param smiParent meta info for parent tile
- * @return a solution instance or null
+ * Split large tile into smaller parts with a simple split and solve the small parts using parallel stream.
+ * @param startTile the tile to split
+ * @param depth recursion depth
+ * @return solution
*/
- private Solution findSolution(int depth, final Tile tile, Tile parent, TileMetaInfo smiParent) {
- boolean addAndReturn = false;
- if (tile.getCount() == 0) {
- if (!allowEmptyPart) {
- hasEmptyPart = true;
- return null;
- }
- 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
- } else if (tile.getCount() < minNodes && depth == 0) {
- addAndReturn = true; // nothing to do
- } else if (tile.getCount() < minNodes) {
- return null;
- } else if (tile.getCount() <= maxNodes) {
- double ratio = tile.getAspectRatio();
- if (ratio < 1.0)
- ratio = 1.0 / ratio;
- if (ratio <= maxAspectRatio) {
- if (ignoreSize || maxNodes >= LARGE_MAX_NODES || checkSize(tile))
- addAndReturn = true;
- }
- } else if (tile.width < 2 && tile.height < 2) {
- return null;
- }
- if (addAndReturn) {
- double outsidePolygonRatio = tile.calcOutsidePolygonRatio();
- if (outsidePolygonRatio > maxOutsidePolygonRatio) {
- return null;
- }
- Solution solution = new Solution(maxNodes);
- solution.add(tile); // can't split further
- return solution;
- }
- if (tile.getCount() < minNodes * 2) {
- return null;
- }
- Solution cached = searchGoodSolutions(tile);
- if (cached != null) {
- return cached;
- }
- // we have to split the tile
- Integer alreadyDone = null;
- if (countBad == 0 && incomplete.size() > 0) {
- alreadyDone = incomplete.remove(tile);
- if (alreadyDone == null)
- incomplete.clear(); // rest is not useful
- }
+ private Solution solveRectangularAreaParallel(Tile startTile, int depth) {
+ if (depth == 0 && (stopNumber > 0 || startTile.getCount() < 256 * maxNodes))
+ return solveRectangularAreaOne(startTile);
- if (alreadyDone == null && depth > 0 && tile.width * tile.height > 100) {
- if (knownBad.contains(tile))
- return null;
+ Solution res = new Solution(maxNodes);
+ long partSize = 64 * maxNodes;
+ if (depth > 0) {
+ partSize = Math.max(1, startTile.getCount() - 1);
}
+ List<Tile> todo = startTile.divide(partSize);
+ System.out.println("Initial simple split returned " + todo.size() + " tile(s)");
+ List<Solver> solvers = new ArrayList<>();
+ List<Area> initialAreas = new ArrayList<>();
- // 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;
-
- IntArrayList todoList = generateTestCases(axis, tile, smi);
- int countAxis = 0;
- int usedTestPos = 0;
- int countDone = 0;
- Solution bestSol = null;
- while (true) {
- if (usedTestPos >= todoList.size()) {
- countAxis++;
- if (countAxis > 1)
- break;
- axis = axis == AXIS_HOR ? AXIS_VERT : AXIS_HOR;
- todoList = generateTestCases(axis, tile, smi);
- usedTestPos = 0;
- continue;
- }
- countDone++;
- 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
- boolean ok = false;
- if (axis == AXIS_HOR) {
- ok = tile.splitHoriz(splitPos, smi);
- } else {
- ok = tile.splitVert(splitPos, smi);
- }
- if (!ok)
+ for (Tile t : todo) {
+ if (t.outsidePolygon())
continue;
+ if (trimTiles)
+ t = t.trim();
+ int areaSize = t.width * t.height;
+ boolean useSearchAll = areaSize < 32_000 || t.getCount() < 16 * maxNodes;
+ boolean anyOutside = t.countElemsOutside() > 0;
+ Solver solver = new Solver(++solverId, useSearchAll, maxNodes, t, shift, 0, trimTiles, startSearchLimit, allowEmptyPart);
+ solver.maxAspectRatio = getStartRatio(startTile);
+
+ System.out.println("Using " + solver.toString() + " on " + Utils.format(areaSize) + " grid elements"
+ + (trimTiles && anyOutside ? ", trim needed" : ", trim not needed"));
+
+ Rectangle r = t.getRealBBox();
+ Area area = new Area(r.y, r.x, (int) r.getMaxY(), (int) r.getMaxX());
+ area.setMapId(solverId);
+ initialAreas.add(area);
+// if (depth > 0 ||solver.name.startsWith("S19 "))
+ solvers.add(solver);
+ }
- Tile[] parts = smi.getParts();
- if (trimTiles) {
- parts[0] = parts[0].trim();
- parts[1] = parts[1].trim();
- }
- 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];
- int countOK = 0;
- for (int i = 0; i < 2; i++) {
- if (i == 0 && alreadyDone != null)
+ solvers.parallelStream().forEach(Solver::solve);
+ List<Solver> solvers2 = new ArrayList<>();
+ if (enableExtraOpt) {
+ for (int i = 0; i < solvers.size(); i++) {
+ Solver solver = solvers.get(i);
+ Solution s = solver.bestSolution;
+ int goal = solver.startTile.getMinParts(maxNodes);
+ int areaSize = solver.startTile.width * solver.startTile.height;
+ if (areaSize > 200_000)
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) {
- countBad++;
-// 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
-// System.out.println(".. " + depth + " with currX = " + currX + " and currY = "+ currY + " at tile " + tile + " bad: " + saveCountBad );
-// }
- break;
+ if (s.size() > 1 && (!s.isNice() || s.size() >= goal + 3)) {
+ System.out.println("trying to improve poor solution from " + solver);
+ Solver sv2 = new Solver(++solverId, !solver.searchAll, maxNodes, solver.startTile, shift, stopNumber, solver.trimTiles, startSearchLimit, allowEmptyPart);
+ System.out.println("Starting " + sv2.toString());
+ sv2.maxAspectRatio = getStartRatio(startTile);
+ solvers2.add(sv2);
}
- checkIfGood(parts[i], sols[i]);
- countOK++;
- }
- 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);
- break;
}
+
+ solvers2.parallelStream().forEach(Solver::solve);
}
-
- smi.propagateToParent(smiParent, tile, parent);
-
- if (bestSol == null && countBad < searchLimit && depth > 0 && tile.width * tile.height > 100) {
- knownBad.add(tile);
+ for (Solver sv : solvers) {
+ Solution sol = sv.bestSolution;
+ Optional<Solver> opt = solvers2.stream().filter(s2 -> sv.startTile.equals(s2.startTile)).findAny();
+ if (opt.isPresent()) {
+ Solution sol2 = opt.get().bestSolution;
+ if (sol2.isNice() && sol2.isSmallerOrBetter(sol)) {
+ System.out.println(opt.get().name + ": replaced solution from " + sv.name);
+ sol = sol2;
+ }
+ }
+ if (sol.isEmpty())
+ sol = solveRectangularAreaParallel(sv.startTile, depth + 1);
+ res.merge(sol);
}
- return bestSol;
- }
-
- private boolean checkSize(Tile tile) {
- return tile.height <= maxTileHeight && tile.width <= maxTileWidth;
+ return res;
}
/**
@@ -763,153 +637,134 @@ public class SplittableDensityArea {
* @param startTile the tile to split
* @return a solution (maybe be empty)
*/
- private Solution solveRectangularArea(Tile startTile) {
+ private Solution solveRectangularAreaOne(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;
- final long startMinNodes = Math.max(Math.min((long) (0.05 * maxNodes), extraDensityInfo.getNodeCount()), 1);
- minNodes = startMinNodes;
+ List<Solver> solvers = new ArrayList<>();
+ List<Future<?>> futures = new ArrayList<>();
+ int numAlgos = 2;
+ ExecutorService threadPool = Executors.newFixedThreadPool(numAlgos);
- if (extraDensityInfo.getNodeCount() / maxNodes < 4) {
- maxAspectRatio = 32;
- } else {
- maxAspectRatio = startTile.getAspectRatio();
- if (maxAspectRatio < 1)
- maxAspectRatio = 1 / maxAspectRatio;
- if (maxAspectRatio < NICE_MAX_ASPECT_RATIO)
- maxAspectRatio = NICE_MAX_ASPECT_RATIO;
- }
- goodSolutions = new HashMap<>(GOOD_SOL_INIT_SIZE);
- goodRatio = 0.5;
- TileMetaInfo smiStart = new TileMetaInfo(startTile, null, null);
- if (!ignoreSize && startTile.getCount() < 300 * maxNodes && (checkSize(startTile) || startTile.getCount() < 10 * maxNodes)) {
- searchAll = true;
+ for (int i = 0; i < numAlgos; i++) {
+ Solver solver = new Solver(++solverId, i == 1, maxNodes, startTile, shift, stopNumber, trimTiles, startSearchLimit, allowEmptyPart);
+ if (solver.searchAll && startTile.getCount() > 300 * maxNodes)
+ continue; // too complex for FULL
+ if (!solver.searchAll && stopNumber == 0 && startTile.getCount() < 10 * maxNodes)
+ continue; // too simple for SOME
+ solver.maxAspectRatio = getStartRatio(startTile);
+ solvers.add(solver);
+ futures.add(threadPool.submit(solver::solve));
}
- boolean algorithmnWasSwitched = false;
-
- if (!beQuiet)
- System.out.println("Trying to find nice split for " + startTile);
- Solution bestSolution = new Solution(maxNodes);
- long t1 = System.currentTimeMillis();
- incomplete = new LinkedHashMap<>();
- resetCaches();
- 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");
- }
- smiStart.setMinNodes(minNodes);
- solution = findSolution(0, startTile, startTile, smiStart);
- if (solution != null) {
- foundBetter = bestSolution.compareTo(solution) > 0;
- if (foundBetter) {
- Solution prevBest = bestSolution;
- bestSolution = solution;
- if (bestSolution.compareTo(firstSolution) < 0) {
- System.out.println("Best solution until now: " + bestSolution.toString() + ", elapsed search time: "
- + (System.currentTimeMillis() - t1) / 1000 + " s");
+
+ threadPool.shutdown();
+
+ Instant t1 = null;
+ final double n75 = 0.75 * maxNodes;
+ final double n85 = 0.85 * maxNodes;
+ while (!threadPool.isTerminated()) {
+ for (int i = 0; i < solvers.size(); i++) {
+ Future<?> future = futures.get(i);
+ if (future.isDone()) {
+ try {
+ future.get();
+ } catch (InterruptedException | ExecutionException e) {
+ throw new SplitFailedException("parallel solver crashed", e.getCause());
}
- filterGoodSolutions(bestSolution);
- // change criteria to find a better(nicer) result
- double factor = 1.10;
- 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 (!beQuiet)
- System.out.println("This can't be improved.");
- break;
- }
- } else {
- if (!bestSolution.isEmpty()) {
- if (minNodes > bestSolution.getWorstMinNodes() + 1) {
- // reduce minNodes
- minNodes = (bestSolution.getWorstMinNodes() + minNodes) / 2;
- if (minNodes < bestSolution.getWorstMinNodes() * 1.001)
- minNodes = bestSolution.getWorstMinNodes() + 1;
+ Solution sol = solvers.get(i).bestSolution;
+ if (sol.isNice()) {
+ if (t1 == null)
+ t1 = Instant.now();
+ long dt = Duration.between(t1, Instant.now()).getSeconds();
+ boolean stop = false;
+ if (sol.getWorstMinNodes() >= n85 && dt > 10) {
+ stop = true; // all tiles have at least 85% of max-nodes
+ } else {
+ int num75 = 0;
+ for (Tile tile : sol.getTiles()) {
+ if (tile.getCount() < n75)
+ num75++;
+ }
+ double below75 = 100.0 * num75 / sol.size();
+ if (below75 > 5 && dt > 30) {
+ // +5 percent of tiles are less the 75 percent but we waited +30 seconds
+ stop = true;
+ }
+ }
+ if (stop) {
+ // stop the other solver
+ solvers.forEach(Solver::stop);
+ }
}
}
}
- 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) {
- // 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) {
- minNodes = 1;
- resetCaches();
- searchLimit = startSearchLimit;
- // sanity check
- System.out.println("No good solution found, trying to find one accepting anything");
- int highestCount = extraDensityInfo.getMaxNodesInDensityMapGridElement();
- // inform user about possible better options?
- double ratio = (double) highestCount / maxNodes;
- if (ratio > 4)
- System.err.printf(
- "max-nodes value %d is far below highest node count %d in single grid element, consider using a higher resolution.%n",
- maxNodes, highestCount);
- else if (ratio > 1)
- System.err.printf(
- "max-nodes value %d is below highest node count %d in single grid element, consider using a higher resolution.%n",
- maxNodes, highestCount);
- else if (ratio < 0.25)
- System.err.printf(
- "max-nodes value %d is far above highest node count %d in single grid element, consider using a lower resolution.%n",
- maxNodes, highestCount);
-
- continue;
- }
- if (!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;
+ try {
+ Thread.sleep(500);
+ } catch (InterruptedException e) {
+ e.printStackTrace();
+ }
+ }
+ // call get() on each future to recognise possible exceptions
+ futures.forEach(f -> {
+ try {
+ f.get();
+ } catch (InterruptedException | ExecutionException e) {
+ Thread.currentThread().interrupt();
+ throw new SplitFailedException("parallel solver crashed", e.getCause());
}
+ });
+ // sort by number of tiles so that the smaller number comes first
+ // can't use compareTo here as it prefers the higher worstMinNodes value
+ solvers.sort((o1, o2) -> {
+ int d = Boolean.compare(o1.bestSolution.isNice(), o2.bestSolution.isNice());
+ if (d != 0)
+ return -d; // prefer nice
+ d = Integer.compare(o1.bestSolution.size(), o2.bestSolution.size());
+ if (d != 0)
+ return d;
+ // prefer higher min-nodes
+ return Long.compare(o2.bestSolution.getWorstMinNodes(), o1.bestSolution.getWorstMinNodes());
+ });
+ Solver best = solvers.get(0);
+ if (best.bestSolution.isEmpty()) {
+ int highestCount = extraDensityInfo.getMaxNodesInDensityMapGridElement();
+ // inform user about possible better options?
+ double ratio = (double) highestCount / maxNodes;
+ if (ratio > 4)
+ System.err.printf(
+ "max-nodes value %d is far below highest node count %d in single grid element, consider using a higher resolution.%n",
+ maxNodes, highestCount);
+ else if (ratio > 1)
+ System.err.printf(
+ "max-nodes value %d is below highest node count %d in single grid element, consider using a higher resolution.%n",
+ maxNodes, highestCount);
+ else if (ratio < 0.25)
+ System.err.printf(
+ "max-nodes value %d is far above highest node count %d in single grid element, consider using a lower resolution.%n",
+ maxNodes, highestCount);
+
+
}
- if (bestSolution.compareTo(firstSolution) > 0)
- bestSolution = firstSolution;
- if (!beQuiet)
- printFinishMsg(bestSolution);
- return bestSolution;
+ hasEmptyPart = best.hasEmptyPart;
+ printFinishMsg(best.bestSolution, best.searchLimit);
+ return best.bestSolution;
}
- private void resetCaches() {
- knownBad = new HashSet<>(50_000);
+ private double getStartRatio(Tile startTile) {
+ if (extraDensityInfo.getNodeCount() / maxNodes < 4) {
+ return 32;
+ }
+ double startMaxAspectRatio = startTile.getAspectRatio();
+ if (startMaxAspectRatio < 1)
+ startMaxAspectRatio = 1 / startMaxAspectRatio ;
+ if (startMaxAspectRatio < NICE_MAX_ASPECT_RATIO)
+ startMaxAspectRatio = NICE_MAX_ASPECT_RATIO;
+ return startMaxAspectRatio;
}
- private void printFinishMsg(Solution solution) {
+ private void printFinishMsg(Solution solution, int searchLimit) {
if (!beQuiet) {
if (!solution.isEmpty()) {
if (solution.getWorstMinNodes() > VERY_NICE_FILL_RATIO * maxNodes && solution.isNice())
@@ -923,6 +778,12 @@ public class SplittableDensityArea {
}
}
+ private static void printFinalSplitMsg(Solution solution) {
+ System.out.println("Final solution: " + solution.toString());
+ if (solution.isNice())
+ System.out.println("This seems to be nice.");
+ }
+
/**
* Convert the list of Tile instances of a solution to Area instances, report
* some statistics.
@@ -934,8 +795,8 @@ public class SplittableDensityArea {
*/
private List<Area> getAreas(Solution sol, java.awt.geom.Area polygonArea) {
List<Area> result = new ArrayList<>();
- int minLat = getAllDensities().getBounds().getMinLat();
- int minLon = getAllDensities().getBounds().getMinLong();
+ int minLat = allDensities.getBounds().getMinLat();
+ int minLon = allDensities.getBounds().getMinLong();
if (polygonArea != null) {
System.out.println("Trying to cut the areas so that they fit into the polygon ...");
@@ -982,82 +843,504 @@ 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 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) {
- return (axis == AXIS_HOR) ? tile.genXTests(smi) : tile.genYTests(smi);
+ private static class Solver {
+ private final long myMaxNodes;
+ private boolean hasEmptyPart;
+ private double maxAspectRatio;
+ private int countBad;
+ private Long minNodes;
+ private int searchLimit;
+ private LinkedHashMap<Tile, Integer> incomplete;
+ private Map<Tile, Long> knownBad = new HashMap<>(50_000);
+ static final int MAX_SEARCH_LIMIT = 5_000_000;
+ final String name;
+ private boolean searchAll;
+ private Solution bestSolution;
+ private Solution smallestSolution;
+ private boolean stopped;
+ private long localOptMinNodes;
+ private final Tile startTile;
+ private int bestPossible;
+ private long largestOptTileCount;
+ private int largestOptSize;
+ private long optLoops;
+ private int[] lastGoodCounts;
+ private final int maxTileHeight;
+ private final int maxTileWidth;
+ private final int stopNumber;
+ private final boolean trimTiles;
+ private final int startSearchLimit;
+ private final boolean allowEmptyPart;
+
+
+ public Solver(int id, boolean searchAll, long maxNodes, Tile startTile, int shift, int stopNumber,
+ boolean trimTiles, int startSearchLimit, boolean allowEmptyPart) {
+ this.searchAll = searchAll;
+ this.myMaxNodes = maxNodes;
+ this.startTile = startTile;
+ this.stopNumber = stopNumber;
+ this.trimTiles = trimTiles;
+ this.startSearchLimit = startSearchLimit;
+ this.allowEmptyPart = allowEmptyPart;
+ incomplete = new LinkedHashMap<>();
+ bestSolution = new Solution(myMaxNodes);
+ name = "S" + id + " " + (searchAll ? "FULL" : "SOME");
+ maxTileHeight = Utils.toMapUnit(MAX_LAT_DEGREES) / (1 << shift);
+ maxTileWidth = Utils.toMapUnit(MAX_LON_DEGREES) / (1 << shift);
}
- double ratio = tile.getAspectRatio();
- IntArrayList tests = new IntArrayList();
- if (ratio < 1.0 / 32 || ratio > 32 || ratio < 1.0 / 16 && axis == AXIS_HOR || ratio > 16 && axis == AXIS_VERT)
- return tests;
- 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) {
- // can't split tile without having one part that has too few nodes
- return tests;
+
+ /**
+ * Try to split the tile into nice parts recursively.
+ *
+ * @param depth the recursion depth
+ * @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) {
+ if (stopped)
+ return null;
+ boolean addAndReturn = false;
+ if (tile.getCount() == 0) {
+ if (!allowEmptyPart) {
+ hasEmptyPart = true;
+ return null;
+ }
+ if (tile.width * tile.height <= 4)
+ return null;
+ return new Solution(myMaxNodes); // allow empty part of the world
+ } else if (tile.getCount() > myMaxNodes && tile.width == 1 && tile.height == 1) {
+ addAndReturn = true; // can't split further
+ } else if (tile.getCount() < minNodes && depth == 0) {
+ addAndReturn = true; // nothing to do
+ } else if (tile.getCount() < minNodes) {
+ return null;
+ } else if (tile.getCount() <= myMaxNodes) {
+ double ratio = tile.getAspectRatio();
+ if (ratio < 1.0)
+ ratio = 1.0 / ratio;
+ if (ratio <= maxAspectRatio) {
+ if (stopNumber > 0 || myMaxNodes >= LARGE_MAX_NODES || checkSize(tile))
+ addAndReturn = true;
+ } else {
+ return null;
+ }
+ } else if (tile.width < 2 && tile.height < 2) {
+ return null;
+ }
+ if (addAndReturn) {
+ if (depth > 0 && smiParent.getNumOutside() > MAX_OUTSIDE_RATIO * tile.width * tile.height
+ && !tile.outsideRatioIsOK(MAX_OUTSIDE_RATIO)) {
+ return null;
+ }
+ Solution solution = new Solution(myMaxNodes);
+ solution.add(tile); // can't split further
+ return solution;
+ }
+ if (tile.getCount() < minNodes * 2) {
+ return null;
+ }
+ if (!trimTiles && tile.getMinParts(myMaxNodes) * minNodes > tile.getCount()) {
+ return null;
+ }
+
+ // we have to split the tile
+ Integer alreadyDone = null;
+ if (countBad == 0 && !incomplete.isEmpty()) {
+ alreadyDone = incomplete.remove(tile);
+ if (alreadyDone == null)
+ incomplete.clear(); // rest is not useful
+ }
+ final boolean isCacheCandidate = depth > 0 && tile.width * tile.height > MIN_TILE_AREA_BAD_CACHE;
+ if (alreadyDone == null && isCacheCandidate) {
+ Long x = knownBad.get(tile);
+ if (x != null && x <= minNodes) {
+ return null;
+ }
+ }
+
+ // copy the existing density info from parent
+ // typically, at least one half can be re-used
+ TileMetaInfo smi = new TileMetaInfo(tile, parent, smiParent);
+ smi.setMinNodes(minNodes);
+
+ // we have to split the tile
+ TestGenerator generator = new TestGenerator(searchAll, tile, smi);
+ int countDone = 0;
+ Solution bestSol = null;
+
+ while (generator.hasNext()) {
+ int splitPos = generator.next();
+ countDone++;
+ if (alreadyDone != null && countDone <= alreadyDone.intValue()) {
+ continue;
+ }
+ // create the two parts of the tile
+ int axis = generator.getAxis();
+ boolean ok = axis == AXIS_HOR ? tile.splitHoriz(splitPos, smi) : tile.splitVert(splitPos, smi);
+ if (!ok)
+ continue;
+
+ Tile[] parts = smi.getParts();
+ 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];
+ int countOK = 0;
+ for (int i = 0; i < 2; i++) {
+ if (trimTiles && smi.getNumOutside() > 0) {
+ parts[i] = parts[i].trim();
+ }
+ // depth first recursive search
+ if (incomplete.isEmpty() || incomplete.containsKey(parts[i])) {
+ sols[i] = findSolution(depth + 1, parts[i], tile, smi);
+ if (sols[i] == null) {
+ countBad++;
+ break;
+ }
+ countOK++;
+ }
+ }
+ if (countOK == 2) {
+ Solution sol = sols[0];
+ sol.merge(sols[1]);
+ if (bestSol == null || bestSol.compareTo(sol) > 0)
+ bestSol = sol;
+ if (depth > 0 || tile.getCount() > 2 * myMaxNodes)
+ break; // we found a valid split
+ } else if (countBad >= searchLimit) {
+ if (DEBUG)
+ System.out.println(name + ": limit reached " + depth + " min-nodes " + minNodes);
+ if (depth < MAX_DEPTH_STATS)
+ lastGoodCounts[depth] = -1;
+ incomplete.put(tile, countDone - 1);
+ break;
+ }
+ }
+
+ if (depth < MAX_DEPTH_STATS && countBad < searchLimit) {
+ lastGoodCounts[depth] = countDone;
+ }
+
+ smi.propagateToParent(smiParent, tile, parent);
+
+ if (bestSol == null && countBad < searchLimit && isCacheCandidate) {
+ Long x = knownBad.get(tile);
+ if (x == null || x > minNodes)
+ knownBad.put(tile, minNodes);
+ }
+
+ // check if we should perform a local optimisation
+ if (bestSol != null && localOptMinNodes > 0 && bestSol.size() > 2 && bestSol.size() <= 32) {
+ long backupMinNodes = minNodes;
+ boolean backupSearchAll = searchAll;
+ int backupCountBad = countBad;
+ int min = tile.getMinParts(myMaxNodes);
+ int oldSize = bestSol.size();
+ while (bestSol.size() > min) {
+ localOptMinNodes = Math.max(tile.getCount() / bestSol.size(), bestSol.getWorstMinNodes() + 1);
+ minNodes = localOptMinNodes;
+ searchAll = false;
+ countBad = 0;
+ Solution sol2 = findSolution(depth, tile, parent, smiParent);
+ if(DEBUG) {
+ if (countBad > 200_000) {
+ System.out.println(name + ": bad opt? tile " + tile + " required " + countBad + " bad tests for " + sol2);
+ }
+ }
+ optLoops++;
+ minNodes = backupMinNodes;
+ searchAll = backupSearchAll;
+ if (sol2 != null && sol2.isSmallerOrBetter(bestSol)) {
+ if (tile.getCount() > largestOptTileCount)
+ largestOptTileCount = tile.getCount();
+ if (oldSize > largestOptSize)
+ largestOptSize = oldSize;
+ bestSol = sol2; // we found a better split
+ } else
+ break;
+ }
+ countBad = backupCountBad;
+ }
+ return bestSol;
}
- 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) {
- // 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) {
- 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
- 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
- return (axis == AXIS_HOR) ? tile.genXTests(smi) : tile.genYTests(smi);
+
+ private boolean checkSize(Tile tile) {
+ return tile.height <= maxTileHeight && tile.width <= maxTileWidth;
+ }
+
+ @Override
+ public String toString() {
+ return name + " for tile " +startTile;
+ }
+
+ public void solve() {
+ bestPossible = stopNumber > 0 ? stopNumber : startTile.getMinParts(myMaxNodes);
+ solve0();
+ if (smallestSolution.isSmallerOrBetter(bestSolution))
+ bestSolution = smallestSolution;
+ System.out.println(name + " goal was " + bestPossible + " tiles, solver "
+ + (stopped ? "was stopped" : "finished") + " with : " + bestSolution.toString());
+ knownBad.clear();
+ incomplete.clear();
+ }
+
+ private void solve0() {
+ knownBad.clear();
+ lastGoodCounts = new int[MAX_DEPTH_STATS];
+ bestSolution = new Solution(myMaxNodes);
+ smallestSolution = new Solution(myMaxNodes);
+ minNodes = Math.max(Math.min((long) (0.05 * myMaxNodes), startTile.getLargestInfo()), 1);
+
+ searchLimit = startSearchLimit;
+ TileMetaInfo smiStart = new TileMetaInfo(startTile, null, null);
+ final long veryNiceMinNodes = (long) (VERY_NICE_FILL_RATIO * myMaxNodes);
+
+ boolean clearIncomplete = false;
+ for (int numLoops = 1; numLoops < MAX_LOOPS && !stopped; numLoops++) {
+ if (clearIncomplete) {
+ incomplete.clear();
+ }
+ // store values to be able to detect progress
+ double saveMaxAspectRatio = maxAspectRatio;
+ long saveMinNodes = minNodes;
+
+ countBad = 0;
+ final String dbgPrefix = name + ": step " + numLoops;
+ if (DEBUG) {
+ System.out.println(dbgPrefix + " searching for split with min-nodes " + minNodes + ", cache size " + Utils.format(knownBad.size()));
+ }
+ smiStart.setMinNodes(minNodes);
+ int oldCacheSize = knownBad.size();
+ largestOptTileCount = 0;
+ largestOptSize = 0;
+ Solution solution = findSolution(0, startTile, startTile, smiStart);
+ if (stopped)
+ return;
+ if (DEBUG) {
+ System.out.println(dbgPrefix + " positions " + Arrays.toString(lastGoodCounts));
+ if (optLoops > 0) {
+ System.out.println(dbgPrefix + " local opt. runs: " + optLoops
+ + ", worked up to count " + Utils.format(largestOptTileCount)
+ + ", worked up to old size " + largestOptSize
+ );
+ }
+ }
+ if (solution != null) {
+ if (solution.isSmallerOrBetter(smallestSolution)) {
+ smallestSolution = solution;
+ }
+ if (solution.size() < stopNumber) {
+ minNodes = (bestSolution.getWorstMinNodes() + solution.getWorstMinNodes()) / 2;
+ if(minNodes != saveMinNodes)
+ continue;
+ solution = null;
+ }
+ boolean foundBetter = bestSolution.compareTo(solution) > 0;
+ if (solution != null) {
+ if (foundBetter ) {
+ Solution prevBest = bestSolution;
+ bestSolution = solution;
+ System.out.println(dbgPrefix+ " goal: " + bestPossible + " tiles, now: "
+ + bestSolution + ", cache size " + Utils.format(knownBad.size()));
+ // change criteria to find a better(nicer) result
+ double factor = 1.10;
+ if (!prevBest.isEmpty() && prevBest.isNice())
+ factor = Math.min(1.30, (double) bestSolution.getWorstMinNodes() / prevBest.getWorstMinNodes());
+ minNodes = Math.max(myMaxNodes / 3, (long) (bestSolution.getWorstMinNodes() * factor));
+ if (localOptMinNodes == 0) {
+ // enable local optimisation
+ minNodes = bestSolution.getWorstMinNodes() + 1;
+ localOptMinNodes = minNodes;
+ }
+
+ } else {
+ minNodes = solution.getWorstMinNodes() + 1;
+ }
+ }
+ } else if (!bestSolution.isEmpty() && minNodes > bestSolution.getWorstMinNodes() + 1) {
+ // reduce minNodes
+ minNodes = (bestSolution.getWorstMinNodes() + minNodes) / 2;
+ if (minNodes < bestSolution.getWorstMinNodes() * 1.001)
+ minNodes = bestSolution.getWorstMinNodes() + 1;
+ } else if (!searchAll && oldCacheSize < knownBad.size()) {
+ if (bestSolution.isEmpty()) {
+ clearIncomplete = false;
+ continue;
+ }
+ }
+ if (!bestSolution.isEmpty() ) {
+ if (stopNumber * 0.95 > bestSolution.getTiles().size())
+ return;
+ if (bestSolution.size() == 1)
+ return;
+ if (bestSolution.size() == bestPossible && numLoops > 6) {
+ return;
+ }
+ }
+ if (stopNumber == 0 && minNodes > veryNiceMinNodes)
+ minNodes = veryNiceMinNodes;
+ clearIncomplete = true;
+ maxAspectRatio = Math.min(32, Math.max(bestSolution.getWorstAspectRatio() / 2, NICE_MAX_ASPECT_RATIO));
+ if (saveMaxAspectRatio == maxAspectRatio && saveMinNodes == minNodes) {
+ // no improvement found
+ boolean tryAgain = false;
+ if (bestSolution.isEmpty() || bestSolution.getWorstMinNodes() < 0.5 * myMaxNodes) {
+ // try to improve by adjusting threshold values
+ if (countBad > searchLimit && searchLimit < MAX_SEARCH_LIMIT) {
+ searchLimit *= 2;
+ knownBad.clear();
+ clearIncomplete = false;
+ System.out.println(name + ": No good solution found, duplicated search-limit to " + searchLimit);
+ tryAgain = true;
+ } else if (bestSolution.isEmpty() && minNodes > 1) {
+ minNodes = 1L;
+ searchLimit = searchAll? startSearchLimit : Math.max(MAX_SEARCH_LIMIT, startSearchLimit);
+ // sanity check
+ System.out.println(name + ": No good solution found, trying to find one accepting anything");
+ tryAgain = true;
+ } else if (!bestSolution.isEmpty() && smallestSolution.size() < bestSolution.size()
+ && minNodes != smallestSolution.getWorstMinNodes() + 1) {
+ minNodes = smallestSolution.getWorstMinNodes() + 1;
+ if (DEBUG) {
+ System.out.println(name + ": Trying to improve smallest solution");
+ }
+ tryAgain = true;
+ }
+ }
+ if (!tryAgain) {
+ return;
+ }
+ }
}
- 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;
- if (tests.get(0) != pos)
- tests.add(pos);
- pos = (axis == AXIS_HOR) ? tile.findFirstXHigher(smi, maxNodes) : tile.findFirstYHigher(smi, maxNodes);
- if (!tests.contains(pos))
- tests.add(pos);
- } else {
- if (range == 0) {
+ }
+
+ void stop() {
+ stopped = true;
+ }
+
+ private class TestGenerator {
+ final boolean searchAll;
+ int axis;
+ final Tile tile;
+ final TileMetaInfo smi;
+ int countAxis;
+ int usedTestPos;
+ private IntArrayList todoList;
+
+ public TestGenerator(boolean searchAll, Tile tile, TileMetaInfo smi) {
+ this.searchAll = searchAll;
+ this.tile = tile;
+ this.smi = smi;
+
+ axis = (tile.getAspectRatio() >= 1.0) ? AXIS_HOR : AXIS_VERT;
+ todoList = generateTestCases();
+ }
+
+ boolean hasNext() {
+ if (usedTestPos >= todoList.size()) {
+ countAxis++;
+ if (countAxis > 1)
+ return false;
+ axis = axis == AXIS_HOR ? AXIS_VERT : AXIS_HOR;
+ todoList = generateTestCases();
+ usedTestPos = 0;
+ }
+ return usedTestPos < todoList.size();
+ }
+
+ int next() {
+ return todoList.get(usedTestPos++);
+ }
+
+ public int getAxis() {
+ return axis;
+ }
+
+ IntArrayList generateTestCases() {
+ final int start = (axis == AXIS_HOR) ? tile.findValidStartX(smi) : tile.findValidStartY(smi);
+ final int end = (axis == AXIS_HOR) ? tile.findValidEndX(smi) : tile.findValidEndY(smi);
+ final int mid = (start + end) / 2;
+ final int range = end - start;
+ if (searchAll || range < 4) {
+ return Tile.genTests(start, end);
+ }
+ double ratio = tile.getAspectRatio();
+ IntArrayList tests = new IntArrayList();
+ if (range < 0 || ratio < 1.0 / 32 || ratio > 32 || ratio < 1.0 / 16 && axis == AXIS_HOR || ratio > 16 && axis == AXIS_VERT) {
+ return tests;
+ } else if (range == 0) {
tests.add(start);
- } else {
- if (nMax != 3)
- tests.add((axis == AXIS_HOR) ? tile.findHorizontalMiddle(smi) : tile.findVerticalMiddle(smi));
- if (!tests.contains(start))
- tests.add(start);
- if (!tests.contains(end))
+ return tests;
+ }
+
+ 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() < myMaxNodes * 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);
+ if (tests.get(tests.size() - 1) != end)
tests.add(end);
+ } else if (tile.getCount() > myMaxNodes * 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 {
+ // count <= 4 * max, this will be one of the last splits
+ long minCount = smi.getNumOutside() > 0 ? tile.countInside() : tile.getCount();
+ int nMin = (int) (minCount / myMaxNodes);
+ if (nMin * myMaxNodes < minCount)
+ nMin++;
+ long limit = minCount / nMin;
+ double dMin = (double) minCount / myMaxNodes;
+ final int around;
+ if ((dMin > 1.8 && dMin < 2.0 && ratio > 0.125 && ratio < 8) || (dMin > 2.8 && dMin < 3.0)) {
+ around = tile.findFirstHigher(axis, smi, limit);
+ } else if (dMin > 3.8) {
+ around = tile.findFirstHigher(axis, smi, 2 * limit);
+ } else {
+ around = -1;
+ }
+ if (around >= 0) {
+ // this is likely to be a good split, generate more cases
+ final int numAround = 20;
+ final int p1 = Math.max(start, around - numAround / 2);
+ final int p2 = Math.min(end, around + numAround / 2);
+ final int toAdd = p2 - p1;
+ if (toAdd > 16)
+ tests = new IntArrayList(toAdd);
+ for (int i = p1; i <= p2; i++) {
+ tests.add(i);
+ }
+ tests.sort((o1, o2) -> Integer.compare(Math.abs(o1 - around), Math.abs(o2 - around)));
+ return tests;
+ }
+ if (nMin == 4)
+ tests.add(tile.findFirstHigher(axis, smi, 2 * limit));
+ tests.add(tile.findFirstHigher(axis, smi, limit));
+
}
+ if (tests.size() > 4) {
+ tests.sort((o1, o2) -> Integer.compare(Math.abs(o1 - mid), Math.abs(o2 - mid)));
+ if (tests.getInt(0) != mid) {
+ tests.add(0, mid);
+ }
+ }
+
+ return tests;
}
}
- return tests;
}
+
}
=====================================
src/uk/me/parabola/splitter/solver/Tile.java
=====================================
@@ -13,12 +13,16 @@
package uk.me.parabola.splitter.solver;
+import java.awt.Rectangle;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
import it.unimi.dsi.fastutil.ints.IntArrayList;
import uk.me.parabola.splitter.Area;
+import uk.me.parabola.splitter.SplitFailedException;
import uk.me.parabola.splitter.Utils;
-import java.awt.Rectangle;
-
/**
* This class implements a "view" on a rectangle covering a part
* of a {@link DensityMap}.
@@ -54,10 +58,9 @@ import java.awt.Rectangle;
*/
public Tile(EnhancedDensityMap densityInfo, Rectangle r) {
super(r);
- if (r.x < 0 || r.y < 0
- || r.x + r.width > densityInfo.getDensityMap().getWidth()
- || r.y + r.height > densityInfo.getDensityMap().getHeight())
- throw new IllegalArgumentException("Rectangle doesn't fit into density map");
+ if (r.x < 0 || r.y < 0 || r.x + r.width > densityInfo.getDensityMap().getWidth()
+ || r.y + r.height > densityInfo.getDensityMap().getHeight())
+ throw new IllegalArgumentException("Rectangle doesn't fit into density map");
this.densityInfo = densityInfo;
count = calcCount();
@@ -93,48 +96,31 @@ import java.awt.Rectangle;
return (getCount() == calcCount());
}
- public IntArrayList genXTests(TileMetaInfo smi) {
- int start = this.findValidStartX(smi);
- int end = this.findValidEndX(smi);
- return genTests(start, end);
- }
-
- public IntArrayList genYTests(TileMetaInfo smi) {
- int start = this.findValidStartY(smi);
- int end = this.findValidEndY(smi);
- return genTests(start, end);
- }
-
- public static IntArrayList genTests(int start, int end) {
- if (end-start < 0)
- return new IntArrayList(1);
- int mid = (start + end) / 2;
- int toAdd = end-start+1;
+ public static IntArrayList genTests(final int start, final int end) {
+ if (end - start < 0)
+ return new IntArrayList(0);
+ final int mid = (start + end) / 2;
+ final int toAdd = end - start + 1;
IntArrayList list = new IntArrayList(toAdd);
- for (int i = 0; i <= mid; i++){
- int pos = mid + i;
- if (pos >= start && pos <= end)
- list.add(pos);
- if (list.size() >= toAdd)
- break;
- if (i == 0)
- continue;
- pos = mid - i;
- if (pos >= start && pos <= end)
- list.add(pos);
+ list.add(mid);
+ for (int i = 1; i < toAdd / 2; i++) {
+ list.add(mid + i);
+ list.add(mid - i);
}
+ if (list.size() < toAdd)
+ list.add(end);
+ if (list.size() < toAdd)
+ list.add(start);
return list;
}
-
-
/**
- * calculate the numnber of nodes in this tile
+ * calculate the number of nodes in this tile
* @return
*/
- private long calcCount(){
+ private long calcCount() {
long sum = 0;
- for (int i=0;i<height;i++){
+ for (int i = 0; i < height; i++) {
sum += getRowSum(i);
}
return sum;
@@ -142,6 +128,7 @@ import java.awt.Rectangle;
/**
* Calculate the sum of all grid elements within a row
+ *
* @param row the row within the tile (0..height-1)
* @return
*/
@@ -150,21 +137,23 @@ import java.awt.Rectangle;
int mapRow = row + y;
long sum = 0;
int[] vector = densityInfo.getMapRow(mapRow);
- if (vector != null){
- int lastX = x + width;
- for (int i = x; i < lastX; i++)
+ if (vector != null) {
+ final int lastX = x + width;
+ for (int i = x; i < lastX; i++)
sum += vector[i];
}
return sum;
}
- private long getRowSum(int row, long []rowSums){
+
+ private long getRowSum(int row, long[] rowSums) {
if (rowSums[row] < 0)
rowSums[row] = getRowSum(row);
return rowSums[row];
}
-
+
/**
* Calculate the sum of all grid elements within a column.
+ *
* @param col the column within the tile
* @return
*/
@@ -173,14 +162,15 @@ import java.awt.Rectangle;
int mapCol = col + x;
long sum = 0;
int[] vector = densityInfo.getMapCol(mapCol);
- if (vector != null){
- int lastY = y + height;
+ if (vector != null) {
+ final int lastY = y + height;
for (int i = y; i < lastY; i++)
sum += vector[i];
}
return sum;
}
- private long getColSum(int col, long[] colSums){
+
+ private long getColSum(int col, long[] colSums) {
if (colSums[col] < 0)
colSums[col] = getColSum(col);
return colSums[col];
@@ -423,7 +413,7 @@ import java.awt.Rectangle;
return smi.getValidEndY();
}
- public int findFirstXHigher(TileMetaInfo smi, long limit){
+ public int findFirstXHigher(TileMetaInfo smi, long limit) {
long sum = 0;
int start = (smi.getFirstNonZeroX() > 0) ? smi.getFirstNonZeroX() : 0;
for (int i = start; i < width; i++) {
@@ -432,15 +422,14 @@ import java.awt.Rectangle;
continue;
if (smi.getFirstNonZeroX() < 0)
smi.setFirstNonZeroX(i);
- if (sum > limit){
+ if (sum > limit) {
return i;
-
}
}
return height;
}
- public int findFirstYHigher(TileMetaInfo smi, long limit){
+ public int findFirstYHigher(TileMetaInfo smi, long limit) {
long sum = 0;
int start = (smi.getFirstNonZeroY() > 0) ? smi.getFirstNonZeroY() : 0;
for (int i = start; i < height; i++) {
@@ -449,14 +438,16 @@ import java.awt.Rectangle;
continue;
if (smi.getFirstNonZeroY() < 0)
smi.setFirstNonZeroY(i);
- if (sum > limit){
+ if (sum > limit) {
return i;
}
}
return height;
}
-
+ public int findFirstHigher(int axis, TileMetaInfo smi, long limit) {
+ return axis == SplittableDensityArea.AXIS_HOR ? findFirstXHigher(smi, limit) : findFirstYHigher(smi, limit);
+ }
/**
*
* @return aspect ratio of this tile
@@ -475,9 +466,9 @@ import java.awt.Rectangle;
long sumRemovedRowCounts = 0;
int minX = -1;
for (int i = 0; i < width; i++) {
- long colSum = getColSum(i) ;
- boolean needed = (densityInfo.getPolygonArea() == null) ? colSum > 0 : (colOutsidePolygon(i) == false);
- if (needed){
+ long colSum = getColSum(i);
+ boolean needed = (densityInfo.getPolygonArea() == null) ? colSum > 0 : !colOutsidePolygon(i);
+ if (needed) {
minX = x + i;
break;
}
@@ -485,9 +476,9 @@ import java.awt.Rectangle;
}
int maxX = -1;
for (int i = width - 1; i >= 0; i--) {
- long colSum = getColSum(i) ;
- boolean needed = (densityInfo.getPolygonArea() == null) ? colSum > 0 : (colOutsidePolygon(i) == false);
- if (needed){
+ long colSum = getColSum(i);
+ boolean needed = (densityInfo.getPolygonArea() == null) ? colSum > 0 : !colOutsidePolygon(i);
+ if (needed) {
maxX = x + i;
break;
}
@@ -496,8 +487,8 @@ import java.awt.Rectangle;
int minY = -1;
for (int i = 0; i < height; i++) {
long rowSum = getRowSum(i);
- boolean needed = (densityInfo.getPolygonArea() == null) ? rowSum > 0 : (rowOutsidePolygon(i) == false);
- if (needed){
+ boolean needed = (densityInfo.getPolygonArea() == null) ? rowSum > 0 : !rowOutsidePolygon(i);
+ if (needed) {
minY = y + i;
break;
}
@@ -506,30 +497,30 @@ import java.awt.Rectangle;
int maxY = -1;
for (int i = height - 1; i >= 0; i--) {
long rowSum = getRowSum(i);
- boolean needed = (densityInfo.getPolygonArea() == null) ? rowSum > 0 : (rowOutsidePolygon(i) == false);
- if (needed){
+ boolean needed = (densityInfo.getPolygonArea() == null) ? rowSum > 0 : !rowOutsidePolygon(i);
+ if (needed) {
maxY = y + i;
break;
}
sumRemovedRowCounts += rowSum;
}
- assert minX <= maxX;
- assert minY <= maxY;
- assert maxX >= 0;
- assert maxY >= 0;
+ if (minX > maxX || minY > maxY || maxX < 0 || maxY < 0) {
+ return new Tile(densityInfo, x, y, 0, 0, 0);
+ }
long newCount = getCount();
int modWidth = maxX - minX + 1;
int modHeight = maxY - minY + 1;
- if (densityInfo.getPolygonArea() != null){
- if (modWidth != width || modHeight != height){
- // tile was trimmed, try hard to avoid a new costly calculation of the count value
- if (width == modWidth){
- newCount = getCount() - sumRemovedRowCounts;
- } else if (height == modHeight){
+ if (densityInfo.getPolygonArea() != null) {
+ if (modWidth != width || modHeight != height) {
+ // tile was trimmed, try hard to avoid a new costly calculation of the count
+ // value
+ if (width == modWidth) {
+ newCount = getCount() - sumRemovedRowCounts;
+ } else if (height == modHeight) {
newCount = getCount() - sumRemovedColCounts;
} else {
-// System.out.printf("ouch: %d %d %d %d (%d) -> %d %d %d %d\n",x,y,width,height,count,minX,minY, maxX - minX + 1, maxY - minY + 1 );
- return new Tile (densityInfo, new Rectangle(minX, minY, modWidth, modHeight));
+ // worst case: recalculate
+ return new Tile(densityInfo, new Rectangle(minX, minY, modWidth, modHeight));
}
}
}
@@ -566,39 +557,40 @@ import java.awt.Rectangle;
public boolean outsidePolygon(){
java.awt.geom.Area polygonArea = densityInfo.getPolygonArea();
- if (polygonArea == null)
- return false;
- if (polygonArea.intersects(getRealBBox()))
- return false;
- return true;
+ return polygonArea != null && !polygonArea.intersects(getRealBBox());
}
/**
- * Count the number of grid elements which are outside of the polygon area,
- * divide it by the total number of grid elements covered by this tile to
- * get a value between 0 and 1 (including).
- * @return
+ *
+ * Check if enough grid elements are inside the polygon.
+ * @param maxOutsideRatio the wanted ratio
+ * @return true if the ratio inside/outside is greater than the given value
*/
- public double calcOutsidePolygonRatio (){
- if (densityInfo.getPolygonArea() == null)
- return 0;
+ public boolean outsideRatioIsOK(final double maxOutsideRatio) {
+ if (densityInfo.allInsidePolygon())
+ return true;
Rectangle realBBox = getRealBBox();
-// if (densityInfo.getPolygonArea().contains(realBBox) )
-// return 0;
// check special case: tile may contain the polygon
Rectangle polyBBox = densityInfo.getPolygonArea().getBounds();
- if (realBBox.contains(polyBBox)){
- return 0;
+ if (realBBox.contains(polyBBox)) {
+ return true;
}
- int countOutside = 0;
- for (int i = x; i < x+width; i++){
- for (int j = y; j < y+height; j++){
- if (densityInfo.isGridElemInPolygon(i,j) == false)
- countOutside++;
+ final long maxOutsde = (long) (maxOutsideRatio * (width * height));
+ final long neededInside = width * height - maxOutsde;
+ int countInside = 0;
+ int countOutside= 0;
+ for (int i = x; i < x + width; i++) {
+ for (int j = y; j < y + height; j++) {
+ if (densityInfo.isGridElemInPolygon(i, j)) {
+ if (++countInside >= neededInside)
+ return true;
+ } else {
+ if (++countOutside >= maxOutsde)
+ return false;
+ }
}
}
- double ratio = (double) countOutside / (width * height) ;
- return ratio;
+ return false;
}
public Rectangle getRealBBox(){
@@ -610,8 +602,7 @@ import java.awt.Rectangle;
@Override
public int hashCode() {
- int hash = x << 24 | y << 16 | width << 8 | height;
- return hash;
+ return x << 24 | y << 16 | width << 8 | height;
}
@Override
@@ -633,4 +624,99 @@ import java.awt.Rectangle;
// sb.append(getAspectRatio());
// return sb.toString();
}
+
+ /**
+ * return minimum number of parts when tile is split with the given maximum.
+ *
+ * @param maxNodes the maximum
+ * @return minimum number of parts for the given maximum
+ */
+ public int getMinParts(long maxNodes) {
+ long minCount = countInside();
+ int nMin = (int) (minCount / maxNodes);
+ if (nMin * maxNodes < minCount)
+ nMin++;
+ return nMin;
+ }
+
+ public long countInside() {
+ long minCount = 0;
+ if (densityInfo.getPolygonArea() == null || densityInfo.allInsidePolygon())
+ return count;
+ for (int i = 0; i < width; i++) {
+ final int[] col = densityInfo.getMapCol(x + i);
+ if (col != null) {
+ for (int k = 0; k < height; k++) {
+ if (densityInfo.isGridElemInPolygon(x + i, y + k))
+ minCount += col[y + k];
+ }
+ }
+ }
+ return minCount;
+ }
+
+ public int countElemsOutside() {
+ if (densityInfo.getPolygonArea() == null || densityInfo.allInsidePolygon())
+ return 0;
+ int num = 0;
+ for (int i = 0; i < width; i++) {
+ for (int k = 0; k < height; k++) {
+ if (!densityInfo.isGridElemInPolygon(x + i, y + k))
+ num++;
+ }
+ }
+ return num;
+ }
+
+ public List<Tile> divide(long maxNodes) {
+ if (getCount() < maxNodes)
+ return Arrays.asList(this);
+ List<Tile> parts = new ArrayList<>(2);
+ TileMetaInfo smi = new TileMetaInfo(this, null, null);
+ smi.setMinNodes(1); // don't create tiles with 0 nodes
+ boolean ok = false;
+ if (width > height) {
+ int start = findValidStartX(smi);
+ int end = findValidEndX(smi);
+ int mid = (start + end) / 2;
+ ok = splitHoriz(mid, smi);
+ } else {
+ int start = findValidStartY(smi);
+ int end = findValidEndY(smi);
+ int mid = (start + end) / 2;
+ ok = splitVert(mid, smi);
+ }
+ if (ok) {
+ for (Tile part : smi.getParts()) {
+ parts.addAll(part.divide(maxNodes));
+ }
+ } else {
+ parts.add(this);
+ }
+ return parts;
+ }
+
+ public double getFillRatio() {
+ return (double)getCount() / (width * height);
+ }
+
+ /**
+ * Find largest count in single grid element. Might be outside of the polygon.
+ * @return largest count in single grid element
+ */
+ int getLargestInfo() {
+ int largest = 0;
+ for (int i = 0; i < width; i++) {
+ final int[] col = densityInfo.getMapCol(x + i);
+ if (col != null) {
+ for (int k = 0; k < height; k++) {
+ int n = col[y+k];
+ if (n > largest) {
+ largest = n;
+ }
+ }
+ }
+ }
+ return largest;
+ }
}
=====================================
src/uk/me/parabola/splitter/solver/TileMetaInfo.java
=====================================
@@ -37,6 +37,7 @@ class TileMetaInfo {
private int horMidPos = -1;
private int validEndX = -1;
private int validEndY = -1;
+ private int numOutside = -1;
/**
* Copy information from parent tile to child. Reusing these values
@@ -63,8 +64,14 @@ class TileMetaInfo {
} else
Arrays.fill(colSums, -1);
- if (smiParent != null)
+ if (smiParent != null) {
this.minNodes = smiParent.minNodes;
+ if (smiParent.getNumOutside() == 0)
+ numOutside = 0;
+ }
+ if (numOutside < 0) {
+ numOutside = tile.countElemsOutside();
+ }
}
/**
@@ -194,6 +201,14 @@ class TileMetaInfo {
this.validEndY = pos;
}
+ public int getNumOutside() {
+ return numOutside;
+ }
+
+ public void setNumOutside(int numOutside) {
+ this.numOutside = numOutside;
+ }
+
/**
* Copy the information back from child to parent so that next child has more info.
* @param smiParent
=====================================
test/func/lib/Outputs.java
=====================================
@@ -53,7 +53,6 @@ public class Outputs {
* @param strings The list of strings to check.
*/
public void checkOutput(String... strings) {
- String out = getOut();
for (String s : strings) {
if (!out.contains(s)) {
// Test has failed. Construct an assertion that will print
@@ -71,7 +70,6 @@ public class Outputs {
* @param strings The list of strings to check.
*/
public void checkError(String... strings) {
- String err = getErr();
for (String s : strings) {
if (!err.contains(s)) {
// Test has failed. Construct an assertion that will print
=====================================
test/func/lib/TestUtils.java
=====================================
@@ -43,6 +43,10 @@ public class TestUtils {
private static final List<String> files = new ArrayList<>();
private static final Deque<Closeable> open = new ArrayDeque<>();
+ private TestUtils () {
+ // avoid implicit public constructor
+ }
+
static {
files.add(Args.DEF_AREAS_KML);
files.add(Args.DEF_AREAS_LIST);
@@ -51,11 +55,7 @@ public class TestUtils {
files.add(Args.DEF_DENSITIES);
files.add(Args.DEF_TEMPLATE);
- Runnable r = new Runnable() {
- public void run() {
- deleteOutputFiles();
- }
- };
+ Runnable r = TestUtils::deleteOutputFiles;
Thread t = new Thread(r);
Runtime.getRuntime().addShutdownHook(t);
}
@@ -91,39 +91,27 @@ public class TestUtils {
Collections.addAll(open, fileList);
}
- /**
- * Run with a single argument. The standard arguments are added first.
- * @param arg The argument.
- */
- public static Outputs run(String arg) {
- return run(new String[] {arg});
- }
-
/**
* Run with the given args. Some standard arguments are added first.
*
* To run without the standard args, use runRaw().
* @param in The arguments to use.
*/
- public static Outputs run(String ... in) {
+ public static Outputs run(String... in) {
List<String> args = new ArrayList<>(Arrays.asList(in));
OutputStream outsink = new ByteArrayOutputStream();
- PrintStream out = new PrintStream(outsink);
OutputStream errsink = new ByteArrayOutputStream();
- PrintStream err = new PrintStream(errsink);
PrintStream origout = System.out;
PrintStream origerr = System.err;
- try {
+ try (PrintStream out = new PrintStream(outsink); PrintStream err = new PrintStream(errsink)) {
System.setOut(out);
System.setErr(err);
Main.mainNoSystemExit(args.toArray(new String[args.size()]));
} finally {
- out.close();
- err.close();
System.setOut(origout);
System.setErr(origerr);
}
View it on GitLab: https://salsa.debian.org/debian-gis-team/mkgmap-splitter/-/commit/f8f0ee8b75c6e83de5463ca044102605fca3810c
--
View it on GitLab: https://salsa.debian.org/debian-gis-team/mkgmap-splitter/-/commit/f8f0ee8b75c6e83de5463ca044102605fca3810c
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/20211201/337c0c26/attachment-0001.htm>
More information about the Pkg-grass-devel
mailing list