Rev 4594 | Blame | Compare with Previous | Last modification | View Log | RSS feed
/*
* 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.Arrays;
import java.util.Collections;
import java.util.List;
import it.unimi.dsi.fastutil.longs.Long2ObjectOpenHashMap;
import uk.me.parabola.imgfmt.app.Area;
import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.imgfmt.app.net.RoadNetwork;
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.PredictFilterPoints;
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.util.ShapeSplitter;
/**
* 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 MAX_RESOLUTION = 24;
private static final int LARGE_OBJECT_DIM = 8192;
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 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<>();
private final List<MapLine> lines = new ArrayList<>();
private final List<MapShape> shapes = new ArrayList<>();
// 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 int areaResolution;
private final boolean splitPolygonsIntoArea;
private int splittableCount;
private Long2ObjectOpenHashMap<Coord> areasHashMap;
/**
* 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.
* @param splitPolygonsIntoArea aligns subareas as powerOf2 and splits polygons into the subareas.
*/
public MapArea(MapDataSource src, int resolution, boolean splitPolygonsIntoArea) {
this.areaResolution = 0; // don't want addSize() to gather information for this MapArea
this.bounds = src.getBounds();
this.splitPolygonsIntoArea = splitPolygonsIntoArea;
for (MapPoint p : src.getPoints()) {
if (p.getMaxResolution() < resolution)
continue;
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 = " + areaResolution);
}
addLines(src, resolution);
addPolygons(src, resolution);
this.areaResolution = resolution;
}
/**
* Add the polygons
* @param src The map data.
* @param resolution The current resolution of the layer.
*/
private void addPolygons(MapDataSource src, final int resolution) {
for (MapShape s : src.getShapes()) {
if (s.getMaxResolution() < resolution)
continue;
addShape(s);
}
}
/**
* 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 = element -> addLine((MapLine) element);
LineSizeSplitterFilter filter = new LineSizeSplitterFilter();
FilterConfig config = new FilterConfig();
config.setResolution(resolution);
config.setBounds(bounds);
filter.init(config);
for (MapLine l : src.getLines()) {
if (l.getMaxResolution() < resolution)
continue;
// %%% ??? if not appearing at this level no need to filter
filter.doFilter(l, chain);
}
}
/**
* Create an map area with the given initial bounds.
*
* @param area The bounds for this area.
* @param resolution The minimum resolution for this area.
* @param splitPolygonsIntoArea splits polygons into the subareas.
*/
private MapArea(Area area, int resolution, boolean splitPolygonsIntoArea) {
bounds = area;
areaResolution = resolution;
this.splitPolygonsIntoArea = splitPolygonsIntoArea;
}
/**
* 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.
* <p>
* This code is dealing with a lot of factors that govern the splitting, eg:
* splitPolygonsIntoArea,
* tooSmallToDivide,
* item.minResolution vs. areaResolution,
* number/size of items and the limits of a subDivision,
* items that exceed maximum subDivision on their own,
* items that extend up to 50% outside the current area,
* items bigger than this.
*
* @param nx The number of pieces in the x (longitude) direction.
* @param ny The number of pieces in the y direction.
* @param bounds the bounding box that is used to create the areas.
* @param tooSmallToDivide the area is small and data overflows; split into overflow areas
*
* @return An array of the new MapArea's or null if can't split.
*/
public MapArea[] split(int nx, int ny, Area bounds, boolean tooSmallToDivide) {
int resolutionShift = MAX_RESOLUTION - areaResolution;
Area[] areas = bounds.split(nx, ny, resolutionShift);
if (areas == null) { // Failed to split!
if (log.isDebugEnabled()) { // see what is here
for (MapLine e : this.lines)
if (e.getMinResolution() <= areaResolution)
log.debug("line. locn=", e.getPoints().get(0).toOSMURL(),
" type=", uk.me.parabola.mkgmap.reader.osm.GType.formatType(e.getType()),
" name=", e.getName(), "min=", e.getMinResolution(), "max=", e.getMaxResolution());
for (MapShape e : this.shapes)
if (e.getMinResolution() <= areaResolution)
log.debug("shape. locn=", e.getPoints().get(0).toOSMURL(),
" type=", uk.me.parabola.mkgmap.reader.osm.GType.formatType(e.getType()),
" name=", e.getName(), "min=", e.getMinResolution(), "max=", e.getMaxResolution(),
" full=", e.getFullArea(),
" calc=", uk.me.parabola.mkgmap.filters.ShapeMergeFilter.calcAreaSizeTestVal(e.getPoints()));
// the main culprits are lots of bits of sea and coastline in an overview map (res 12)
}
return null;
}
MapArea[] mapAreas = new MapArea[nx * ny];
log.info("Splitting area " + bounds + " into " + nx + "x" + ny + " pieces at resolution " + areaResolution, tooSmallToDivide);
List<MapArea> addedAreas = new ArrayList<>();
for (int i = 0; i < mapAreas.length; i++) {
mapAreas[i] = new MapArea(areas[i], areaResolution, splitPolygonsIntoArea);
if (log.isDebugEnabled())
log.debug("area before", mapAreas[i].getBounds());
}
int xbaseHp = areas[0].getMinLong() << Coord.DELTA_SHIFT;
int ybaseHp = areas[0].getMinLat() << Coord.DELTA_SHIFT;
int dxHp = areas[0].getWidth() << Coord.DELTA_SHIFT;
int dyHp = areas[0].getHeight() << Coord.DELTA_SHIFT;
// Some of the work done by PolygonSubdivSizeSplitterFilter now done here
final int maxSize = Math.min((1<<24)-1, Math.max(MapSplitter.MAX_DIVISION_SIZE << (MAX_RESOLUTION - areaResolution), 0x8000));
/**
* These constants control when an item (shape unless splitPolygonsIntoArea or line) is shifted into its own MapArea/SubDivision.
* Generally, an item is allowed into the MapArea chosen by centre provided it is no bigger than the MapArea.
* This means that there could be big items near the edges of the MapArea that stick out by almost half, so must
* ensure that this doesn't cause the mapArea to exceed subDivision size limits.
* When the MapArea get small, we don't want to shift lots if items into their own areas;
* The *2 of LARGE_OBJECT_DIM is to keep to the same behaviour as earlier versions.
*/
final int maxWidth = Math.max(Math.min(areas[0].getWidth(), maxSize/2), LARGE_OBJECT_DIM*2);
final int maxHeight = Math.max(Math.min(areas[0].getHeight(), maxSize/2), LARGE_OBJECT_DIM*2);
// Now sprinkle each map element into the correct map area.
// do shapes first because want these to define the primary area
// and don't have a good tooSmallToDivide strategy when not splitPolygonsIntoArea.
if (tooSmallToDivide) {
distShapesIntoNewAreas(addedAreas, mapAreas[0]);
} else {
for (MapShape e : this.shapes) {
Area shapeBounds = e.getBounds();
if (splitPolygonsIntoArea || shapeBounds.getMaxDimension() > maxSize) {
splitIntoAreas(mapAreas, e);
continue;
}
int areaIndex = pickArea(mapAreas, e, xbaseHp, ybaseHp, nx, ny, dxHp, dyHp);
if (areas[areaIndex].contains(shapeBounds)) {
mapAreas[areaIndex].addShape(e);
} else if (shapeBounds.getHeight() <= maxHeight && shapeBounds.getWidth() <= maxWidth) {
// this polygon is partially outside the subdivision, but won't exceed the allowable offsets
mapAreas[areaIndex].addShape(e);
} else {
MapArea largeObjectArea = new MapArea(shapeBounds, areaResolution, true); // use splitIntoAreas to deal with overflow
largeObjectArea.addShape(e);
addedAreas.add(largeObjectArea);
}
}
}
if (tooSmallToDivide) {
distPointsIntoNewAreas(addedAreas, mapAreas[0]);
} else {
for (MapPoint p : this.points) {
int areaIndex = pickArea(mapAreas, p, xbaseHp, ybaseHp, nx, ny, dxHp, dyHp);
mapAreas[areaIndex].addPoint(p);
}
}
if (tooSmallToDivide) {
distLinesIntoNewAreas(addedAreas, mapAreas[0]);
} else {
for (MapLine l : this.lines) {
// Drop any zero sized lines.
if (!(l instanceof MapRoad) && l.getRect().height <= 0 && l.getRect().width <= 0)
continue;
Area lineBounds = l.getBounds();
int areaIndex = pickArea(mapAreas, l, xbaseHp, ybaseHp, nx, ny, dxHp, dyHp);
if ((lineBounds.getHeight() > maxHeight || lineBounds.getWidth() > maxWidth) &&
!areas[areaIndex].contains(lineBounds)) {
MapArea largeObjectArea = new MapArea(lineBounds, areaResolution, false);
largeObjectArea.addLine(l);
addedAreas.add(largeObjectArea);
continue;
}
mapAreas[areaIndex].addLine(l);
}
}
if (!addedAreas.isEmpty()) {
// combine list and array
int pos = mapAreas.length;
mapAreas = Arrays.copyOf(mapAreas, mapAreas.length + addedAreas.size());
for (MapArea ma : addedAreas) {
if (ma.getBounds() == null) // distShapesIntoNewAreas etc didn't know how big it was going to be
ma.setBounds(ma.getFullBounds()); // so set to bounds of all elements
mapAreas[pos++] = ma;
}
}
return mapAreas;
}
private void distPointsIntoNewAreas(List<MapArea> addedAreas, MapArea primaryArea) {
MapArea extraArea = primaryArea;
for (MapPoint p : this.points)
if (p.getMinResolution() > areaResolution) // doesn't add to subDivision
primaryArea.addPoint(p);
else {
if (!extraArea.canAddSize(p, POINT_KIND)) {
extraArea = new MapArea((Area)null, areaResolution, false);
addedAreas.add(extraArea);
}
extraArea.addPoint(p);
}
}
private void distLinesIntoNewAreas(List<MapArea> addedAreas, MapArea primaryArea) {
MapArea extraArea = primaryArea;
for (MapLine l : this.lines)
if (l.getMinResolution() > areaResolution) // doesn't add to subDivision
primaryArea.addLine(l);
else {
if (!extraArea.canAddSize(l, LINE_KIND)) {
extraArea = new MapArea((Area)null, areaResolution, false);
addedAreas.add(extraArea);
}
extraArea.addLine(l);
}
}
private void distShapesIntoNewAreas(List<MapArea> addedAreas, MapArea primaryArea) {
MapArea extraArea = primaryArea;
for (MapShape e : this.shapes)
if (e.getMinResolution() > areaResolution) // doesn't add to subDivision
primaryArea.addShape(e);
else {
if (!extraArea.canAddSize(e, SHAPE_KIND)) {
extraArea = new MapArea((Area)null, areaResolution, true); // use splitIntoAreas to deal with overflow
addedAreas.add(extraArea);
}
extraArea.addShape(e);
}
}
/**
* 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;
}
/**
* override the initial bounds of this area.
*/
public void setBounds(Area actualBounds) {
this.bounds = actualBounds;
}
/**
* 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;
}
/**
* Can this area be split (in a way that reduces subDivision content)?
*
* If more than one item (point/line/shape) to be shown at this resolution then yes.
* Must use count of items rather than the sum of numElements that addSize() estimates
* because these are generated by later filters after the contents of the subDivision
* has been set.
*
* A single shape is considered splittable because it will end up in a splitPolygonsIntoArea
* area and this can then be divided down to <= MIN_DIMENSION(=10) pixel rectangle;
* so, if, somehow, the shape passed through every pixel that would be 100 points, well
* below MAX_POINTS_IN_ELEMENT, MAX_RNG_SIZE, MAX_XT_SHAPE_SIZE
*/
public boolean canSplit() {
return splittableCount > 1;
}
/**
* 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 el 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 el, int kind) {
final int res = el.getMinResolution();
if (res > areaResolution || res > MAX_RESOLUTION)
return;
++splittableCount;
final int numPoints;
final int numElements;
switch (kind) {
case POINT_KIND:
case XT_POINT_KIND:
// Points are predictably less than 10 bytes.
sizes[kind] += 9;
if(!el.hasExtendedType()) {
if(((MapPoint) el).isCity())
nActiveIndPoints++;
else
nActivePoints++;
}
break;
case LINE_KIND:
case XT_LINE_KIND:
// Estimate the size taken by lines and shapes as a constant plus
// a factor based on the number of points.
numPoints = PredictFilterPoints.predictedMaxNumPoints(((MapLine) el).getPoints(), areaResolution,
// assume MapBuilder.doRoads is true. subDiv.getZoom().getLevel() == 0 is maximum resolution
((MapLine) el).isRoad() && areaResolution == MAX_RESOLUTION);
if (numPoints <= 1 && !((MapLine) el).isRoad())
return;
numElements = 1 + ((numPoints - 1) / LineSplitterFilter.MAX_POINTS_IN_LINE);
sizes[kind] += numElements * 11 + numPoints * 4; // very pessimistic, typically less than 2 bytes are needed for one point
if (!el.hasExtendedType())
nActiveLines += numElements;
break;
case SHAPE_KIND:
case XT_SHAPE_KIND:
++splittableCount; // see canSplit() above
// Estimate the size taken by lines and shapes as a constant plus
// a factor based on the number of points.
numPoints = PredictFilterPoints.predictedMaxNumPoints(((MapShape) el).getPoints(), areaResolution, false);
if (numPoints <= 3)
return;
numElements = 1 + ((numPoints - 1) / PolygonSplitterFilter.MAX_POINT_IN_ELEMENT);
sizes[kind] += numElements * 11 + numPoints * 4; // very pessimistic, typically less than 2 bytes are needed for one point
if (!el.hasExtendedType())
nActiveShapes += numElements;
break;
default:
log.error("should not be here");
assert false;
break;
}
}
/**
* Will element fit nicely?
* Limit to WANTED_MAX_AREA_SIZE which is smaller than MAX_XT_xxx_SIZE
* so don't need to check down to the last detail
*
* @param el The element. Assume want to display it at this resolution
* @param kind What kind of element this is: KIND_POINT/LINE/SHAPE.
*/
private boolean canAddSize(MapElement el, int kind) {
final int numPoints;
final int numElements;
int sumSize = 0;
for (int s : sizes)
sumSize += s;
switch (kind) {
case POINT_KIND:
if (getNumPoints() >= MapSplitter.MAX_NUM_POINTS)
return false;
// Points are predictably less than 10 bytes.
if ((sumSize + 9) > MapSplitter.WANTED_MAX_AREA_SIZE)
return false;
break;
case LINE_KIND:
// Estimate the size taken by lines and shapes as a constant plus
// a factor based on the number of points.
numPoints = PredictFilterPoints.predictedMaxNumPoints(((MapLine) el).getPoints(), areaResolution,
// assume MapBuilder.doRoads is true. subDiv.getZoom().getLevel() == 0 is maximum resolution
((MapLine) el).isRoad() && areaResolution == MAX_RESOLUTION);
if (numPoints <= 1 && !((MapLine) el).isRoad())
break;
numElements = 1 + ((numPoints - 1) / LineSplitterFilter.MAX_POINTS_IN_LINE);
if (getNumLines() + numElements > MapSplitter.MAX_NUM_LINES)
return false;
// very pessimistic, typically less than 2 bytes are needed for one point
if ((sumSize + numElements * 11 + numPoints * 4) > MapSplitter.WANTED_MAX_AREA_SIZE)
return false;
break;
case SHAPE_KIND:
// Estimate the size taken by lines and shapes as a constant plus
// a factor based on the number of points.
numPoints = PredictFilterPoints.predictedMaxNumPoints(((MapShape) el).getPoints(), areaResolution, false);
if (numPoints <= 3)
break;
numElements = 1 + ((numPoints - 1) / PolygonSplitterFilter.MAX_POINT_IN_ELEMENT);
// very pessimistic, typically less than 2 bytes are needed for one point
if ((sumSize + numElements * 11 + numPoints * 4) > MapSplitter.WANTED_MAX_AREA_SIZE)
return false;
break;
}
return true;
}
/**
* 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;
}
/**
* Add to bounds considering high precision values.
* @param co
*/
private void addToBounds(Coord co) {
int latHp = co.getHighPrecLat();
int latLower = latHp >> Coord.DELTA_SHIFT;
int latUpper = (latLower << Coord.DELTA_SHIFT) < latHp ? latLower + 1 : latLower;
if (latLower < minLat)
minLat = latLower;
if (latUpper > maxLat)
maxLat = latUpper;
int lonHp = co.getHighPrecLon();
int lonLeft = lonHp >> Coord.DELTA_SHIFT;
int lonRight = (lonLeft << Coord.DELTA_SHIFT) < lonHp ? lonLeft + 1 : lonLeft;
if (lonLeft < minLon)
minLon = lonLeft;
if (lonRight > maxLon)
maxLon = lonRight;
}
/**
* 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 xbaseHp The high-precision x coord at the origin
* @param ybaseHp The high-precision y coord of the origin
* @param nx number of divisions.
* @param ny number of divisions in y.
* @param dxHp The size of each division (x direction)
* @param dyHp The size of each division (y direction)
* @return The index to areas where the map element fits.
*/
private static int pickArea(MapArea[] areas, MapElement e,
int xbaseHp, int ybaseHp,
int nx, int ny,
int dxHp, int dyHp)
{
int x = e.getLocation().getHighPrecLon();
int y = e.getLocation().getHighPrecLat();
int xcell = (x - xbaseHp) / dxHp;
int ycell = (y - ybaseHp) / dyHp;
if (xcell < 0) {
log.info("xcell was", xcell, "x", x, "xbase", xbaseHp);
xcell = 0;
}
if (ycell < 0) {
log.info("ycell was", ycell, "y", y, "ybase", ybaseHp);
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;
}
/**
* Spit the polygon into areas
*
* @param areas The available areas to choose from.
* @param e The map element.
* @param used flag vector to say area has been added to.
*/
private void splitIntoAreas(MapArea[] areas, MapShape e)
{
if (areas.length == 1) { // this happens quite a lot
areas[0].addShape(e);
return;
}
// quick check if bbox of shape lies fully inside one of the areas
Area shapeBounds = e.getBounds();
// this is worked out at standard precision, along with Area.contains() and so can get
// tricky problems as it might not really be fully within the area.
// so: pretend the shape is a touch bigger. Will get the optimisation most of the time
// and in the boundary cases will fall into the precise code.
int xtra = 2;
// However, if the shape is significantly larger than the error margin (ie most of it
// should be in this area) I don't see any problem in letting it expand a little bit out
// of the area.
// This avoids very small polygons being left in the adjacent areas, which ShapeMergeFilter
// notices with an debug message and then output filters probably chuck away.
if (Math.min(shapeBounds.getWidth(), shapeBounds.getHeight()) > 8)
xtra = -2; // pretend shape is smaller
shapeBounds = new Area(shapeBounds.getMinLat()-xtra,
shapeBounds.getMinLong()-xtra,
shapeBounds.getMaxLat()+xtra,
shapeBounds.getMaxLong()+xtra);
for (int areaIndex = 0; areaIndex < areas.length; ++areaIndex) {
if (areas[areaIndex].getBounds().contains(shapeBounds)) {
areas[areaIndex].addShape(e);
return;
}
}
// Shape crosses area(s), we have to split it
if (areasHashMap == null)
areasHashMap = new Long2ObjectOpenHashMap<>();
int stepLat = 0;
if (areas[0].getBounds().getMaxLat() == areas[1].getBounds().getMinLat())
stepLat = 1;
else if (areas[0].getBounds().getMaxLong() == areas[1].getBounds().getMinLong())
stepLat = areas.length; // assume single row
else
log.error("SplitIntoAreas expects shared edge between the subDivs");
if (stepLat != 0) {
int dimLat = stepLat == 1 ? areas.length : 1; // preset presuming single row or column
// search for conflict with assumption of single row/col to determine grid dimension
for (int areaIndex = 2; areaIndex < areas.length; ++areaIndex) {
if (stepLat == 1) {
if (areas[areaIndex-1].getBounds().getMaxLat() != areas[areaIndex].getBounds().getMinLat()) {
dimLat = areaIndex;
break;
}
} else {
if (areas[areaIndex-1].getBounds().getMaxLong() != areas[areaIndex].getBounds().getMinLong()) {
stepLat = areaIndex;
dimLat = areas.length / areaIndex;
break;
}
}
}
splitIntoRows(e, areas, stepLat, dimLat, areasHashMap);
return;
}
for (int areaIndex = 0; areaIndex < areas.length; ++areaIndex) {
List<List<Coord>> subShapePoints = ShapeSplitter.clipToBounds(e.getPoints(), areas[areaIndex].getBounds(), areasHashMap);
for (List<Coord> subShape : subShapePoints) {
MapShape s = e.copy();
s.setPoints(subShape);
s.setClipped(true);
areas[areaIndex].addShape(s);
}
}
}
private static void splitIntoRows(MapShape e, MapArea[] areas, int stepLat, int dimLat, Long2ObjectOpenHashMap<Coord> areasHashMap) {
final int dimLong = areas.length / dimLat;
final int stepLong = stepLat == 1 ? dimLat : 1;
List<List<Coord>> pendList = Collections.singletonList(e.getPoints());
for (int inx = 1; inx < dimLat; ++inx) {
int areaIndex = inx * stepLat;
int dividingLine = areas[areaIndex].getBounds().getMinLat();
List<List<Coord>> lessList = new ArrayList<>(), moreList = new ArrayList<>();
for (List<Coord> subShape : pendList)
ShapeSplitter.splitShape(subShape, dividingLine << Coord.DELTA_SHIFT, false, lessList, moreList, areasHashMap);
if (!lessList.isEmpty())
splitIntoCols(lessList, areas, areaIndex-stepLat, stepLong, dimLong, areasHashMap, e);
if (moreList.isEmpty())
return;
pendList = moreList;
}
splitIntoCols(pendList, areas, (dimLat-1)*stepLat, stepLong, dimLong, areasHashMap, e);
}
private static void splitIntoCols(List<List<Coord>> rowList, MapArea[] areas, int startInx, int stepLong, int dimLong, Long2ObjectOpenHashMap<Coord> areasHashMap, MapShape template) {
List<List<Coord>> pendList = rowList;
for (int inx = 1; inx < dimLong; ++inx) {
int areaIndex = startInx + inx * stepLong;
int dividingLine = areas[areaIndex].getBounds().getMinLong();
List<List<Coord>> lessList = new ArrayList<>(), moreList = new ArrayList<>();
for (List<Coord> subShape : pendList)
ShapeSplitter.splitShape(subShape, dividingLine << Coord.DELTA_SHIFT, true, lessList, moreList, areasHashMap);
if (!lessList.isEmpty())
saveParts(lessList, areas[areaIndex-stepLong], template);
if (moreList.isEmpty())
return;
pendList = moreList;
}
saveParts(pendList, areas[startInx+(dimLong-1)*stepLong], template);
}
private static void saveParts(List<List<Coord>> cellList, MapArea area, MapShape template) {
for (List<Coord> subShape : cellList) {
MapShape s = template.copy();
s.setPoints(subShape);
s.setClipped(true);
area.addShape(s);
}
}
/**
* @return true if this area contains any data
*/
public boolean hasData() {
return !points.isEmpty() || !lines.isEmpty() || !shapes.isEmpty();
}
@Override
public String toString() {
return "MapArea [res=" + areaResolution + ", width=" + bounds.getWidth() + ", height=" + bounds.getHeight()
+ ", sizes=" + Arrays.toString(sizes) + "]";
}
}