/*
* Copyright (C) 2007 Steve Ratcliffe
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 2 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.
*
*
* Author: Steve Ratcliffe
* Create date: 21-Jan-2007
*/
package uk.me.parabola.mkgmap.build;
import java.util.ArrayList;
import java.util.List;
import uk.me.parabola.imgfmt.app.Area;
import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.imgfmt.app.trergn.Overview;
import uk.me.parabola.log.Logger;
import uk.me.parabola.mkgmap.filters.FilterConfig;
import uk.me.parabola.mkgmap.filters.LineSizeSplitterFilter;
import uk.me.parabola.mkgmap.filters.LineSplitterFilter;
import uk.me.parabola.mkgmap.filters.MapFilterChain;
import uk.me.parabola.mkgmap.filters.PolygonSplitterFilter;
import uk.me.parabola.mkgmap.filters.PolygonSubdivSizeSplitterFilter;
import uk.me.parabola.mkgmap.general.MapDataSource;
import uk.me.parabola.mkgmap.general.MapElement;
import uk.me.parabola.mkgmap.general.MapLine;
import uk.me.parabola.mkgmap.general.MapPoint;
import uk.me.parabola.mkgmap.general.MapRoad;
import uk.me.parabola.mkgmap.general.MapShape;
import uk.me.parabola.imgfmt.app.net.RoadNetwork;
/**
* A sub area of the map. We have to divide the map up into areas to meet the
* format of the Garmin map. This class holds all the map elements that belong
* to a particular area and provides a way of splitting areas into smaller ones.
*
* It also acts as a map data source so that we can derive lower level
* areas from it.
*
* @author Steve Ratcliffe
*/
public class MapArea
implements MapDataSource
{
private static final Logger log =
Logger.
getLogger(MapArea.
class);
private static final int INITIAL_CAPACITY =
100;
private static final int MAX_RESOLUTION =
24;
public static final int POINT_KIND =
0;
public static final int LINE_KIND =
1;
public static final int SHAPE_KIND =
2;
public static final int XT_POINT_KIND =
3;
public static final int XT_LINE_KIND =
4;
public static final int XT_SHAPE_KIND =
5;
public static final int NUM_KINDS =
6;
// This is the initial area.
private final Area bounds
;
// Because ways may extend beyond the bounds, we keep track of the actual
// bounding box here.
private int minLat =
Integer.
MAX_VALUE;
private int minLon =
Integer.
MAX_VALUE;
private int maxLat =
Integer.
MIN_VALUE;
private int maxLon =
Integer.
MIN_VALUE;
// The contents of the area.
private final List<MapPoint
> points =
new ArrayList<MapPoint
>(INITIAL_CAPACITY
);
private final List<MapLine
> lines =
new ArrayList<MapLine
>(INITIAL_CAPACITY
);
private final List<MapShape
> shapes =
new ArrayList<MapShape
>(INITIAL_CAPACITY
);
// amount of space required for the contents
private final int[] sizes =
new int[NUM_KINDS
];
private int nActivePoints
;
private int nActiveIndPoints
;
private int nActiveLines
;
private int nActiveShapes
;
/** The resolution that this area is at */
private final int areaResolution
;
/**
* Create a map area from the given map data source. This map
* area will have the same bounds as the map data source and
* will contain all the same map elements.
*
* @param src The map data source to initialise this area with.
* @param resolution The resolution of this area.
*/
public MapArea
(MapDataSource src,
int resolution
) {
this.
areaResolution =
0;
this.
bounds = src.
getBounds();
addToBounds
(bounds
);
for (MapPoint p : src.
getPoints()) {
if(bounds.
contains(p.
getLocation()))
addPoint
(p
);
else
log.
error("Point with type 0x" +
Integer.
toHexString(p.
getType()) +
" at " + p.
getLocation().
toOSMURL() +
" is outside of the map area centred on " + bounds.
getCenter().
toOSMURL() +
" width = " + bounds.
getWidth() +
" height = " + bounds.
getHeight() +
" resolution = " + resolution
);
}
addLines
(src, resolution
);
addPolygons
(src, resolution
);
}
/**
* Add the polygons, making sure that they are not too big.
* @param src The map data.
* @param resolution The resolution of this layer.
*/
private void addPolygons
(MapDataSource src,
final int resolution
) {
MapFilterChain chain =
new MapFilterChain
() {
public void doFilter
(MapElement element
) {
MapShape shape =
(MapShape
) element
;
shapes.
add(shape
);
addToBounds
(shape.
getBounds());
addSize
(element, shape.
hasExtendedType()? XT_SHAPE_KIND : SHAPE_KIND
);
}
};
PolygonSubdivSizeSplitterFilter filter =
new PolygonSubdivSizeSplitterFilter
();
FilterConfig config =
new FilterConfig
();
config.
setResolution(resolution
);
config.
setBounds(bounds
);
filter.
init(config
);
for (MapShape s : src.
getShapes()) {
filter.
doFilter(s, chain
);
}
}
/**
* Add the lines, making sure that they are not too big for resolution
* that we are working with.
* @param src The map data.
* @param resolution The current resolution of the layer.
*/
private void addLines
(MapDataSource src,
final int resolution
) {
// Split lines for size, such that it is appropriate for the
// resolution that it is at.
MapFilterChain chain =
new MapFilterChain
() {
public void doFilter
(MapElement element
) {
MapLine line =
(MapLine
) element
;
lines.
add(line
);
addToBounds
(line.
getBounds());
addSize
(element, line.
hasExtendedType()? XT_LINE_KIND : LINE_KIND
);
}
};
LineSizeSplitterFilter filter =
new LineSizeSplitterFilter
();
FilterConfig config =
new FilterConfig
();
config.
setResolution(resolution
);
config.
setBounds(bounds
);
filter.
init(config
);
for (MapLine l : src.
getLines()) {
filter.
doFilter(l, chain
);
}
}
/**
* Create an map area with the given initial bounds.
*
* @param area The bounds for this area.
* @param res The minimum resolution for this area.
*/
private MapArea
(Area area,
int res
) {
bounds = area
;
areaResolution = res
;
addToBounds
(area
);
}
/**
* Split this area into several pieces. All the map elements are reallocated
* to the appropriate subarea. Usually this instance would now be thrown
* away and the new sub areas used instead.
*
* @param nx The number of pieces in the x (longitude) direction.
* @param ny The number of pieces in the y direction.
* @param resolution The resolution of the level.
* @param bounds the bounding box that is used to create the areas.
* @return An array of the new MapArea's.
*/
public MapArea
[] split
(int nx,
int ny,
int resolution,
Area bounds
) {
Area[] areas = bounds.
split(nx, ny
);
MapArea
[] mapAreas =
new MapArea
[nx
* ny
];
log.
info("Splitting area " + bounds +
" into " + nx +
"x" + ny +
" pieces at resolution " + resolution
);
boolean useNormalSplit =
true;
while (true){
for (int i =
0; i
< nx
* ny
; i++
) {
mapAreas
[i
] =
new MapArea
(areas
[i
], resolution
);
if (log.
isDebugEnabled())
log.
debug("area before", mapAreas
[i
].
getBounds());
}
int xbase30 = areas
[0].
getMinLong() << Coord.
DELTA_SHIFT;
int ybase30 = areas
[0].
getMinLat() << Coord.
DELTA_SHIFT;
int dx30 = areas
[0].
getWidth() << Coord.
DELTA_SHIFT;
int dy30 = areas
[0].
getHeight() << Coord.
DELTA_SHIFT;
boolean[] used =
new boolean[nx
* ny
];
// Now sprinkle each map element into the correct map area.
for (MapPoint p :
this.
points) {
int pos = pickArea
(mapAreas, p, xbase30, ybase30, nx, ny, dx30, dy30
);
mapAreas
[pos
].
addPoint(p
);
used
[pos
] =
true;
}
int areaIndex =
0;
for (MapLine l :
this.
lines) {
// Drop any zero sized lines.
if (l
instanceof MapRoad ==
false && l.
getRect().
height <=
0 && l.
getRect().
width <=
0)
continue;
if (useNormalSplit
)
areaIndex = pickArea
(mapAreas, l, xbase30, ybase30, nx, ny, dx30, dy30
);
else
areaIndex = ++areaIndex
% mapAreas.
length;
mapAreas
[areaIndex
].
addLine(l
);
used
[areaIndex
] =
true;
}
for (MapShape e :
this.
shapes) {
if (useNormalSplit
)
areaIndex = pickArea
(mapAreas, e, xbase30, ybase30, nx, ny, dx30, dy30
);
else
areaIndex = ++areaIndex
% mapAreas.
length;
mapAreas
[areaIndex
].
addShape(e
);
used
[areaIndex
] =
true;
}
// detect special case
if (useNormalSplit
&& mapAreas.
length ==
2 && bounds.
getMaxDimension() < 2 * (MapSplitter.
MIN_DIMENSION +
1)
&& used
[0] != used
[1]
&& (this.
lines.
size() > 1 ||
this.
shapes.
size() > 1)) {
/* if we get here we probably have two or more identical long ways or
* big shapes with the same center point. We can safely distribute
* them equally to the two areas.
*/
useNormalSplit =
false;
continue;
}
return mapAreas
;
}
}
/**
* Get the full bounds of this area. As lines and polylines are
* added then may go outside of the initial area. When this happens
* we need to increase the size of the area.
*
* @return The full size required to hold all the included
* elements.
*/
public Area getFullBounds
() {
return new Area(minLat, minLon, maxLat, maxLon
);
}
/**
* Get an estimate of the size of the RGN space that will be required to
* hold the elements
*
* @return Estimates of the max size that will be needed in the RGN file
* for the points/lines/shapes in this sub-division.
*/
public int[] getEstimatedSizes
() {
return sizes
;
}
/**
* Get the initial bounds of this area. That is the initial
* bounds before anything was added.
*
* @return The initial bounds as when it was created.
* @see #getFullBounds
*/
public Area getBounds
() {
return bounds
;
}
/**
* Get a list of all the points.
*
* @return The points.
*/
public List<MapPoint
> getPoints
() {
return points
;
}
/**
* Get a list of all the lines.
*
* @return The lines.
*/
public List<MapLine
> getLines
() {
return lines
;
}
/**
* Get a list of all the shapes.
*
* @return The shapes.
*/
public List<MapShape
> getShapes
() {
return shapes
;
}
public RoadNetwork getRoadNetwork
() {
// I don't think this is needed here.
return null;
}
/**
* This is not used for areas.
* @return Always returns null.
*/
public List<Overview
> getOverviews
() {
return null;
}
/**
* True if there are any 'active' points in this area. Ie ones that will be
* shown because their resolution is at least as high as that of the
* area.
*
* @return True if any active points in this area.
*/
public boolean hasPoints
() {
return nActivePoints
> 0;
}
/**
* True if there are active indexed points in the area.
* @return True if any active indexed points in the area.
*/
public boolean hasIndPoints
() {
return nActiveIndPoints
> 0;
}
/**
* True if there are any 'active' points in this area. Ie ones that will be
* shown because their resolution is at least as high as that of the
* area.
*
* @return True if any active points in this area.
*/
public boolean hasLines
() {
return nActiveLines
> 0;
}
/**
* Return number of lines in this area.
*/
public int getNumLines
() {
return nActiveLines
;
}
/**
* Return number of shapes in this area.
*/
public int getNumShapes
() {
return nActiveShapes
;
}
/**
* Return number of points in this area.
*/
public int getNumPoints
() {
return nActivePoints + nActiveIndPoints
;
}
/**
* True if there are any 'active' points in this area. Ie ones that will be
* shown because their resolution is at least as high as that of the
* area.
*
* @return True if any active points in this area.
*/
public boolean hasShapes
() {
return nActiveShapes
> 0;
}
/**
* Add an estimate of the size that will be required to hold this element
* if it should be displayed at the given resolution. We also keep track
* of the number of <i>active</i> elements here ie elements that will be
* shown because they are at a resolution at least as great as the resolution
* of the area.
*
* @param p The element containing the minimum resolution that it will be
* displayed at.
* @param kind What kind of element this is KIND_POINT etc.
*/
private void addSize
(MapElement p,
int kind
) {
int res = p.
getMinResolution();
if (res
> MAX_RESOLUTION
)
return;
int numPoints
;
int numElements
;
switch (kind
) {
case POINT_KIND:
case XT_POINT_KIND:
if(res
<= areaResolution
) {
// Points are predictably less than 9 bytes.
sizes
[kind
] +=
9;
if(!p.
hasExtendedType()) {
if(((MapPoint
) p
).
isCity())
nActiveIndPoints++
;
else
nActivePoints++
;
}
}
break;
case LINE_KIND:
case XT_LINE_KIND:
if(res
<= areaResolution
) {
// Estimate the size taken by lines and shapes as a constant plus
// a factor based on the number of points.
numPoints =
((MapLine
) p
).
getPoints().
size();
numElements =
1 +
((numPoints -
1) / LineSplitterFilter.
MAX_POINTS_IN_LINE);
sizes
[kind
] += numElements
* 11 + numPoints
* 4;
if (!p.
hasExtendedType())
nActiveLines += numElements
;
}
break;
case SHAPE_KIND:
case XT_SHAPE_KIND:
if(res
<= areaResolution
) {
// Estimate the size taken by lines and shapes as a constant plus
// a factor based on the number of points.
numPoints =
((MapLine
) p
).
getPoints().
size();
numElements =
1 +
((numPoints -
1) / PolygonSplitterFilter.
MAX_POINT_IN_ELEMENT);
sizes
[kind
] += numElements
* 11 + numPoints
* 4;
if (!p.
hasExtendedType())
nActiveShapes += numElements
;
}
break;
default:
log.
error("should not be here");
assert false;
break;
}
}
/**
* Add a single point to this area.
*
* @param p The point to add.
*/
private void addPoint
(MapPoint p
) {
points.
add(p
);
addToBounds
(p.
getLocation());
addSize
(p, p.
hasExtendedType()? XT_POINT_KIND : POINT_KIND
);
}
/**
* Add a single line to this area.
*
* @param l The line to add.
*/
private void addLine
(MapLine l
) {
lines.
add(l
);
addToBounds
(l.
getBounds());
addSize
(l, l.
hasExtendedType()? XT_LINE_KIND : LINE_KIND
);
}
/**
* Add a single shape to this map area.
*
* @param s The shape to add.
*/
private void addShape
(MapShape s
) {
shapes.
add(s
);
addToBounds
(s.
getBounds());
addSize
(s, s.
hasExtendedType()? XT_SHAPE_KIND : SHAPE_KIND
);
}
/**
* Add to the bounds of this area. That is the new bounds
* for this area will cover the existing ones plus the new
* area.
*
* @param a Area to add into this map area.
*/
private void addToBounds
(Area a
) {
int l = a.
getMinLat();
if (l
< minLat
)
minLat = l
;
l = a.
getMaxLat();
if (l
> maxLat
)
maxLat = l
;
l = a.
getMinLong();
if (l
< minLon
)
minLon = l
;
l = a.
getMaxLong();
if (l
> maxLon
)
maxLon = l
;
}
private void addToBounds
(Coord co
) {
int l = co.
getLatitude();
if (l
< minLat
)
minLat = l
;
if (l
> maxLat
)
maxLat = l
;
l = co.
getLongitude();
if (l
< minLon
)
minLon = l
;
if (l
> maxLon
)
maxLon = l
;
}
/**
* Out of all the available areas, it picks the one that the map element
* should be placed into.
*
* Since we know how the area is divided (equal sizes) we can work out
* which one it fits into without stepping through them all and checking
* coordinates.
*
* @param areas The available areas to choose from.
* @param e The map element.
* @param xbase30 The 30-bit x coord at the origin
* @param ybase30 The 30-bit y coord of the origin
* @param nx number of divisions.
* @param ny number of divisions in y.
* @param dx30 The size of each division (x direction)
* @param dy30 The size of each division (y direction)
* @return The index to areas where the map element fits.
*/
private int pickArea
(MapArea
[] areas, MapElement e,
int xbase30,
int ybase30,
int nx,
int ny,
int dx30,
int dy30
)
{
int x = e.
getLocation().
getHighPrecLon();
int y = e.
getLocation().
getHighPrecLat();
int xcell =
(x - xbase30
) / dx30
;
int ycell =
(y - ybase30
) / dy30
;
if (xcell
< 0) {
log.
info("xcell was", xcell,
"x", x,
"xbase", xbase30
);
xcell =
0;
}
if (ycell
< 0) {
log.
info("ycell was", ycell,
"y", y,
"ybase", ybase30
);
ycell =
0;
}
if (xcell
>= nx
)
xcell = nx -
1;
if (ycell
>= ny
)
ycell = ny -
1;
if (log.
isDebugEnabled()) {
log.
debug("adding", e.
getLocation(),
"to", xcell,
"/", ycell,
areas
[xcell
* ny + ycell
].
getBounds());
}
return xcell
* ny + ycell
;
}
}