Subversion Repositories splitter

Rev

Rev 643 | Blame | Compare with Previous | Last modification | View Log | RSS feed

/*
 * 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;
        }
       
}