WebSVN - mkgmap - Rev 3431 - /u/demon.box73/main/src/uk/me/parabola/mkgmap/reader/osm/boundary/BoundaryQuadTree.java

/*
* 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.Shape;
import java.awt.geom.Area;
import java.awt.geom.Path2D;
import java.awt.geom.PathIterator;
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;
import uk.me.parabola.util.ShapeSplitter;

/**
* 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 aid
private static final String DEBUG_TREEPATH = "?";
private static final boolean DO_ALL_TESTS = false;

private static final boolean DO_CLIP = true;
private static final boolean DO_NOT_CLIP = false;

// maps the "normal" tags of the boundaries that are saved in this tree to
// the boundaryId
private final HashMap<String, Tags> boundaryTags = new LinkedHashMap<>();
// maps the location relevant info to the boundaryId
private final HashMap<String, BoundaryLocationInfo> preparedLocationInfo;
// property controlled preparer
private final BoundaryLocationPreparer preparer;

private final Node root;
// the bounding box of the quadtree
private final Rectangle bbox;
private final String bbox_key;

// tags that can be returned in the get method
public 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 array
public 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<> ();
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 tags
preparedLocationInfo = preparer.getPreparedLocationInfo(boundaries);
if (boundaries == null || boundaries.size() == 0)
return;

HashMap<String,Boundary> bMap = new HashMap<>();
for (Boundary b: boundaries){
bMap.put(b.getId(), b);
boundaryTags.put(b.getId(), b.getTags());
}
sortBoundaryTagsMap();
// add the boundaries in a specific order
for (String id: boundaryTags.keySet()){
root.add (bMap.get(id).getArea(), id, null, DO_NOT_CLIP);
}
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 points
Coord 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<>(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<>();
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 tags
for (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 a new Area instance (might be empty)
*/
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 first
for (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 quadtree
root.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 it
ArrayList<String> ids = new ArrayList<>(boundaryTags.keySet());
Collections.sort(ids, new AdminLevelCollator());
Collections.reverse(ids);
HashMap<String,Tags> tmp = new LinkedHashMap<>(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 static void writeBoundaryTags(OutputStream stream, Tags tags, String id) throws IOException{
DataOutputStream dOutStream = new DataOutputStream(stream);
dOutStream.writeUTF("TAGS");
dOutStream.writeUTF(id);
// write the tags
int 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 searchBBox a bounding box. Areas not intersecting the bbox are
* ignored.
* @throws IOException
*/
private void readStreamQuadTreeFormat(DataInputStream inpStream,
uk.me.parabola.imgfmt.app.Area searchBBox) 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();
if (log.isDebugEnabled()){
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 ( searchBBox == null || searchBBox.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.warn(refs,id,treePath,"invalid or empty or too small area");
}
} 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 tree
private 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.getArea().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.getArea().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).getArea());
a.intersect(nodes.get(j).getArea());

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.parseInt(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 = 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 a shape and the related tags to the tree.
* @param shape the part of the boundary area that should be added to the tree.
* @param boundaryId id of the originating boundary
* @param refs A string containing boundaryIds and admin-level info
* of all boundaries with lower admin levels that share the same area.
* @param clipOption true: clip the shape with the bounding box of the nodeElem,
* false: use shape without clipping
*/
private void add(Shape shape, String boundaryId, String refs, boolean clipOption){
assert isLeaf;
Path2D.Double path;
if (clipOption){
path = ShapeSplitter.clipShape (shape, bbox);
// only add areas that intersect with this part of the tree
if (path == null)
return;
}
else
path = new Path2D.Double(shape);
if (nodes == null)
nodes = new ArrayList<>();
NodeElem nodeElem = new NodeElem(boundaryId, path, 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<>();
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){
path.append(area, false);
}
add(new Area(path), id, null, DO_NOT_CLIP);
}
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<>();
this.getAreas(areas, treePath, admLevel);
if (areas.isEmpty() == false){
Path2D.Double path = new Path2D.Double(PathIterator.WIND_NON_ZERO, 1024 * 1024);
for (Entry <String, List<Area>> entry : areas.entrySet()){
for (Area area: entry.getValue()){
path.append(area, false);
}
}
Area combinedArea = new Area(path);
return combinedArea;
}
return new Area();
}

/**
* 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.getArea());
if (aList == null){
aList = new ArrayList<>(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.getArea());
if (aList == null){
aList = new ArrayList<>(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();
if (DEBUG){
if (treePath.equals(DEBUG_TREEPATH) || DEBUG_TREEPATH.equals("all")){
for (NodeElem nodeElem: nodes){
nodeElem.saveGPX("start",treePath);
}
}
}

mergeEqualIds();
mergeLastRectangles();
if (DEBUG)
printNodes("prep", treePath);

List<NodeElem> reworked = new ArrayList<>();

// detect intersection of areas, merge tag info
for (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.getArea().isEmpty())
continue;

Rectangle2D rCurr = currElem.getArea().getBounds2D();

Rectangle2D rAdd = rCurr.createIntersection(toAdd.getArea().getBounds2D());
if (rAdd.isEmpty()){
continue;
}
// the bounding boxes intersect, so we have to find out if the areas also intersect
Area toAddxCurr = new Area(currElem.getArea());
toAddxCurr.intersect(toAdd.getArea());

if (!isWritable(toAddxCurr)){
continue; // empty or only too small fragments
}

Area toAddMinusCurr = new Area(toAdd.getArea());
toAddMinusCurr.subtract(currElem.getArea());

if (toAddMinusCurr.isEmpty()){
// toadd is fully covered by curr
if (toAdd.tagMask == POSTCODE_ONLY){
// if we get here, toAdd has only zip code that is already known
// in larger or equal area of currElem
toAdd.getArea().reset(); // ignore this
break;
}
}

// test if toAdd contains usable tag(s)
String chkMsg = currElem.checkAddTags(toAdd, bounds);
// warning: intersection of areas with equal levels
if (chkMsg != null){
if (DEBUG){
// save debug GPX for areas that wiil
// appear in warning message below
toAdd.saveGPX("warn_toAdd",treePath);
currElem.saveGPX("warn_curr",treePath);
}
log.warn(chkMsg);
}

Area currMinusToAdd = new Area(currElem.getArea());
currMinusToAdd.subtract(toAdd.getArea());

// remove intersection part from toAdd
toAdd.setArea(toAddMinusCurr);
if (!isWritable(currMinusToAdd)){
// curr is fully covered by toAdd
if (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 curr
currElem.setArea(currMinusToAdd);

if (toAdd.tagMask != POSTCODE_ONLY){
// combine tag info in intersection
intersect.addLocInfo(toAdd);
reworked.add(intersect);
}
}

if (toAdd.isValid())
reworked.add(toAdd);
}
nodes = reworked;
// free memory for nodes with empty or too small areas
removeEmptyAreas(treePath);

long dt = System.currentTimeMillis()-t1;
if (dt > 1000){
log.info(bbox_key, " : makeDistinct 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).getArea().add(nodes.get(i).getArea());
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 area
do{
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 boundary
if (prevNode.tagMask != POSTCODE_ONLY && lastNode.getArea().isRectangular() && prevNode.getArea().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 one
if (prevNode.getArea().equals(lastNode.getArea())){
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.getArea().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 areas
removeThis = true;
}else if (!isWritable(chkRemove.getArea())){
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 tuning
if (depth >= 5 || nodes.size() <= 7 || bounds.getHeight() < 10 || bounds.getWidth() < 10 ){
makeDistinct(treePath);
return ;
}

// mergeLastRectangles();
allocChilds();
for (NodeElem nodeElem: nodes){
Rectangle shapeBBox = nodeElem.shape.getBounds();
for (int i = 0; i < 4; i++){
if (childs[i].bbox.intersects(shapeBBox))
childs[i].add(nodeElem.shape, nodeElem.boundaryId, nodeElem.locationDataSrc, DO_CLIP);
}
}
// return memory to GC
nodes = null;
}
// finally try splitting the sub trees
for (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 node
private Area area;

private Shape shape; // for temp. use when splitting
// location relevant tags of boundaries that intersect with the bounding box of this node
private Tags locTags;

// a bit mask that helps comparing Tags
private short tagMask;
// boundary that was initially used
private final String boundaryId;
// data for the intersects_with tag
private String locationDataSrc;
private int srcPos;

/**
* Create a node element.
* @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 info
* 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 node element.
* @param boundaryId The boundary Id
* @param shape the (part of the) boundary area stored in this node
* @param refs A string containing boundaryIds and admin level info
* of all boundaries with lower admin levels that share the same area.
*/
NodeElem (String boundaryId, Shape shape, String refs){
srcPos = -1;
this.boundaryId = boundaryId;
this.shape = shape;
this.locationDataSrc = refs;
calcLocTags();
}

/**
* Create a new node element 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)
return false;
Area checkArea = getArea();
if (checkArea == null || checkArea.isEmpty()
|| checkArea.getBounds2D().getWidth() <= BoundaryUtil.MIN_DIMENSION && checkArea.getBounds2D().getHeight() <= BoundaryUtil.MIN_DIMENSION)
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:r998818
String[] 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;
else
this.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();
try(DataOutputStream dos = new DataOutputStream(oneItemStream)){
String id = this.boundaryId;
dos.writeUTF(treePath.substring(1));
dos.writeUTF(id);
if (this.locationDataSrc == null)
dos.writeUTF("");
else
dos.writeUTF(this.locationDataSrc);
BoundarySaver.writeArea(dos, this.getArea());
}
// now start to write into the real stream

// first write the bounding box so that is possible to skip the
// complete entry
uk.me.parabola.imgfmt.app.Area outBBox = Java2DConverter.createBbox(this.getArea());
DataOutputStream dOutStream = new DataOutputStream(stream);
dOutStream.writeUTF("AREA");
dOutStream.writeInt(outBBox.getMinLat());
dOutStream.writeInt(outBBox.getMinLong());
dOutStream.writeInt(outBBox.getMaxLat());
dOutStream.writeInt(outBBox.getMaxLong());

// write the size of the boundary block so that it is possible to
// skip it
byte[] data = oneItemStream.toByteArray();
assert data.length > 0 : "bSize is not > 0 : " + data.length;
dOutStream.writeInt(data.length);

// write the boundary block
dOutStream.write(data);
dOutStream.flush();
}

private Area getArea(){
if (shape != null){
area = new Area(shape);
shape = null;
}
return area;
}

private void setArea(Area area) {
this.area = area;
this.shape = null;
}

/**
* 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 area
for (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=122907
errMsg= "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 available
adminLevel1= BoundaryLocationPreparer.UNSET_ADMIN_LEVEL;
}
if (i2.getName() == null || i2.getName() == "?") {
// admin_level tag is set but no valid name available
adminLevel2= 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 Locator
if (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 boundaryId
return 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;
}
}

Subversion Repositories mkgmap

(root)/u/demon.box73/main/src/uk/me/parabola/mkgmap/reader/osm/boundary/BoundaryQuadTree.java - Rev 3431