I have a working solution for ensuring that the created point is placed
within the polygon when using --add-pois-to-areas, based on drawing the
polygon on to a small monochrome bitmap and then looking for the point that
is furthest from the surrounding area. I used a 9x9 bitmap for polygons
having a small number of points and 15x15 for longer polygons. There is
however a performance penalty. My standard map takes about 1 hour 20
minutes; using this algorithm the time increases by about 50% to about 2
hours. I am not currently able to commit changes to SVN (perhaps someone can
help out with that) but I have attached the code changes. I suggest that due
to the performance penalty, if we adopt this, then the --add-pois-to-areas
option be extended to be --add-pois-to-areas[=centre|optimised] or something
similar, with the default being centre and functioning as now and the
optimised option invoking the new code. Please try out the suggested change.
Note I don't expect this to work properly where a polygon is formed from a
multiploygon relation, but the code could quite easily be adapted for this
circumstance.
Regards,
Mike
Additions to Way.java:
import java.awt.image.BufferedImage;
/*
* Find a point that is farthest from the edge of the shape
* by drawing the shape onto a small monochrome bitmap and
* then finding the point that is farthest from a black pixel.
* The shape is scaled differently in X and Y to fit a square bitmap.
* The size of the bitmap depends on the number of points in the shape.
*/
public Coord getPointWithinArea() {
// if shape is not closed or must be convex, use getCofG
if ((points.size() < 5) || !isClosed())
return getCofG();
// first get the coordinates of the rectangle containing the way
int minLat = Integer.MAX_VALUE;
int minLon = Integer.MAX_VALUE;
int maxLat = Integer.MIN_VALUE;
int maxLon = Integer.MIN_VALUE;
for(Coord p : points) {
int lat = p.getHighPrecLat();
int lon = p.getHighPrecLon();
minLat = Math.min(minLat, lat);
minLon = Math.min(minLon, lon);
maxLat = Math.max(maxLat, lat);
maxLon = Math.max(maxLon, lon);
}
if ((maxLon == minLon) || (maxLat == minLat))
return Coord.makeHighPrecCoord((maxLat + minLat) / 2,
(maxLon + minLon) / 2);
// choose a bitmap resolution based on the number of points
int bitmapSize = points.size() < 10 ? 9 : 15;
int halfBitmapSize = bitmapSize / 2;
int halfBitmapSize2 = bitmapSize - halfBitmapSize;
// create a polygon scaled to fit the resolution
double xScale = (double)(bitmapSize - 1) / (double)(maxLon -
minLon);
double yScale = (double)(bitmapSize - 1) / (double)(maxLat -
minLat);
Polygon polygon = new Polygon();
for(Coord p : points)
polygon.addPoint((int)((p.getHighPrecLon() - minLon) *
xScale), (int)((p.getHighPrecLat() - minLat) * yScale));
// draw the polygon as a white shape on a black background
BufferedImage image = new BufferedImage (bitmapSize,
bitmapSize, BufferedImage.TYPE_BYTE_BINARY);
Graphics2D graphics = image.createGraphics();
graphics.setColor(Color.black);
graphics.fillRect(0, 0, bitmapSize, bitmapSize);
graphics.setColor(Color.white);
graphics.fillPolygon(polygon);
// set the default coordinate to the middle of the bitmap
int bestX = halfBitmapSize;
int bestY = halfBitmapSize;
// examine each point in the bitmap, to see whether it is
farthest from a black pixel
// start at the centre point and move outwards in concentric
squares
// we can stop looking when we are closer to the edge than the
biggest distance
int biggestSquaredDistanceToBlack =
getSquaredDistanceToBlack(image, bestX, bestY);
for (int start = 1; (start <= halfBitmapSize) &&
(biggestSquaredDistanceToBlack < (halfBitmapSize2 - start) * (halfBitmapSize2 -
start)); start++) {
for (int i = 0; i <= start; i++) {
int x = halfBitmapSize + i;
int y = halfBitmapSize + start;
int squaredDistanceToBlack =
getSquaredDistanceToBlack(image, x, y);
if (biggestSquaredDistanceToBlack <
squaredDistanceToBlack) {
biggestSquaredDistanceToBlack =
squaredDistanceToBlack;
bestX = x;
bestY = y;
}
x = halfBitmapSize - i;
y = halfBitmapSize - start;
squaredDistanceToBlack =
getSquaredDistanceToBlack(image, x, y);
if (biggestSquaredDistanceToBlack <
squaredDistanceToBlack) {
biggestSquaredDistanceToBlack =
squaredDistanceToBlack;
bestX = x;
bestY = y;
}
x = halfBitmapSize + start;
y = halfBitmapSize - i;
squaredDistanceToBlack =
getSquaredDistanceToBlack(image, x, y);
if (biggestSquaredDistanceToBlack <
squaredDistanceToBlack) {
biggestSquaredDistanceToBlack =
squaredDistanceToBlack;
bestX = x;
bestY = y;
}
x = halfBitmapSize - start;
y = halfBitmapSize + i;
squaredDistanceToBlack =
getSquaredDistanceToBlack(image, x, y);
if (biggestSquaredDistanceToBlack <
squaredDistanceToBlack) {
biggestSquaredDistanceToBlack =
squaredDistanceToBlack;
bestX = x;
bestY = y;
}
if ( i > 0) {
x = halfBitmapSize - i;
y = halfBitmapSize + start;
squaredDistanceToBlack =
getSquaredDistanceToBlack(image, x, y);
if (biggestSquaredDistanceToBlack <
squaredDistanceToBlack) {
biggestSquaredDistanceToBlack =
squaredDistanceToBlack;
bestX = x;
bestY = y;
}
x = halfBitmapSize + i;
y = halfBitmapSize - start;
squaredDistanceToBlack =
getSquaredDistanceToBlack(image, x, y);
if (biggestSquaredDistanceToBlack <
squaredDistanceToBlack) {
biggestSquaredDistanceToBlack =
squaredDistanceToBlack;
bestX = x;
bestY = y;
}
x = halfBitmapSize + start;
y = halfBitmapSize + i;
squaredDistanceToBlack =
getSquaredDistanceToBlack(image, x, y);
if (biggestSquaredDistanceToBlack <
squaredDistanceToBlack) {
biggestSquaredDistanceToBlack =
squaredDistanceToBlack;
bestX = x;
bestY = y;
}
x = halfBitmapSize - start;
y = halfBitmapSize - i;
squaredDistanceToBlack =
getSquaredDistanceToBlack(image, x, y);
if (biggestSquaredDistanceToBlack <
squaredDistanceToBlack) {
biggestSquaredDistanceToBlack =
squaredDistanceToBlack;
bestX = x;
bestY = y;
}
}
}
}
return Coord.makeHighPrecCoord(minLat + (int)Math.round((bestY
+ 0.5) / yScale), minLon + (int)Math.round((bestX + 0.5) / xScale));
}
private int getSquaredDistanceToBlack(BufferedImage image, int x, int y)
{
if ((image.getRGB(x, y) & 0xffffff) == 0)
return 0;
int bitmapSize = image.getWidth();
int halfBitmapSize = bitmapSize / 2;
for (int delta = 1; delta <= halfBitmapSize; delta++) {
if ((x < delta) ||
(x + delta >= bitmapSize) ||
(y < delta) ||
(y + delta >= bitmapSize) ||
((image.getRGB(x + delta, y) & 0xffffff) == 0)
||
((image.getRGB(x - delta, y) & 0xffffff) == 0)
||
((image.getRGB(x, y + delta) & 0xffffff) == 0)
||
((image.getRGB(x, y - delta) & 0xffffff) == 0))
return delta * delta;
for (int delta2 = 1; delta2 < delta; delta2++) {
if (((image.getRGB(x + delta, y + delta2) &
0xffffff) == 0) ||
((image.getRGB(x - delta, y + delta2) &
0xffffff) == 0) ||
((image.getRGB(x + delta2, y + delta) &
0xffffff) == 0) ||
((image.getRGB(x + delta2, y - delta) &
0xffffff) == 0) ||
((image.getRGB(x + delta, y - delta2) &
0xffffff) == 0) ||
((image.getRGB(x - delta, y - delta2) &
0xffffff) == 0) ||
((image.getRGB(x - delta2, y + delta) &
0xffffff) == 0) ||
((image.getRGB(x - delta2, y - delta) &
0xffffff) == 0))
return delta * delta + delta2 * delta2;
}
if (((image.getRGB(x + delta, y + delta) & 0xffffff) ==
0) ||
((image.getRGB(x - delta, y + delta) &
0xffffff) == 0) ||
((image.getRGB(x + delta, y - delta) &
0xffffff) == 0) ||
((image.getRGB(x - delta, y - delta) &
0xffffff) == 0))
return 2 * delta * delta;
}
return 2 * halfBitmapSize * halfBitmapSize;
}
In function addPOItoPolygon in POIGeneratorHook.java, replace:
if (poiCoord == null) {
// did not find any label coord
// use the common center point of the area
poiCoord = polygon.getCofG();
}
with:
if (poiCoord == null) {
// did not find any label coord
// find a suitable point within the area
poiCoord = polygon.getPointWithinArea();
}
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
