Rev 2436 | View as "text/plain" | Blame | Compare with Previous | Last modification | View Log | RSS feed
/** Copyright (C) 2012.** This program is free software; you can redistribute it and/or modify* it under the terms of the GNU General Public License version 3 or* 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.*/package uk.me.parabola.mkgmap.reader.osm.boundary;import java.awt.Rectangle;import java.awt.geom.Area;import java.awt.geom.Path2D;import java.awt.geom.Rectangle2D;import java.io.ByteArrayOutputStream;import java.io.DataInputStream;import java.io.DataOutputStream;import java.io.EOFException;import java.io.IOException;import java.io.OutputStream;import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.HashMap;import java.util.Iterator;import java.util.LinkedHashMap;import java.util.List;import java.util.Map;import java.util.Map.Entry;import java.util.regex.Pattern;import uk.me.parabola.imgfmt.app.Coord;import uk.me.parabola.log.Logger;import uk.me.parabola.mkgmap.reader.osm.Tags;import uk.me.parabola.mkgmap.reader.osm.Way;import uk.me.parabola.util.EnhancedProperties;import uk.me.parabola.util.GpxCreator;import uk.me.parabola.util.Java2DConverter;/*** A quadtree implementation to handle areas formed by boundaries.* Each node of the Quadtree stores a list of NodeElems. A NodeElem* stores one area and the related location relevant tags.* @author GerdP**/public class BoundaryQuadTree {private static final Logger log = Logger.getLogger(BoundaryQuadTree.class);private static final boolean DEBUG = false;// debugging aidprivate static final String DEBUG_TREEPATH = "?";private static final boolean DO_ALL_TESTS = false;// maps the "normal" tags of the boundaries that are saved in this tree to// the boundaryIdprivate final HashMap<String, Tags> boundaryTags = new LinkedHashMap<String,Tags>();// maps the location relevant info to the boundaryIdprivate final HashMap<String, BoundaryLocationInfo> preparedLocationInfo;// property controlled preparerprivate final BoundaryLocationPreparer preparer;private final Node root;// the bounding box of the quadtreeprivate final Rectangle bbox;private final String bbox_key;// tags that can be returned in the get methodpublic final static String[] mkgmapTagsArray = {"mkgmap:admin_level1","mkgmap:admin_level2","mkgmap:admin_level3","mkgmap:admin_level4","mkgmap:admin_level5","mkgmap:admin_level6","mkgmap:admin_level7","mkgmap:admin_level8","mkgmap:admin_level9","mkgmap:admin_level10","mkgmap:admin_level11","mkgmap:postcode"};// 11: the position of "mkgmap:postcode" in the above arraypublic final static short POSTCODE_ONLY = 1 << 11;/*** Create a quadtree with the data in an open stream.* @param inpStream the open stream with QUADTREE_DATA_FORMAT* @param fileBbox The bounding box for the quadTree* @param searchBbox The bounding box for the quadTree, only data within this box is used* @param props if not null, use it to set location names*/public BoundaryQuadTree(DataInputStream inpStream,uk.me.parabola.imgfmt.app.Area fileBbox,uk.me.parabola.imgfmt.app.Area searchBbox, EnhancedProperties props)throws IOException {preparedLocationInfo = new LinkedHashMap<String, BoundaryLocationInfo> ();preparer = new BoundaryLocationPreparer(props);assert fileBbox != null: "parameter fileBbox must not be null";this.bbox = new Rectangle(fileBbox.getMinLong(), fileBbox.getMinLat(),fileBbox.getMaxLong() - fileBbox.getMinLong(), fileBbox.getMaxLat()- fileBbox.getMinLat());this.bbox_key = BoundaryUtil.getKey(this.bbox.y, this.bbox.x);root = new Node(this.bbox);readStreamQuadTreeFormat(inpStream,searchBbox);}/*** Create a quadtree for a given bounding box and a list of boundaries.* Involves costly calculations to split the areas.* @param givenBbox The bounding box for the quadTree, only data within this box is used* @param boundaries A list of boundaries. For better performance, the list should be sorted so that small areas come first.* @param props if not null, use it to set location names*/public BoundaryQuadTree(uk.me.parabola.imgfmt.app.Area givenBbox,List<Boundary> boundaries, EnhancedProperties props) {preparer = new BoundaryLocationPreparer(props);assert givenBbox != null: "parameter givenBbox must not be null";this.bbox = new Rectangle(givenBbox.getMinLong(), givenBbox.getMinLat(),givenBbox.getMaxLong() - givenBbox.getMinLong(),givenBbox.getMaxLat() - givenBbox.getMinLat());this.bbox_key = BoundaryUtil.getKey(this.bbox.y, this.bbox.x);root = new Node(this.bbox);// extract the location relevant tagspreparedLocationInfo = preparer.getPreparedLocationInfo(boundaries);if (boundaries == null || boundaries.size() == 0)return;HashMap<String,Boundary> bMap = new HashMap<String,Boundary>();for (Boundary b: boundaries){bMap.put(b.getId(), b);boundaryTags.put(b.getId(), b.getTags());}sortBoundaryTagsMap();// add the boundaries in a specific orderfor (String id: boundaryTags.keySet()){root.add (bMap.get(id).getArea(), id, null);}bMap = null;root.split("_");}/*** Return location relevant Tags for the point defined by Coord* @param co the point* @return a reference to the internal Tags or null if the point was not found.* The returned Tags must not be modified by the caller.*/public Tags get(Coord co){Tags res = root.get(co/*, "_"*/);if (res == null && bbox.contains(co.getLongitude(),co.getLatitude())){// we did not find the point, probably it lies on a boundary and// the clauses regarding insideness of areas make it "invisible"// try again a few other nearby pointsCoord neighbour1 = new Coord(co.getLatitude()-1, co.getLongitude());Coord neighbour2 = new Coord(co.getLatitude() , co.getLongitude()-1);Coord neighbour3 = new Coord(co.getLatitude()+1, co.getLongitude());Coord neighbour4 = new Coord(co.getLatitude() , co.getLongitude()+1);res = root.get(neighbour1/*, "_"*/);if (res == null)res = root.get(neighbour2/*, "_"*/);if (res == null)res = root.get(neighbour3/*, "_"*/);if (res == null)res = root.get(neighbour4/*, "_"*/);}return res;}/*** Return a map with boundary IDs and the related tags.* @return the map. It is a LinkedHashMap, the order is created with* AdminLevelCollator and then reversed.*/public Map<String, Tags> getTagsMap() {return new LinkedHashMap<String, Tags>(boundaryTags);}/*** Create a map with boundary Ids and the related area parts that* are stored in the tree. When the parts are added, they normally* give the original boundary (clipped by the bounding box of the quadtree).* Exception: For overlapping boundaries with equal admin_levels only one* boundary will contain the complete area information.* @return A HashMap mapping BoundaryIds to a List with all area parts*/public Map<String, List<Area>> getAreas(){Map<String, List<Area>> areas = new HashMap<String, List<Area>>();root.getAreas(areas, "_", null);return areas;}/*** For BoundaryMerger: Add the data of another tree into this tree.* @param other the other instance of BoundaryQuadTree*/public void merge(BoundaryQuadTree other){if (bbox.equals(other.bbox) == false){log.error("Cannot merge tree with different bounding box");return;}for (Entry <String, BoundaryLocationInfo> entry : other.preparedLocationInfo.entrySet()){if (this.preparedLocationInfo.containsKey(entry.getKey()) == false){this.preparedLocationInfo.put(entry.getKey(),entry.getValue());}}// add the others tagsfor (Entry <String, Tags> entry : other.boundaryTags.entrySet()){if (this.boundaryTags.containsKey(entry.getKey()) == false){this.boundaryTags.put(entry.getKey(),entry.getValue());}}sortBoundaryTagsMap();root.mergeNodes(other.root, "_");}/*** Return the area that is covered by a given admin level* @param admLevel reasonable values are 2 .. 11 (inclusive)* @return*/public Area getCoveredArea (Integer admLevel){return root.getCoveredArea(admLevel, "_");}/*** Return boundary names relevant for the point defined by Coord* @param co the point* @return A string with a boundary Id, optionally followed by pairs of admlevel:boundary Id.* Sample: r1184826;6:r62579;4:r62372;2:r51477*/public String getBoundaryNames(Coord co){return root.getBoundaryNames(co);}/*** Save the BoundaryQuadTree to an open stream. The format is QUADTREE_DATA_FORMAT.* @param stream* @throws IOException*/public void save(OutputStream stream)throws IOException{// save the tag infos of all boundaries firstfor (Entry<String,Tags> entry : boundaryTags.entrySet()){writeBoundaryTags(stream, entry.getValue(), entry.getKey());}// now write the area info for those boundaries that have positions in the quadtreeroot.save(stream, "_");}/*** Sort the boundary-Tags-Map so that zip-code-only boundaries appear first, followed by* admin_level-11,10,9,...2*/private void sortBoundaryTagsMap(){// make sure that the merged LinkedHashMap is sorted as mergeBoundaries() needs itArrayList<String> ids = new ArrayList<String>(boundaryTags.keySet());Collections.sort(ids, new AdminLevelCollator());Collections.reverse(ids);HashMap<String,Tags> tmp = new LinkedHashMap<String,Tags>(boundaryTags);boundaryTags.clear();for (String id: ids){boundaryTags.put(id,tmp.get(id));}}/*** Write the TAGS sections of the QUADTREE_DATA_FORMAT. Each* section starts with the "TAGS" eye catcher followed by the* boundary id, the number of tags and the tags as* key/value pairs.* @param stream an already opened OutputStream* @param tags the boundary tags* @param id the boundaryId* @throws IOException*/private void writeBoundaryTags(OutputStream stream, Tags tags, String id) throws IOException{DataOutputStream dOutStream = new DataOutputStream(stream);dOutStream.writeUTF("TAGS");dOutStream.writeUTF(id);// write the tagsint noOfTags = tags.size();dOutStream.writeInt(noOfTags);Iterator<Entry<String, String>> tagIter = tags.entryIterator();while (tagIter.hasNext()) {Entry<String, String> tag = tagIter.next();dOutStream.writeUTF(tag.getKey());dOutStream.writeUTF(tag.getValue());noOfTags--;}assert noOfTags == 0 : "Remaining tags: " + noOfTags + " size: "+ tags.size() + " " + tags.toString();dOutStream.flush();}/*** Read a stream in QUADTREE_DATA_FORMAT* @param inpStream the already opened DataInputStream* @param bbox a bounding box. Areas not intersecting the bbox are* ignored.* @throws IOException*/private void readStreamQuadTreeFormat(DataInputStream inpStream,uk.me.parabola.imgfmt.app.Area bbox) throws IOException{boolean isFirstArea = true;try {while (true) {String type = inpStream.readUTF();if (type.equals("TAGS")){String id = inpStream.readUTF();Tags tags = new Tags();int noOfTags = inpStream.readInt();for (int i = 0; i < noOfTags; i++) {String name = inpStream.readUTF();String value = inpStream.readUTF();tags.put(name, value.intern());}boundaryTags.put(id, tags);}else if (type.equals("AREA")){if (isFirstArea){isFirstArea = false;prepareLocationInfo();}int minLat = inpStream.readInt();int minLong = inpStream.readInt();int maxLat = inpStream.readInt();int maxLong = inpStream.readInt();log.debug("Next boundary. Lat min:",minLat,"max:",maxLat,"Long min:",minLong,"max:",maxLong);uk.me.parabola.imgfmt.app.Area rBbox = new uk.me.parabola.imgfmt.app.Area(minLat, minLong, maxLat, maxLong);int bSize = inpStream.readInt();log.debug("Size:",bSize);if ( bbox == null || bbox.intersects(rBbox)) {log.debug("Bbox intersects. Load the boundary");String treePath = inpStream.readUTF();String id = inpStream.readUTF();String refs = inpStream.readUTF();if (refs.isEmpty())refs = null;Area area = BoundaryUtil.readAreaAsPath(inpStream);if (area != null && area.isEmpty() == false)root.add(area, refs, id, treePath);} else {log.debug("Bbox does not intersect. Skip",bSize);inpStream.skipBytes(bSize);}}else{log.error("unknown type field " + type );}}} catch (EOFException exp) {// it's always thrown at the end of the file// log.error("Got EOF at the end of the file");}}/*** Fill the map preparedLocationInfo with data from the boundary tags.*/private void prepareLocationInfo() {for (Entry<String, Tags> entry : boundaryTags.entrySet()) {BoundaryLocationInfo info = preparer.parseTags(entry.getValue());preparedLocationInfo.put(entry.getKey(), info);}}/*** A node for the BoundaryQuadTree. Many methods use a so-called treePath to identify the position* of the node in the tree. A treePath _021 means root->childs[0]->childs[2]->childs[1].* This path is also saved in the QUADTREE_DATA_FORMAT.* @author GerdP**/private class Node {private Node [] childs;private List<NodeElem> nodes;// bounding box of this part of the treeprivate final Rectangle bbox;private final uk.me.parabola.imgfmt.app.Area bounds;private short depth;private boolean isLeaf;/*** Create an empty node for the given bbox* @param bbox*/private Node (Rectangle bbox){this.bounds = new uk.me.parabola.imgfmt.app.Area (bbox.y, bbox.x, bbox.y+bbox.height, bbox.x+bbox.width);this.bbox = new Rectangle(bbox);isLeaf = true;}/*** Constructor that is used by the split method. The parameters give the corners of a bounding box.* @param minLat* @param minLong* @param maxLat* @param maxLong*/private Node (int minLat, int minLong, int maxLat, int maxLong){this.bounds = new uk.me.parabola.imgfmt.app.Area (minLat, minLong, maxLat, maxLong);this.bbox = new Rectangle(minLong, minLat, maxLong - minLong, maxLat - minLat);this.isLeaf = true;}/*** Travel through the tree, save all usable areas of all leaves* @param stream the open OutputStream* @param treePath the path to this tree node* @throws IOException*/private void save(OutputStream stream, String treePath )throws IOException{if (isLeaf){if (nodes != null){for (NodeElem nodeElem :nodes){if (nodeElem.isValid())nodeElem.save(stream, treePath);}}}else {for (int i = 0; i < 4; i++){childs[i].save(stream, treePath + i);}}}/*** Return boundary names relevant for the point defined by Coord* @param co the point* @return A string with a boundary Id, optionally followed by pairs of admlevel:boundary Id.* Sample: r1184826;6:r62579;4:r62372;2:r51477*/private String getBoundaryNames(Coord co) {if (this.bounds.contains(co) == false)return null;if (isLeaf){if (nodes == null || nodes.size() == 0)return null;int lon = co.getLongitude();int lat = co.getLatitude();for (NodeElem nodeElem: nodes){if (nodeElem.tagMask > 0){if (nodeElem.area.contains(lon,lat)){String res = new String (nodeElem.boundaryId);if (nodeElem.locationDataSrc != null)res += ";" + nodeElem.locationDataSrc;return res;}}}}else {for (int i = 0; i < 4; i++){String res = childs[i].getBoundaryNames(co);if (res != null)return res;}}return null;}/*** Return location relevant Tags for the point defined by Coord* @param co the point* @return a reference to the internal Tags or null if the point was not found.* The returned Tags must not be modified by the caller.*/private Tags get(Coord co/*, String treePath*/){if (this.bounds.contains(co) == false)return null;if (isLeaf){if (nodes == null || nodes.size() == 0)return null;int lon = co.getLongitude();int lat = co.getLatitude();for (NodeElem nodeElem: nodes){if (nodeElem.tagMask > 0){if (nodeElem.area.contains(lon,lat)){return nodeElem.locTags;}}}}else {for (int i = 0; i < 4; i++){Tags res = childs[i].get(co/*, treePath+i*/);if (res != null)return res;}}return null;}/*** Debugging helper: Print node Tags and maybe create gpx* @param prefix identifies the calling routine* @param treePath*/private void printNodes(String prefix, String treePath){int n = 0;for (NodeElem nodeElem: nodes){if (treePath.equals(DEBUG_TREEPATH)){nodeElem.saveGPX(prefix,treePath);}String res = new String();for (int i = mkgmapTagsArray.length-1; i >= 0 ; --i){String tagVal = nodeElem.locTags.get(mkgmapTagsArray[i] );if (tagVal != null){res += i+1 + "=" + tagVal + ";";}}System.out.println(prefix + " " + treePath + " " + n + ":" + nodeElem.boundaryId + " " + nodeElem.tagMask + " " + res );++n;}}/*** Test if all areas in one node are distinct areas. This is wanted, but not* absolutely needed.* @param treePath Position in the quadtree. Used for GPX.* @return false if any area intersects with another area and the* intersection has a dimension.*/private boolean testIfDistinct(String treePath){boolean ok = true;for (int i=0; i< nodes.size()-1; i++){for (int j=i+1; j < nodes.size(); j++){Area a = new Area (nodes.get(i).area);a.intersect(nodes.get(j).area);if (a.isEmpty())continue;Path2D.Double path = new Path2D.Double(a);a = new Area(path);if (a.isEmpty())continue;if (a.getBounds2D().getHeight() < 0.1d && a.getBounds2D().getWidth() < 0.1d)continue;ok = false;log.error("boundaries still intersect in tree path "+ treePath + " " + nodes.get(i).boundaryId + " "+ nodes.get(j).boundaryId + " bbox: " + a.getBounds2D());NodeElem tmpNodeElem = new NodeElem(nodes.get(i).boundaryId+"_"+nodes.get(j).boundaryId,new Area(a.getBounds2D()), null);tmpNodeElem.saveGPX("intersection_rect",treePath);}}if (DEBUG){if (!ok){for (NodeElem nodeElem: nodes){nodeElem.saveGPX("not_distinct",treePath);}}}return ok;}/*** Add an area and the related tags to the tree. The position in the tree is known* and passed via the treePath.* @param area the part of the boundary area that should be added to the tree.* @param refs a string that contains information about other boundaries that share the* same area* @param boundaryId id of the originating boundary* @param treePath empty string: calculate position, else the first character is used as index of the child*/private void add(Area area, String refs, String boundaryId, String treePath){Node node = this;String path = treePath;while(path.isEmpty() == false){int idx = Integer.valueOf(path.substring(0, 1));path = path.substring(1);if (node.childs == null)node.allocChilds();node = node.childs[idx];}if (node.nodes == null){node.nodes = new ArrayList<NodeElem>();}NodeElem nodeElem = new NodeElem(boundaryId, area, refs);assert (area.getBounds2D().getWidth() == 0 || area.getBounds2D().getHeight() == 0 || this.bbox.intersects(area.getBounds2D())) : "boundary bbox doesn't fit into quadtree "+ bbox + " " + area.getBounds2D();node.nodes.add(nodeElem);}/*** Add an area and the related tags to the tree.* @param area the part of the boundary area that should be added to the tree.* @param locTags the location relevant tags from the boundary* @param boundaryId id of the originating boundary*/private void add(Area area, String boundaryId, String refs){if (!isLeaf){// should not happenfor (int i = 0; i < 4; i++){childs[i].add(area, boundaryId, refs);}return;}// only add areas that intersect with this part of the treeif (area.intersects(this.bbox) == false)return;Area a;if (area.contains(bbox))a = new Area(this.bbox); // quadtree bbox lies entirely in areaelse {a = new Area(area);Area bboxArea = new Area(this.bbox);// check if area lies entirely in quadtree bboxif (bboxArea.contains(area.getBounds2D()) == false){// worst case: area and bbox partly intersecta.intersect(bboxArea);}}if (a.isEmpty() == false){if (nodes == null)nodes = new ArrayList<NodeElem>();NodeElem nodeElem = new NodeElem(boundaryId, a, refs);nodes.add(nodeElem);}}/*** Merge this subtree with another subtree.* @param other A Node of another BoundaryQuadTree* @param treePath position of this node in its tree*/private void mergeNodes(Node other, String treePath){if (!this.isLeaf && !other.isLeaf){for (int i = 0; i < 4; i++){childs[i].mergeNodes(other.childs[i], treePath+i);}}else{// (sub) tree is different, rebuild it as combination of// both trees.HashMap<String,List<Area>> areas = new HashMap<String, List<Area>>();this.getAreas(areas, treePath,null);other.getAreas(areas, treePath,null);isLeaf = true;nodes = null;childs = null;for (String id: boundaryTags.keySet()){List<Area> aList = areas.get(id);if (aList == null)continue;Path2D.Double path = new Path2D.Double();for (Area area : aList){BoundaryUtil.addToPath(path, area);}add(new Area(path), id, null);}split(treePath);}}/*** Calculate the area that is covered by boundaries of a given adminlevel* @param admLevel the admin_level, a value from 2 to 11 (including)* @param treePath A string that helps to identify the position in the quadtree* @return a new Area instance (might be empty)*/private Area getCoveredArea(Integer admLevel, String treePath){HashMap<String,List<Area>> areas = new HashMap<String, List<Area>>();this.getAreas(areas, treePath, admLevel);Path2D.Double path = new Path2D.Double();for (Entry <String, List<Area>> entry : areas.entrySet()){for (Area area: entry.getValue()){BoundaryUtil.addToPath(path,area);}}Area combinedArea = new Area(path);return combinedArea;}/*** See BoundaryQuadTree {@link #BoundaryQuadTree.getAreas()}* @param areas* @param treePath* @param admLevel*/private void getAreas(Map<String, List<Area>> areas, String treePath, Integer admLevel){if (!this.isLeaf ){for (int i = 0; i < 4; i++){childs[i].getAreas(areas, treePath+i, admLevel);}return;}if (nodes == null || nodes.size() == 0)return;Short testMask = null;if (admLevel != null)testMask = (short) (1<<(admLevel-1));for (NodeElem nodeElem : nodes){String id = nodeElem.boundaryId;if (testMask != null && (nodeElem.tagMask & testMask) == 0)continue;List<Area> aList = areas.get(id);Area a = new Area(nodeElem.area);if (aList == null){aList = new ArrayList<Area>(4);areas.put(id, aList);}aList.add(a);if (testMask != null)continue;String refInfo = nodeElem.locationDataSrc;if (refInfo != null) {String[] relBounds = refInfo.split(Pattern.quote(";"));for (String relBound : relBounds) {String[] relParts = relBound.split(Pattern.quote(":"));if (relParts.length != 2) {log.error("Wrong format in locationDataSrc. Value: " + refInfo);continue;}id = relParts[1];aList = areas.get(id);a = new Area(nodeElem.area);if (aList == null){aList = new ArrayList<Area>(4);areas.put(id, aList);}aList.add(a);}}}}/**** Merge information from the boundaries saved by BoundarySaver.* This method is used when bnd file is in raw format.* For intersections, create new areas with the merged* location tags, and subtract the parts from the source* areas. The result should be a reduced number of distinct areas.* @param treePath Identifies the position in the tree*/private void makeDistinct(String treePath){if (isLeaf == false || nodes == null || nodes.size() <= 1)return;if (DEBUG){printNodes("start", treePath);}long t1 = System.currentTimeMillis();mergeEqualIds();mergeLastRectangles();if (DEBUG)printNodes("prep", treePath);List<NodeElem> reworked = new ArrayList<NodeElem>();// detect intersection of areas, merge tag infofor (int i=0; i < nodes.size(); i++){NodeElem toAdd = nodes.get(i);if (DEBUG){if (treePath.equals(DEBUG_TREEPATH) || DEBUG_TREEPATH.equals("all")){for (NodeElem nodeElem: reworked){nodeElem.saveGPX("debug"+i,treePath);}}}for (int j=0; j < reworked.size(); j++){if (toAdd.isValid() == false)break;NodeElem currElem = reworked.get(j);if (currElem.srcPos == i || currElem.area.isEmpty())continue;Rectangle2D rCurr = currElem.area.getBounds2D();Rectangle2D rAdd = rCurr.createIntersection(toAdd.area.getBounds2D());if (rAdd.isEmpty()){continue;}// the bounding boxes intersect, so we have to find out if the areas also intersectArea toAddxCurr = new Area(currElem.area);toAddxCurr.intersect(toAdd.area);if (!isWritable(toAddxCurr)){continue; // empty or only too small fragments}Area toAddMinusCurr = new Area(toAdd.area);toAddMinusCurr.subtract(currElem.area);if (toAddMinusCurr.isEmpty()){// toadd is fully covered by currif (toAdd.tagMask == POSTCODE_ONLY){// if we get here, toAdd has only zip code that is already known// in larger or equal area of currElemtoAdd.area.reset(); // ignore thisbreak;}}// test if toAdd contains usable tag(s)String chkMsg = currElem.checkAddTags(toAdd, bounds);// warning: intersection of areas with equal levelsif (chkMsg != null){if (DEBUG){// save debug GPX for areas that wiil// appear in warning message belowtoAdd.saveGPX("warn_toAdd",treePath);currElem.saveGPX("warn_curr",treePath);}log.warn(chkMsg);}Area currMinusToAdd = new Area(currElem.area);currMinusToAdd.subtract(toAdd.area);// remove intersection part from toAddtoAdd.area = toAddMinusCurr;if (!isWritable(currMinusToAdd)){// curr is fully covered by toAddif (toAdd.tagMask != POSTCODE_ONLY){currElem.addLocInfo(toAdd);}continue; // no need to create new intersection area}NodeElem intersect = new NodeElem(currElem, toAddxCurr, i);if (DEBUG){if (chkMsg != null)intersect.saveGPX("warn_inter", treePath);}// remove intersection part also from currcurrElem.area = currMinusToAdd;if (toAdd.tagMask != POSTCODE_ONLY){// combine tag info in intersectionintersect.addLocInfo(toAdd);reworked.add(intersect);}}if (toAdd.isValid())reworked.add(toAdd);}nodes = reworked;// free memory for nodes with empty or too small areasremoveEmptyAreas(treePath);long dt = System.currentTimeMillis()-t1;if (dt > 1000)log.info(bbox_key, ": merge required long time:", dt, "ms");if (DEBUG)printNodes("end", treePath);//double check ?if (DO_ALL_TESTS){testIfDistinct(treePath);}}/*** Combine the areas with equal boundary IDs.* We can assume that equal IDs are paired when add is* called with sorted input.*/private void mergeEqualIds(){int start = nodes.size()-1;for (int i = start; i > 0; i--){if (nodes.get(i).boundaryId.equals(nodes.get(i-1).boundaryId)){nodes.get(i-1).area.add(nodes.get(i).area);nodes.remove(i);}}}/*** Optimization:* The last nodes are likely to fully cover the quadtree bbox.* Merge the tag information for them to avoid some splitting* and later merging.*/private void mergeLastRectangles(){boolean done;//step1: merge nodes that fully cover the quadtree areado{done = true;if (nodes.size()<= 1)break;NodeElem lastNode = nodes.get(nodes.size()-1);NodeElem prevNode = nodes.get(nodes.size()-2);// don't merge admin_level tags into zip-code only boundaryif (prevNode.tagMask != POSTCODE_ONLY && lastNode.area.isRectangular() && prevNode.area.isRectangular()){// two areas are rectangles, it is likely that they are equal to the bounding box// In this case we add the tags to the existing area instead of creating a new oneif (prevNode.area.equals(lastNode.area)){prevNode.addLocInfo(lastNode);nodes.remove(nodes.size()-1);done = false;}}} while (!done);}/*** The mergeBoundaries() algorithm can create empty* areas (points, lines, or extremely small intersections).* These are removed here.* @param treePath*/private void removeEmptyAreas(String treePath){for (int j = nodes.size()-1; j >= 0 ; j--){boolean removeThis = false;NodeElem chkRemove = nodes.get(j);if (chkRemove.isValid() == false)removeThis = true;else if (this.bbox.intersects(chkRemove.area.getBounds2D()) == false){// we might get here because of errors in java.awt.geom.Area// sometimes, Area.subtract() seems to produce an area which// lies outside of original areasremoveThis = true;}else if (!isWritable(chkRemove.area)){removeThis = true;}if (removeThis){nodes.remove(j);}}}/*** allocate 4 childs with bounding boxes that have 1/4 of the* size of the parent.*/private void allocChilds(){childs = new Node[4];Coord center = bounds.getCenter();childs[0] = new Node(bounds.getMinLat(), bounds.getMinLong(),center.getLatitude(), center.getLongitude());childs[1] = new Node(center.getLatitude(), bounds.getMinLong(),bounds.getMaxLat(), center.getLongitude());childs[2] = new Node(bounds.getMinLat(), center.getLongitude(),center.getLatitude(), bounds.getMaxLong());childs[3] = new Node(center.getLatitude(), center.getLongitude(),bounds.getMaxLat(), bounds.getMaxLong());for (int i = 0; i < 4; i++){childs[i].depth = (short) (this.depth + 1);}isLeaf = false;}/*** Split the tree into 4 equally sized parts and* distribute the data.*/private void split(String treePath){if (isLeaf == true){if (nodes == null)return;if (DEBUG){String fname = "gpx/" + treePath+ "/bbox"+treePath;List<List<Coord>> polys = Java2DConverter.areaToShapes(Java2DConverter.createBoundsArea(bounds));GpxCreator.createGpx(fname, polys.get(0));}// subject to tuningif (depth >= 5 || nodes.size() <= 7 || bounds.getHeight() < 10 || bounds.getWidth() < 10 ){makeDistinct(treePath);return ;}mergeLastRectangles();allocChilds();for (int i = 0; i < 4; i++){for (NodeElem nodeElem: nodes){childs[i].add(nodeElem.area, nodeElem.boundaryId, nodeElem.locationDataSrc);}}// return memory to GCnodes = null;}// finally try splitting the sub treesfor (int i = 0; i < 4; i++){childs[i].split(treePath+i);}}}private class NodeElem{// the intersections of the boundaries with the bounding box of this nodeprivate Area area;// location relevant tags of boundaries that intersect with the bounding box of this nodeprivate Tags locTags;// a bit mask that helps comparing Tagsprivate short tagMask;// boundary that was initially usedprivate final String boundaryId;// data for the intersects_with tagprivate String locationDataSrc;private int srcPos;/*** Create a node elem.* @param boundaryId The boundary Id* @param area the (part of the) boundary area stored in this node* @param refs A string containing boundaryIds and admin-level infos* of all boundaries with lower admin levels that share the same area.*/NodeElem (String boundaryId, Area area, String refs){srcPos = -1;this.boundaryId = boundaryId;this.area = area;this.locationDataSrc = refs;calcLocTags();}/*** Create a new node elem as a partly copy of an existing* NodeElem and a new area.* @param other the existing NodeElem instance* @param area the new area* @param srcPos identifies the position of other in the* nodes list of the Node.*/NodeElem (NodeElem other, Area area, int srcPos){this.area = area;this.srcPos = srcPos;this.boundaryId = other.boundaryId;this.tagMask = other.tagMask;this.locationDataSrc = other.locationDataSrc;this.locTags = other.locTags.copy();}/*** check if a NodeElem contains usable info.* @return false if either the area is not usable or* the tags should be ignored.*/private boolean isValid(){if (tagMask == 0 || area == null || area.isEmpty())return false;return true;}/*** Add the location relevant data of another NodeElem* @param toAdd the other NodeElem*/private void addLocInfo(NodeElem toAdd){addLocationDataString(toAdd);addMissingTags(toAdd.locTags);tagMask |= toAdd.tagMask;}/*** Calculate the tags that are location relevant.* Problem: If the tree is created by BoundaryPreparer, we do not know how to calculate* the name because we don't know which tag to use for this, so be aware that this* may return different results compared to the LocationHook.* @param boundary*/private void calcLocTags(){locTags = new Tags();tagMask = 0;BoundaryLocationInfo bInfo = preparedLocationInfo.get(boundaryId);if (bInfo == null){log.error("unknown boundaryId " + boundaryId);return;}if (bInfo.getZip() != null){locTags.put("mkgmap:postcode",bInfo.getZip());}if (bInfo.getAdmLevel() != BoundaryLocationPreparer.UNSET_ADMIN_LEVEL){locTags.put(BoundaryQuadTree.mkgmapTagsArray[bInfo.getAdmLevel()-1], bInfo.getName());}if (locationDataSrc != null && locationDataSrc.isEmpty() == false){// the common format of refInfo is// 2:r19884;4:r20039;6:r998818String[] relBounds = locationDataSrc.split(Pattern.quote(";"));for (String relBound : relBounds) {String[] relParts = relBound.split(Pattern.quote(":"));if (relParts.length != 2) {log.error("Wrong format. Value: " + locationDataSrc);continue;}BoundaryLocationInfo addInfo = preparedLocationInfo.get(relParts[1]);if (addInfo == null) {log.warn("Referenced boundary not known:", relParts[1]);continue;}int addAdmLevel = addInfo.getAdmLevel();String addAdmName = null;if (addAdmLevel != BoundaryLocationPreparer.UNSET_ADMIN_LEVEL){addAdmName = addInfo.getName();}String addZip = addInfo.getZip();if (addAdmName != null){if (locTags.get(BoundaryQuadTree.mkgmapTagsArray[addAdmLevel-1]) == null)locTags.put(BoundaryQuadTree.mkgmapTagsArray[addAdmLevel-1], addAdmName);}if (addZip != null){if (locTags.get("mkgmap:postcode") == null)locTags.put("mkgmap:postcode", addZip);}}}tagMask = calcLocationTagsMask();}/*** Merge the locationDataSrc of two NodeElems.* The caller has to make sure that the merge makes sense.* @param toAdd The other NodeElem*/private void addLocationDataString (NodeElem toAdd){BoundaryLocationInfo info = preparedLocationInfo.get(toAdd.boundaryId);assert info.getAdmLevel() > 0 : "cannot use admLevel";String admLevel = info.getAdmLevel() + ":" + toAdd.boundaryId;if (this.locationDataSrc == null)this.locationDataSrc = admLevel;elsethis.locationDataSrc += ";" + admLevel;if (toAdd.locationDataSrc != null){this.locationDataSrc += ";" + toAdd.locationDataSrc;}}/*** Write a nodeElem an AREA segment of the QUADTREE_DATA_FORMAT.* @param stream the already opened OutputStream* @param treePath identifies the position within the tree* @throws IOException*/private void save(OutputStream stream, String treePath) throws IOException{ByteArrayOutputStream oneItemStream = new ByteArrayOutputStream();DataOutputStream dos = new DataOutputStream(oneItemStream);String id = this.boundaryId;dos.writeUTF(treePath.substring(1));dos.writeUTF(id);if (this.locationDataSrc == null)dos.writeUTF("");elsedos.writeUTF(this.locationDataSrc);BoundarySaver.writeArea(dos, this.area);dos.close();// now start to write into the real stream// first write the bounding box so that is possible to skip the// complete entryuk.me.parabola.imgfmt.app.Area bbox = Java2DConverter.createBbox(this.area);DataOutputStream dOutStream = new DataOutputStream(stream);dOutStream.writeUTF("AREA");dOutStream.writeInt(bbox.getMinLat());dOutStream.writeInt(bbox.getMinLong());dOutStream.writeInt(bbox.getMaxLat());dOutStream.writeInt(bbox.getMaxLong());// write the size of the boundary block so that it is possible to// skip itbyte[] data = oneItemStream.toByteArray();assert data.length > 0 : "bSize is not > 0 : " + data.length;dOutStream.writeInt(data.length);// write the boundary blockdOutStream.write(data);dOutStream.flush();}/*** calculate a handy short value that represents the available location tags* @return a bit mask, a bit with value 1 means the corresponding entry in {@link locationTagNames }* is available*/private short calcLocationTagsMask(){short res = 0;for (int i = 0; i < mkgmapTagsArray.length; i++){if (locTags.get(mkgmapTagsArray[i] ) != null)res |= (1 << i);}return res;}/*** For debugging: Save the area in gpx format* @param desc used as directory name* @param treePath*/private void saveGPX(String desc, String treePath){if (DEBUG){if (area == null)return;List<List<Coord>> singlePolys = Java2DConverter.areaToShapes(area);Collections.reverse(singlePolys);int cntPoly = 0;for (List<Coord> polyPart : singlePolys) {String attr = Way.clockwise(polyPart) ? "o" : "i";String fname = "gpx/" + treePath+ "/" + desc + "_" + area.getBounds().x + "_" + area.getBounds().y + "_" + boundaryId+ "_" + cntPoly + "_"+attr;GpxCreator.createGpx(fname, polyPart);++cntPoly;}}}/*** Handle errors in OSM data. Two boundaries with equal levels should not intersect.* Special case: zip-code-only boundaries with same zip code* @param other the other NodeElem* @param bounds a bounding box for the intersection of the two areas. Used* to create the error message.* @return null if no error, else a String with an error message*/private String checkAddTags(NodeElem other, uk.me.parabola.imgfmt.app.Area bounds){String errMsg = null;int errAdmLevel = 0;// case c) toAdd area is fully covered by currElem areafor (int k = 0; k < mkgmapTagsArray.length; k++){int testMask = 1 << k;if ((testMask & other.tagMask) != 0 && (this.tagMask & testMask) != 0){if (testMask == POSTCODE_ONLY){String zipKey = mkgmapTagsArray[k];if (other.locTags.get(zipKey).equals(this.locTags.get(zipKey)) == false){errMsg = "different " + zipKey;break;}}else{errAdmLevel = k+1;errMsg = new String ("same admin_level (" + errAdmLevel + ")");break;}}}if (errMsg != null){String url = bounds.getCenter().toOSMURL() + "&";url += (other.boundaryId.startsWith("w")) ? "way" : "relation";url += "=" + other.boundaryId.substring(1);//http://www.openstreetmap.org/?lat=49.394988&lon=6.551425&zoom=18&layers=M&relation=122907errMsg= "incorrect data: " + url + " intersection of boundaries with " + errMsg + " " + other.boundaryId + " " + this.boundaryId + " " ;if (errAdmLevel != 0 && this.locationDataSrc != null)errMsg += this.locationDataSrc;}return errMsg;}/*** Add tags from src to locTags if they are missing* @param src the Tags to be added*/private void addMissingTags(Tags src){Iterator<Entry<String,String>> tagIter = src.entryIterator();while (tagIter.hasNext()) {Entry<String,String> tag = tagIter.next();if (locTags.get(tag.getKey()) == null){locTags.put(tag.getKey(),tag.getValue());}}}}/**** Used to sort BoundaryLocationInfo. Input are boundaryIds.* @author gerd**/public class AdminLevelCollator implements Comparator<String> {public int compare(String o1, String o2) {if (o1.equals(o2)) {return 0;}BoundaryLocationInfo i1 = preparedLocationInfo.get(o1);BoundaryLocationInfo i2 = preparedLocationInfo.get(o2);int adminLevel1 = i1.getAdmLevel();int adminLevel2 = i2.getAdmLevel();if (i1.getName() == null || i1.getName() == "?") {// admin_level tag is set but no valid name availableadminLevel1= BoundaryLocationPreparer.UNSET_ADMIN_LEVEL;}if (i2.getName() == null || i2.getName() == "?") {// admin_level tag is set but no valid name availableadminLevel2= BoundaryLocationPreparer.UNSET_ADMIN_LEVEL;}if (adminLevel1 > adminLevel2)return 1;if (adminLevel1 < adminLevel2)return -1;if (i1.getAdmLevel() == 2){// prefer countries that are known by the Locatorif (i1.isISOName() == true && i2.isISOName() == false)return 1;if (i1.isISOName() == false && i2.isISOName() == true)return -1;}boolean post1set = i1.getZip() != null;boolean post2set = i2.getZip() != null;if (post1set && !post2set)return 1;if (!post1set && post2set)return -1;// if all is equal, prefer the lower boundaryIdreturn o1.compareTo(o2);}}/*** test if the conversion to a Path2D and back gives an empty area. If the* area is not already empty this routine simulates the writing and reading* and tests if the result is empty. Returns true is the area is not empty.*/public static boolean isWritable(Area area){if (area.isEmpty())return false;Path2D.Double path = new Path2D.Double(area);Area testArea = new Area(path);if (testArea.isEmpty()){return false;}return true;}}