/*
* Copyright (c) 2009, Chris Miller
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 3 as
* published by the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*/
package uk.me.parabola.splitter.solver;
import java.awt.Point;
import java.awt.Rectangle;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.LineNumberReader;
import java.util.List;
import java.util.regex.Pattern;
import uk.me.parabola.splitter.Area;
import uk.me.parabola.splitter.MapDetails;
import uk.me.parabola.splitter.RoundingUtils;
import uk.me.parabola.splitter.SplitFailedException;
import uk.me.parabola.splitter.Utils;
/**
* Builds up a map of node densities across the total area being split.
* Density information is held at the maximum desired map resolution.
* Every step up in resolution increases the size of the density map by
* a factor of 4.
*
* @author Chris Miller
*/
public class DensityMap
{
private static final int SEA_NODE_FACTOR =
2;
private final int width, height, shift
;
private int[][] nodeMap
;
private Area bounds
;
private long totalNodeCount
;
/**
* Creates a density map.
* @param area the area that the density map covers.
* @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;
shift =
24 - resolution
;
bounds = RoundingUtils.
round(area, resolution
);
height = bounds.
getHeight() >> shift
;
width = bounds.
getWidth() >> shift
;
nodeMap =
new int[width
][];
}
/**
* @param polygonArea the polygon area
* @return an area with rectilinear shape that approximates the polygon area
*/
public java.
awt.
geom.
Area rasterPolygon
(java.
awt.
geom.
Area polygonArea
) {
if (polygonArea ==
null)
return null;
java.
awt.
geom.
Area simpleArea =
new java.
awt.
geom.
Area();
if (!polygonArea.
intersects(Utils.
area2Rectangle(bounds,
0)))
return simpleArea
;
int gridElemWidth = bounds.
getWidth() / width
;
int gridElemHeight = bounds.
getHeight() / height
;
Rectangle polygonBbox = polygonArea.
getBounds();
int minLat =
Math.
max((int) polygonBbox.
getMinY(), bounds.
getMinLat());
int maxLat =
Math.
min((int) polygonBbox.
getMaxY(), bounds.
getMaxLat());
int minY = latToY
(minLat
);
int maxY = latToY
(maxLat
);
assert minY
>=
0 && minY
<= height
;
assert maxY
>=
0 && maxY
<= height
;
for (int x =
0; x
< width
; x++
) {
int lon = xToLon
(x
);
if (lon + gridElemWidth
< polygonBbox.
getMinX()
|| lon
> polygonBbox.
getMaxX()
||
!polygonArea.
intersects(lon, polygonBbox.
getMinY(), gridElemWidth, polygonBbox.
getHeight())) {
continue;
}
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
)) {
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
;
}
}
if (firstY
>=
0){
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 polygon area contains holes, polygon is probably concave, trying to fix this");
simpleArea.
reset();
shapes.
forEach(s -
> simpleArea.
add(Utils.
shapeToArea(s
)));
}
}
return simpleArea
;
}
public int getShift
() {
return shift
;
}
public Area getBounds
() {
return bounds
;
}
public int getWidth
() {
return width
;
}
public int getHeight
() {
return height
;
}
public int addNode
(int lat,
int lon
) {
if (!bounds.
contains(lat, lon
))
return 0;
totalNodeCount++
;
int x = lonToX
(lon
);
if (x == width
)
x--
;
int y = latToY
(lat
);
if (y == height
)
y--
;
if (nodeMap
[x
] ==
null)
nodeMap
[x
] =
new int[height
];
return ++nodeMap
[x
][y
];
}
public long getNodeCount
() {
return totalNodeCount
;
}
public int getNodeCount
(int x,
int y
) {
return nodeMap
[x
] !=
null ? nodeMap
[x
][y
] :
0;
}
public DensityMap subset
(final Area subsetBounds
) {
int minLat =
Math.
max(bounds.
getMinLat(), subsetBounds.
getMinLat());
int minLon =
Math.
max(bounds.
getMinLong(), subsetBounds.
getMinLong());
int maxLat =
Math.
min(bounds.
getMaxLat(), subsetBounds.
getMaxLat());
int maxLon =
Math.
min(bounds.
getMaxLong(), subsetBounds.
getMaxLong());
// If the area doesn't intersect with the density map, return an empty map
if (minLat
> maxLat || minLon
> maxLon
) {
return new DensityMap
(Area.
EMPTY,
24 - shift
);
}
Area subset =
new Area(minLat, minLon, maxLat, maxLon
);
// If there's nothing in the area return an empty map
if (subset.
getWidth() ==
0 || subset.
getHeight() ==
0) {
return new DensityMap
(Area.
EMPTY,
24 - shift
);
}
DensityMap result =
new DensityMap
(subset,
24 - shift
);
int startX = lonToX
(subset.
getMinLong());
int startY = latToY
(subset.
getMinLat());
int maxX = subset.
getWidth() >> shift
;
int maxY = subset.
getHeight() >> shift
;
for (int x =
0; x
< maxX
; x++
) {
if (startY ==
0 && maxY == height
) {
result.
nodeMap[x
] = nodeMap
[startX + x
];
} else if (nodeMap
[startX + x
] !=
null) {
result.
nodeMap[x
] =
new int[maxY
];
try {
System.
arraycopy(nodeMap
[startX + x
], startY, result.
nodeMap[x
],
0, maxY
);
} catch (ArrayIndexOutOfBoundsException e
) {
System.
out.
println("subSet() died at " + startX +
',' + startY +
" " + maxX +
',' + maxY +
" " + x
);
}
}
for (int y =
0; y
< maxY
; y++
) {
if (result.
nodeMap[x
] !=
null)
result.
totalNodeCount += result.
nodeMap[x
][y
];
}
}
return result
;
}
private int yToLat
(int y
) {
return (y
<< shift
) + bounds.
getMinLat();
}
private int xToLon
(int x
) {
return (x
<< shift
) + bounds.
getMinLong();
}
private int latToY
(int lat
) {
return lat - bounds.
getMinLat() >>> shift
;
}
private int lonToX
(int lon
) {
return lon - bounds.
getMinLong() >>> shift
;
}
/**
* Write content of density map to file. Serves for easier debugging,
* but may also be used to manipulate the map with other tools.
* @param fileName the name of the output file
* @param detailBounds
* @param collectorBounds
*/
public void saveMap
(String fileName,
Area detailBounds,
Area collectorBounds
) {
try (FileWriter f =
new FileWriter(new File(fileName
))){
f.
write(detailBounds.
getMinLat() +
"," + detailBounds.
getMinLong() +
"," + detailBounds.
getMaxLat() +
"," + detailBounds.
getMaxLong() +
'\n');
if (collectorBounds
!=
null)
f.
write(collectorBounds.
getMinLat() +
"," + collectorBounds.
getMinLong() +
"," + collectorBounds.
getMaxLat() +
"," + collectorBounds.
getMaxLong() +
'\n');
else
f.
write("no_bounds_in_input\n");
for (int x=
0; x
<width
; x++
){
if (nodeMap
[x
] !=
null){
for (int y=
0; y
<height
; y++
){
if (nodeMap
[x
][y
] !=
0)
f.
write(x+
"," + y +
"," + nodeMap
[x
][y
] +
'\n');
}
}
}
} catch (IOException e
) {
e.
printStackTrace();
System.
err.
println("Warning: Could not write " + fileName +
", processing continues.");
}
}
/**
* For debugging, to be removed.
* @param fileName
* @param details
* @return
*/
public Area readMap
(String fileName, MapDetails details
) {
File mapFile =
new File(fileName
);
Area collectorBounds =
null;
if (!mapFile.
exists()) {
System.
out.
println("Error: map file doesn't exist: " + mapFile
);
return null;
}
try (InputStream fileStream =
new FileInputStream(mapFile
);
LineNumberReader problemReader =
new LineNumberReader(
new InputStreamReader(fileStream
));) {
Pattern csvSplitter =
Pattern.
compile(Pattern.
quote(","));
String inLine
;
String[] items
;
inLine = problemReader.
readLine();
if (inLine
!=
null){
items = csvSplitter.
split(inLine
);
if (items.
length !=
4) {
reportErrorLine
(problemReader.
getLineNumber(), inLine
);
return null;
}
details.
addToBounds(Integer.
parseInt(items
[0]),
Integer.
parseInt(items
[1]));
details.
addToBounds(Integer.
parseInt(items
[2]),
Integer.
parseInt(items
[3]));
}
inLine = problemReader.
readLine();
if (inLine
!=
null && !"no_bounds_in_input".
equals(inLine
)) {
items = csvSplitter.
split(inLine
);
if (items.
length !=
4) {
reportErrorLine
(problemReader.
getLineNumber(), inLine
);
return null;
}
collectorBounds =
new Area(Integer.
parseInt(items
[0]),
Integer.
parseInt(items
[1]),
Integer.
parseInt(items
[2]),
Integer.
parseInt(items
[3]));
}
while ((inLine = problemReader.
readLine()) !=
null) {
items = csvSplitter.
split(inLine
);
if (items.
length !=
3) {
reportErrorLine
(problemReader.
getLineNumber(), inLine
);
return null;
}
int x,y,sum
;
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
);
} else {
if (nodeMap
[x
] ==
null)
nodeMap
[x
] =
new int[height
];
nodeMap
[x
][y
] = sum
;
totalNodeCount += sum
;
}
}
catch(NumberFormatException exp
){
System.
out.
println("Error: Invalid number format in density file " + fileName +
", line " + problemReader.
getLineNumber() +
": " + inLine
);
System.
out.
println(exp
);
throw new SplitFailedException
("Error: Cannot read density file " + mapFile
);
}
}
} catch (IOException exp
) {
throw new SplitFailedException
("Error: Cannot read density file " + mapFile
);
}
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;
assert width2
> 0;
assert height2
> 0;
return new Area(yToLat
(y
),xToLon
(x
),yToLat
(y+height2
),xToLon
(x+width2
));
}
/**
* Handle data that will be added with the --precomp-sea option of mkgmap.
* We add coast line data only to empty parts to avoid counting it twice.
* @param seaData a DensityMap that was filled with data from precompiled sea
* @param area
*/
public void mergeSeaData
(DensityMap seaData,
Area area,
boolean trim
) {
if (this.
shift != seaData.
shift
||
!Utils.
area2Rectangle(bounds,
0).
equals(Utils.
area2Rectangle(seaData.
getBounds(),
0))) {
throw new SplitFailedException
("cannot merge density maps");
}
if (trim
&& totalNodeCount ==
0)
return;
int minX = lonToX
(area.
getMinLong());
int maxX = lonToX
(area.
getMaxLong());
int minY = latToY
(area.
getMinLat());
int maxY = latToY
(area.
getMaxLat());
if (maxX
>= width
)
maxX = width -
1;
if (maxY
>= height
)
maxY = height -
1;
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++
) {
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) {
int seaCount = seaCol
[y
] * SEA_NODE_FACTOR
;
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;
}
}