Subversion Repositories splitter

/*
 * Copyright (c) 2009.
 *
 * 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;

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.regex.Pattern;

/**
 * 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 final 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)) == false)
                        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()) == false){
                                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) == false){
                                        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)));
                        }
                }
                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 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());
                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');
                        f.write(collectorBounds.getMinLat() + "," + collectorBounds.getMinLong() + "," + collectorBounds.getMaxLat() + "," + collectorBounds.getMaxLong() + '\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++){
                                                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){
                                        System.out.println("Error: Invalid format in map file, line number " + 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){
                                items = csvSplitter.split(inLine);
                                if (items.length != 4){
                                        System.out.println("Error: Invalid format in map file, line number " + 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) {
                                        System.out.println("Error: Invalid format in map file, line number " + 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;
        }

        public Area getArea(int x, int y, int width2, int height2) {
                assert x >= 0;
                assert y >= 0;
                assert width2 > 0;
                assert height2 > 0;
                Area area = new Area(yToLat(y),xToLon(x),yToLat(y+height2),xToLon(x+width2));
                return area;
        }

        /**
         * 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)) == false) {
                        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;
                if (maxY == height)
                        --maxY;
                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;
                        }
                }
                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;
                                        if (seaCount > 0){
                                                col[y] = seaCount;
                                                totalNodeCount += seaCount;
                                                addedSeaNodes += seaCount;
                                        }
                                }
                        }
                }
                System.out.println("Added " + addedSeaNodes + " nodes from precompiled sea data.");
        }
}