Rev 480 | Blame | Compare with Previous | Last modification | View Log | RSS feed
/** Copyright (c) 2016, Gerd Petermann** 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.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.io.PrintWriter;import java.util.ArrayList;import java.util.Iterator;import java.util.List;import java.util.Set;import java.util.TreeSet;import java.util.regex.Pattern;import it.unimi.dsi.fastutil.longs.LongArrayList;import uk.me.parabola.splitter.args.SplitterParams;public class ProblemLists {private final LongArrayList problemWays = new LongArrayList();private final LongArrayList problemRels = new LongArrayList();private final TreeSet<Long> calculatedProblemWays = new TreeSet<>();private final TreeSet<Long> calculatedProblemRels = new TreeSet<>();/*** Calculate lists of ways and relations that appear in multiple areas for a* given list of areas.* @param osmFileHandler* @param realAreas list of areas, possibly overlapping if read from split-file* @param overlapAmount* @param mainOptions main options* @return*/public DataStorer calcProblemLists(OSMFileHandler osmFileHandler, List<Area> realAreas, int overlapAmount, SplitterParams mainOptions) {long startProblemListGenerator = System.currentTimeMillis();ArrayList<Area> distinctAreas = getNonOverlappingAreas(realAreas);if (distinctAreas.size() > realAreas.size()) {System.err.println("Waring: The areas given in --split-file are overlapping.");Set<Integer> overlappingTiles = new TreeSet<>();for (int i = 0; i < realAreas.size(); i++) {Area a1 = realAreas.get(i);for (int j = i + 1; j < realAreas.size(); j++) {Area a2 = realAreas.get(j);if (a1.intersects(a2)) {overlappingTiles.add(a1.getMapId());overlappingTiles.add(a2.getMapId());}}}if (!overlappingTiles.isEmpty()) {System.out.println("Overlaping tiles: " + overlappingTiles.toString());}}System.out.println("Generating problem list for " + distinctAreas.size() + " distinct areas");List<Area> workAreas = addPseudoAreas(distinctAreas);int numPasses = (int) Math.ceil((double) workAreas.size() / mainOptions.getMaxAreas());int areasPerPass = (int) Math.ceil((double) workAreas.size() / numPasses);if (numPasses > 1) {System.out.println("Processing " + distinctAreas.size() + " areas in " + numPasses + " passes, "+ areasPerPass + " areas at a time");} else {System.out.println("Processing " + distinctAreas.size() + " areas in a single pass");}ArrayList<Area> allAreas = new ArrayList<>();System.out.println("Pseudo areas:");for (int j = 0; j < workAreas.size(); j++) {Area area = workAreas.get(j);allAreas.add(area);if (area.isPseudoArea())System.out.println("Pseudo area " + area.getMapId() + " covers " + area);}DataStorer distinctDataStorer = new DataStorer(workAreas, overlapAmount);System.out.println("Starting problem-list-generator pass(es)");for (int pass = 0; pass < numPasses; pass++) {System.out.println("-----------------------------------");System.out.println("Starting problem-list-generator pass " + (pass + 1) + " of " + numPasses);long startThisPass = System.currentTimeMillis();int areaOffset = pass * areasPerPass;int numAreasThisPass = Math.min(areasPerPass, workAreas.size() - pass * areasPerPass);ProblemListProcessor processor = new ProblemListProcessor(distinctDataStorer, areaOffset, numAreasThisPass,mainOptions);boolean done = false;while (!done) {done = osmFileHandler.execute(processor);calculatedProblemWays.addAll(processor.getProblemWays());calculatedProblemRels.addAll(processor.getProblemRels());}System.out.println("Problem-list-generator pass " + (pass + 1) + " took "+ (System.currentTimeMillis() - startThisPass) + " ms");}System.out.println("Problem-list-generator pass(es) took "+ (System.currentTimeMillis() - startProblemListGenerator) + " ms");DataStorer dataStorer = new DataStorer(realAreas, overlapAmount);dataStorer.translateDistinctToRealAreas(distinctDataStorer);return dataStorer;}/** Read user defined problematic relations and ways */public boolean readProblemIds(String problemFileName) {File fProblem = new File(problemFileName);boolean ok = true;if (!fProblem.exists()) {System.out.println("Error: problem file doesn't exist: " + fProblem);return false;}try (InputStream fileStream = new FileInputStream(fProblem);LineNumberReader problemReader = new LineNumberReader(new InputStreamReader(fileStream));) {Pattern csvSplitter = Pattern.compile(Pattern.quote(":"));Pattern commentSplitter = Pattern.compile(Pattern.quote("#"));String problemLine;String[] items;while ((problemLine = problemReader.readLine()) != null) {items = commentSplitter.split(problemLine);if (items.length == 0 || items[0].trim().isEmpty()) {// comment or empty linecontinue;}items = csvSplitter.split(items[0].trim());if (items.length != 2) {System.out.println("Error: Invalid format in problem file, line number "+ problemReader.getLineNumber() + ": " + problemLine);ok = false;continue;}long id = 0;try {id = Long.parseLong(items[1]);} catch (NumberFormatException exp) {System.out.println("Error: Invalid number format in problem file, line number "+ +problemReader.getLineNumber() + ": " + problemLine + exp);ok = false;}if ("way".equals(items[0]))problemWays.add(id);else if ("rel".equals(items[0]))problemRels.add(id);else {System.out.println("Error in problem file: Type not way or relation, line number "+ +problemReader.getLineNumber() + ": " + problemLine);ok = false;}}} catch (IOException exp) {System.out.println("Error: Cannot read problem file " + fProblem + exp);return false;}return ok;}/*** Write a file that can be given to mkgmap that contains the correct* arguments for the split file pieces. You are encouraged to edit the file* and so it contains a template of all the arguments that you might want to* use.** @param problemRelsThisPass* @param problemWaysThisPass*/public void writeProblemList(File fileOutputDir, String fname) {try (PrintWriter w = new PrintWriter(new FileWriter(new File(fileOutputDir, fname)));) {w.println("#");w.println("# This file can be given to splitter using the --problem-file option");w.println("#");w.println("# List of relations and ways that are known to cause problems");w.println("# in splitter or mkgmap");w.println("# Objects listed here are specially treated by splitter to assure");w.println("# that complete data is written to all related tiles");w.println("# Format:");w.println("# way:<id>");w.println("# rel:<id>");w.println("# ways");for (long id : calculatedProblemWays) {w.println("way: " + id + " #");}w.println("# rels");for (long id : calculatedProblemRels) {w.println("rel: " + id + " #");}w.println();} catch (IOException e) {System.err.println("Warning: Could not write problem-list file " + fname + ", processing continues");}}/*** Calculate writers for elements which cross areas.** @param dataStorer* stores data that is needed in different passes of the program.* @param osmFileHandler* used to access OSM input files*/public void calcMultiTileElements(DataStorer dataStorer, OSMFileHandler osmFileHandler) {// merge the calculated problem ids and the user given problem idsproblemWays.addAll(calculatedProblemWays);problemRels.addAll(calculatedProblemRels);calculatedProblemRels.clear();calculatedProblemWays.clear();if (problemWays.isEmpty() && problemRels.isEmpty())return;// calculate which ways and relations are written to multiple areas.MultiTileProcessor multiProcessor = new MultiTileProcessor(dataStorer, problemWays, problemRels);// multiTileProcessor stores the problem relations in its own structures// return memory to GCproblemRels.clear();problemWays.clear();problemRels.trim();problemWays.trim();boolean done = false;long startThisPhase = System.currentTimeMillis();int prevPhase = -1;while (!done) {int phase = multiProcessor.getPhase();if (prevPhase != phase) {startThisPhase = System.currentTimeMillis();System.out.println("-----------------------------------");System.out.println("Executing multi-tile analyses phase " + phase);}done = osmFileHandler.execute(multiProcessor);prevPhase = phase;if (done || (phase != multiProcessor.getPhase())) {System.out.println("Multi-tile analyses phase " + phase + " took "+ (System.currentTimeMillis() - startThisPhase) + " ms");}}System.out.println("-----------------------------------");}/*** Make sure that our areas cover the planet. This is done by adding* pseudo-areas if needed.** @param realAreas* list of areas (read from split-file or calculated)* @return new list of areas containing the real areas and additional areas*/public static List<Area> addPseudoAreas(List<Area> realAreas) {ArrayList<Area> areas = new ArrayList<>(realAreas);Rectangle planetBounds = new Rectangle(Utils.toMapUnit(-180.0), Utils.toMapUnit(-90.0),2 * Utils.toMapUnit(180.0), 2 * Utils.toMapUnit(90.0));while (!checkIfCovered(planetBounds, areas)) {boolean changed = addPseudoArea(areas);if (!changed) {throw new SplitFailedException("Failed to fill planet with pseudo-areas");}}return areas;}/*** Work around for possible rounding errors in area.subtract processing** @param area* an area that is considered to be empty or a rectangle* @return*/private static java.awt.geom.Area simplifyArea(java.awt.geom.Area area) {if (area.isEmpty() || area.isRectangular())return area;// area.isRectugular() may returns false although the shape is a// perfect rectangle :-( If we subtract the area from its bounding// box we get better results.java.awt.geom.Area bbox = new java.awt.geom.Area(area.getBounds2D());bbox.subtract(area);if (bbox.isEmpty()) // bbox equals area: is a rectanglereturn new java.awt.geom.Area(area.getBounds2D());return area;}private static boolean checkIfCovered(Rectangle bounds, ArrayList<Area> areas) {java.awt.geom.Area bbox = new java.awt.geom.Area(bounds);long sumTiles = 0;for (Area area : areas) {sumTiles += (long) area.getHeight() * (long) area.getWidth();bbox.subtract(area.getJavaArea());}long areaBox = (long) bounds.height * (long) bounds.width;if (sumTiles != areaBox)return false;return bbox.isEmpty();}/*** Create a list of areas that do not overlap. If areas in the original list* are overlapping, they can be replaced by up to 5 disjoint areas. This is* done if parameter makeDisjoint is true** @param realAreas* the list of areas* @return the new list*/public static ArrayList<Area> getNonOverlappingAreas(final List<Area> realAreas) {java.awt.geom.Area covered = new java.awt.geom.Area();ArrayList<Area> splitList = new ArrayList<>();int artificialId = -99999999;boolean foundOverlap = false;for (Area area1 : realAreas) {Rectangle r1 = area1.getRect();if (covered.intersects(r1) == false) {splitList.add(area1);} else {if (foundOverlap == false) {foundOverlap = true;System.out.println("Removing overlaps from tiles...");}// String msg = "splitting " + area1.getMapId() + " " + (i+1) +// "/" + realAreas.size() + " overlapping ";// find intersecting areas in the already covered partArrayList<Area> splitAreas = new ArrayList<>();for (int j = 0; j < splitList.size(); j++) {Area area2 = splitList.get(j);if (area2 == null)continue;Rectangle r2 = area2.getRect();if (r1.intersects(r2)) {java.awt.geom.Area overlap = new java.awt.geom.Area(area1.getRect());overlap.intersect(area2.getJavaArea());Rectangle ro = overlap.getBounds();if (ro.height == 0 || ro.width == 0)continue;// msg += area2.getMapId() + " ";Area aNew = new Area(ro.y, ro.x, (int) ro.getMaxY(), (int) ro.getMaxX());aNew.setMapId(artificialId++);aNew.setName("" + area1.getMapId());aNew.setJoinable(false);covered.subtract(area2.getJavaArea());covered.add(overlap);splitList.set(j, aNew);java.awt.geom.Area coveredByPair = new java.awt.geom.Area(r1);coveredByPair.add(new java.awt.geom.Area(r2));java.awt.geom.Area originalPair = new java.awt.geom.Area(coveredByPair);int minX = coveredByPair.getBounds().x;int minY = coveredByPair.getBounds().y;int maxX = (int) coveredByPair.getBounds().getMaxX();int maxY = (int) coveredByPair.getBounds().getMaxY();coveredByPair.subtract(overlap);if (coveredByPair.isEmpty())continue; // two equal areas acoveredByPair.subtract(covered);java.awt.geom.Area testSplit = new java.awt.geom.Area(overlap);Rectangle[] rectPair = { r1, r2 };Area[] areaPair = { area1, area2 };int lx = minX;int lw = ro.x - minX;int rx = (int) ro.getMaxX();int rw = maxX - rx;int uy = (int) ro.getMaxY();int uh = maxY - uy;int by = minY;int bh = ro.y - by;Rectangle[] clippers = { new Rectangle(lx, minY, lw, bh), // lower// leftnew Rectangle(ro.x, minY, ro.width, bh), // lower// middlenew Rectangle(rx, minY, rw, bh), // lower rightnew Rectangle(lx, ro.y, lw, ro.height), // leftnew Rectangle(rx, ro.y, rw, ro.height), // rightnew Rectangle(lx, uy, lw, uh), // upper leftnew Rectangle(ro.x, uy, ro.width, uh), // upper// middlenew Rectangle(rx, uy, rw, uh) // upper right};for (Rectangle clipper : clippers) {for (int k = 0; k <= 1; k++) {Rectangle test = clipper.intersection(rectPair[k]);if (!test.isEmpty()) {testSplit.add(new java.awt.geom.Area(test));if (k == 1 || covered.intersects(test) == false) {aNew = new Area(test.y, test.x, (int) test.getMaxY(), (int) test.getMaxX());aNew.setMapId(areaPair[k].getMapId());splitAreas.add(aNew);covered.add(aNew.getJavaArea());}}}}assert testSplit.equals(originalPair);}}// recombine parts that form a rectanglefor (Area splitArea : splitAreas) {if (splitArea.isJoinable()) {for (int j = 0; j < splitList.size(); j++) {Area area = splitList.get(j);if (area == null || area.isJoinable() == false || area.getMapId() != splitArea.getMapId())continue;boolean doJoin = false;if (splitArea.getMaxLat() == area.getMaxLat() && splitArea.getMinLat() == area.getMinLat()&& (splitArea.getMinLong() == area.getMaxLong()|| splitArea.getMaxLong() == area.getMinLong()))doJoin = true;else if (splitArea.getMinLong() == area.getMinLong()&& splitArea.getMaxLong() == area.getMaxLong()&& (splitArea.getMinLat() == area.getMaxLat()|| splitArea.getMaxLat() == area.getMinLat()))doJoin = true;if (doJoin) {splitArea = area.add(splitArea);splitArea.setMapId(area.getMapId());splitList.set(j, splitArea);splitArea = null; // don't add laterbreak;}}}if (splitArea != null) {splitList.add(splitArea);}}/** if (msg.isEmpty() == false) System.out.println(msg);*/}covered.add(new java.awt.geom.Area(r1));}covered.reset();Iterator<Area> iter = splitList.iterator();while (iter.hasNext()) {Area a = iter.next();if (a == null)iter.remove();else {Rectangle r1 = a.getRect();if (covered.intersects(r1) == true) {throw new SplitFailedException("Failed to create list of distinct areas");}covered.add(a.getJavaArea());}}return splitList;}/*** Fill uncovered parts of the planet with pseudo-areas. TODO: check if* better algorithm reduces run time in ProblemListProcessor We want a small* number of pseudo areas because many of them will require more memory or* more passes, esp. when processing whole planet. Also, the total length of* all edges should be small.** @param areas* list of areas (either real or pseudo)* @return true if pseudo-areas were added*/private static boolean addPseudoArea(ArrayList<Area> areas) {int oldSize = areas.size();Rectangle planetBounds = new Rectangle(Utils.toMapUnit(-180.0), Utils.toMapUnit(-90.0),2 * Utils.toMapUnit(180.0), 2 * Utils.toMapUnit(90.0));java.awt.geom.Area uncovered = new java.awt.geom.Area(planetBounds);java.awt.geom.Area covered = new java.awt.geom.Area();for (Area area : areas) {uncovered.subtract(area.getJavaArea());covered.add(area.getJavaArea());}Rectangle rCov = covered.getBounds();Rectangle[] topAndBottom = {new Rectangle(planetBounds.x, (int) rCov.getMaxY(), planetBounds.width,(int) (planetBounds.getMaxY() - rCov.getMaxY())), // topnew Rectangle(planetBounds.x, planetBounds.y, planetBounds.width, rCov.y - planetBounds.y) }; // bottomfor (Rectangle border : topAndBottom) {if (!border.isEmpty()) {uncovered.subtract(new java.awt.geom.Area(border));covered.add(new java.awt.geom.Area(border));Area pseudo = new Area(border.y, border.x, (int) border.getMaxY(), (int) border.getMaxX());pseudo.setMapId(-1 * (areas.size() + 1));pseudo.setPseudoArea(true);areas.add(pseudo);}}while (uncovered.isEmpty() == false) {boolean changed = false;List<List<Point>> shapes = Utils.areaToShapes(uncovered);// we divide planet into stripes for all vertices of the uncovered// areaint minX = uncovered.getBounds().x;int nextX = Integer.MAX_VALUE;for (int i = 0; i < shapes.size(); i++) {List<Point> shape = shapes.get(i);for (Point point : shape) {int lon = point.x;if (lon < nextX && lon > minX)nextX = lon;}}java.awt.geom.Area stripeLon = new java.awt.geom.Area(new Rectangle(minX, planetBounds.y, nextX - minX, planetBounds.height));// cut out already covered areastripeLon.subtract(covered);assert stripeLon.isEmpty() == false;// the remaining area must be a set of zero or more disjoint// rectanglesList<List<Point>> stripeShapes = Utils.areaToShapes(stripeLon);for (int j = 0; j < stripeShapes.size(); j++) {List<Point> rectShape = stripeShapes.get(j);java.awt.geom.Area test = Utils.shapeToArea(rectShape);test = simplifyArea(test);assert test.isRectangular();Rectangle pseudoRect = test.getBounds();if (uncovered.contains(pseudoRect)) {assert test.getBounds().width == stripeLon.getBounds().width;boolean wasMerged = false;// check if new area can be merged with last rectanglesfor (int k = areas.size() - 1; k >= oldSize; k--) {Area prev = areas.get(k);if (prev.getMaxLong() < pseudoRect.x || prev.isPseudoArea() == false)continue;if (prev.getHeight() == pseudoRect.height && prev.getMaxLong() == pseudoRect.x&& prev.getMinLat() == pseudoRect.y) {// mergeArea pseudo = prev.add(new Area(pseudoRect.y, pseudoRect.x, (int) pseudoRect.getMaxY(),(int) pseudoRect.getMaxX()));pseudo.setMapId(prev.getMapId());pseudo.setPseudoArea(true);areas.set(k, pseudo);// System.out.println("Enlarged pseudo area " +// pseudo.getMapId() + " " + pseudo);wasMerged = true;break;}}if (!wasMerged) {Area pseudo = new Area(pseudoRect.y, pseudoRect.x, (int) pseudoRect.getMaxY(),(int) pseudoRect.getMaxX());pseudo.setMapId(-1 * (areas.size() + 1));pseudo.setPseudoArea(true);// System.out.println("Adding pseudo area " +// pseudo.getMapId() + " " + pseudo);areas.add(pseudo);}uncovered.subtract(test);covered.add(test);changed = true;}}if (!changed)break;}return oldSize != areas.size();}}