After the index branch has been developed so far that we can use the
results in MapSource (thanks to Steve!!) there is a big need for a
mechanism to fill missing location information.
There has been a lot of discussion about that. It stopped because it was
quite theoretical (from my point of view). Therefore I have started to
implement a prototype osm hook that tries to complete the missing
location information. I think the is_in tag is quite problematic
therefore I decided to use the addr tags.
Attached is a *very* early implementation that makes use of the boundary
polygons. It checks all nodes and ways/polygons within all boundary
polygons and fills the missing addr tags.
I think this is a better foundation for the discussion how we want to
fill the missing location information.
Before flaming me about terrible code please be aware that:
* the patch is not optimized
* it's version 1, so far away from handling all situations / countries
* it's a very early prototype
I would be happy if you try it and make some proposals how it could be
improved.
Some improvements I already know and thinking about:
* The new hook should run after the multipolygon finishing and not before
* The is_in tag should be handled
* boundary information propagation => First go through all boundaries
and add the information from higher levels to lower ones, i.e. add
addr:district to all city boundaries within that district
* Use landuse=residential information in combination with the place nodes
* In case a boundary level is missing (which mostly will be the case for
countries admin_level=2), select the addr information from all nodes and
ways within a boundary by using the most used addr-tag value. (in
germany the addr:country=DE should be the most used)
Have fun!
WanMil
Index: src/uk/me/parabola/util/ElementQuadTree.java
===================================================================
--- src/uk/me/parabola/util/ElementQuadTree.java (revision 1860)
+++ src/uk/me/parabola/util/ElementQuadTree.java (working copy)
@@ -2,69 +2,72 @@
import java.util.ArrayList;
import java.util.Collection;
-import java.util.Collections;
import java.util.Iterator;
import java.util.List;
-import java.util.ListIterator;
import uk.me.parabola.imgfmt.app.Area;
import uk.me.parabola.imgfmt.app.Coord;
-import uk.me.parabola.util.QuadTreeNode.QuadTreePolygon;
+import uk.me.parabola.mkgmap.reader.osm.Element;
+import uk.me.parabola.util.ElementQuadTreeNode.QuadTreePolygon;
-public class QuadTree {
+public class ElementQuadTree {
- private final QuadTreeNode root;
+ private final ElementQuadTreeNode root;
private long itemCount;
- public QuadTree(Area bbox) {
- this.root = new QuadTreeNode(bbox);
+ public ElementQuadTree(Area bbox) {
+ this.root = new ElementQuadTreeNode(bbox);
this.itemCount = 0;
}
- public boolean addAll(Collection<Coord> coordList) {
+ public ElementQuadTree(Collection<Element> elements) {
+ this.root = new ElementQuadTreeNode(elements);
+ this.itemCount = 0;
+ }
+
+ public boolean addAll(Collection<Element> elements) {
boolean oneAdded = false;
- for (Coord c : coordList) {
- oneAdded = add(c) | oneAdded;
+ for (Element element : elements) {
+ oneAdded = add(element) | oneAdded;
}
return oneAdded;
}
- public boolean add(Coord c) {
+ public boolean add(Element element) {
- boolean added = root.add(c);
+ boolean added = root.add(element);
if (added) {
itemCount++;
}
return added;
}
- public List<Coord> get(Area bbox) {
- return root.get(bbox, new ArrayList<Coord>(2000));
+ public MultiHashMap<Coord, Element> get(Area bbox) {
+ return root.get(bbox, new MultiHashMap<Coord, Element>());
}
- public List<Coord> get(Collection<List<Coord>> polygons) {
- return root.get(new QuadTreePolygon(polygons), new ArrayList<Coord>(
- 2000));
+ public MultiHashMap<Coord, Element> get(Collection<List<Coord>> polygons) {
+ return root.get(new QuadTreePolygon(polygons),
+ new MultiHashMap<Coord, Element>());
}
- public List<Coord> get(List<Coord> polygon) {
+ public MultiHashMap<Coord, Element> get(List<Coord> polygon) {
return get(polygon, 0);
}
- public List<Coord> get(List<Coord> polygon, int offset) {
+ public MultiHashMap<Coord, Element> get(List<Coord> polygon, int offset) {
if (polygon.size() < 3) {
- return Collections.emptyList();
+ return new MultiHashMap<Coord, Element>();
}
if (polygon.get(0).equals(polygon.get(polygon.size() - 1)) == false) {
return null;
}
- ArrayList<Coord> points = root.get(new QuadTreePolygon(polygon),
- new ArrayList<Coord>(2000));
+ MultiHashMap<Coord, Element> points = root.get(new QuadTreePolygon(polygon),
+ new MultiHashMap<Coord, Element>());
if (offset > 0) {
- ListIterator<Coord> pointIter = points.listIterator();
- while (pointIter.hasNext()) {
- if (isCloseToPolygon(pointIter.next(), polygon, offset)) {
- pointIter.remove();
+ for (Coord c : new ArrayList<Coord>(points.keySet())) {
+ if (isCloseToPolygon(c, polygon, offset)) {
+ points.remove(c);
}
}
}
@@ -76,7 +79,8 @@
root.clear();
}
- public long getSize() {
+ // TODO itemCount is not a good counter (coords or elements?)
+ private long getSize() {
return itemCount;
}
Property changes on: src\uk\me\parabola\util\ElementQuadTree.java
___________________________________________________________________
Added: svn:mime-type
+ text/plain
Index: src/uk/me/parabola/util/ElementQuadTreeNode.java
===================================================================
--- src/uk/me/parabola/util/ElementQuadTreeNode.java (revision 1860)
+++ src/uk/me/parabola/util/ElementQuadTreeNode.java (working copy)
@@ -1,20 +1,26 @@
package uk.me.parabola.util;
-import java.awt.*;
-import java.util.ArrayList;
+import java.awt.Rectangle;
import java.util.Collection;
import java.util.Collections;
-import java.util.HashSet;
import java.util.List;
+import java.util.Map.Entry;
import uk.me.parabola.imgfmt.app.Area;
import uk.me.parabola.imgfmt.app.Coord;
+import uk.me.parabola.log.Logger;
+import uk.me.parabola.mkgmap.reader.osm.Element;
+import uk.me.parabola.mkgmap.reader.osm.Node;
+import uk.me.parabola.mkgmap.reader.osm.Relation;
+import uk.me.parabola.mkgmap.reader.osm.Way;
+
+public class ElementQuadTreeNode {
-public class QuadTreeNode {
+ private static final Logger log = Logger.getLogger(ElementQuadTreeNode.class);
private static final int MAX_POINTS = 20;
- private Collection<Coord> points;
+ private MultiHashMap<Coord, Element> points;
private final Area bounds;
private Area coveredBounds;
@@ -22,7 +28,7 @@
return coveredBounds;
}
- private QuadTreeNode[] children;
+ private ElementQuadTreeNode[] children;
public static final class QuadTreePolygon {
private final java.awt.geom.Area javaArea;
@@ -59,47 +65,114 @@
}
}
- public QuadTreeNode(Area bounds) {
- this(bounds, Collections.<Coord>emptyList());
+ public ElementQuadTreeNode(Area bounds) {
+ this(bounds, Collections.<Element> emptyList());
}
- public QuadTreeNode(Area bounds, Collection<Coord> points) {
- this.bounds = bounds;
+
+ public ElementQuadTreeNode(Collection<Element> elements) {
this.children = null;
int minLat = Integer.MAX_VALUE;
int maxLat = Integer.MIN_VALUE;
int minLong = Integer.MAX_VALUE;
int maxLong = Integer.MIN_VALUE;
- for (Coord c : points) {
- if (c.getLatitude() < minLat) {
- minLat = c.getLatitude();
+
+ this.points = new MultiHashMap<Coord, Element>();
+ for (Element el : elements) {
+ Collection<Coord> coords = null;
+ if (el instanceof Relation) {
+ continue;
+ } else if (el instanceof Way) {
+ Way w = (Way) el;
+ if (w.isClosed()) {
+ coords = w.getPoints().subList(0, w.getPoints().size()-1);
+ } else {
+ coords = w.getPoints();
+ }
+ } else if (el instanceof Node) {
+ coords = Collections.singleton(((Node) el).getLocation());
}
- if (c.getLatitude() > maxLat) {
- maxLat = c.getLatitude();
+
+ for (Coord c : coords) {
+ if (c.getLatitude() < minLat) {
+ minLat = c.getLatitude();
+ }
+ if (c.getLatitude() > maxLat) {
+ maxLat = c.getLatitude();
+ }
+ if (c.getLongitude() < minLong) {
+ minLong = c.getLongitude();
+ }
+ if (c.getLongitude() > maxLong) {
+ maxLong = c.getLongitude();
+ }
+ points.add(c, el);
}
- if (c.getLongitude() < minLong) {
- minLong = c.getLongitude();
+
+ }
+ coveredBounds = new Area(minLat, minLong, maxLat, maxLong);
+ this.bounds = coveredBounds;
+
+ if (points.size() > MAX_POINTS) {
+ split();
+ }
+ }
+
+ public ElementQuadTreeNode(Area bounds, Collection<Element> elements) {
+ this.bounds = bounds;
+ this.children = null;
+
+ int minLat = Integer.MAX_VALUE;
+ int maxLat = Integer.MIN_VALUE;
+ int minLong = Integer.MAX_VALUE;
+ int maxLong = Integer.MIN_VALUE;
+
+ this.points = new MultiHashMap<Coord, Element>();
+ for (Element el : elements) {
+ Collection<Coord> coords = null;
+ if (el instanceof Relation) {
+ continue;
+ } else if (el instanceof Way) {
+ Way w = (Way) el;
+ if (w.isClosed()) {
+ coords = w.getPoints().subList(0, w.getPoints().size()-1);
+ } else {
+ coords = w.getPoints();
+ }
+ } else if (el instanceof Node) {
+ coords = Collections.singleton(((Node) el).getLocation());
}
- if (c.getLongitude() > maxLong) {
- maxLong = c.getLongitude();
+
+ for (Coord c : coords) {
+ if (c.getLatitude() < minLat) {
+ minLat = c.getLatitude();
+ }
+ if (c.getLatitude() > maxLat) {
+ maxLat = c.getLatitude();
+ }
+ if (c.getLongitude() < minLong) {
+ minLong = c.getLongitude();
+ }
+ if (c.getLongitude() > maxLong) {
+ maxLong = c.getLongitude();
+ }
+ points.add(c, el);
}
+
}
coveredBounds = new Area(minLat, minLong, maxLat, maxLong);
if (points.size() > MAX_POINTS) {
- this.points = points;
split();
- } else {
- this.points = new HashSet<Coord>(points);
- }
+ }
}
public Area getBounds() {
return this.bounds;
}
- public boolean add(Coord c) {
+ private boolean add(Coord c, Element element) {
if (coveredBounds == null) {
coveredBounds = new Area(c.getLatitude(), c.getLongitude(),
c.getLatitude(), c.getLongitude());
@@ -111,21 +184,49 @@
c.getLongitude()));
}
if (isLeaf()) {
- boolean added = points.add(c);
+ points.add(c,element);
if (points.size() > MAX_POINTS)
split();
- return added;
+ return true;
} else {
- for (QuadTreeNode nodes : children) {
+ for (ElementQuadTreeNode nodes : children) {
if (nodes.getBounds().contains(c)) {
- return nodes.add(c);
+ return nodes.add(c, element);
}
}
return false;
}
}
- public List<Coord> get(Area bbox, List<Coord> resultList) {
+ public boolean add(Element c) {
+ if (c instanceof Relation) {
+ log.error("Relations are not supported by this quadtree implementation. Skipping relation "
+ + c.toBrowseURL());
+ return false;
+ } else if (c instanceof Way) {
+ // add all points to the tree
+ Way w = (Way) c;
+ List<Coord> points;
+ if (w.isClosed()) {
+ points = w.getPoints().subList(0, w.getPoints().size()-1);
+ } else {
+ points = w.getPoints();
+ }
+
+ boolean allOk = true;
+ for (Coord cp : points) {
+ allOk = add(cp, c) && allOk;
+ }
+ return allOk;
+ } else if (c instanceof Node) {
+ return add(((Node) c).getLocation(), c);
+ } else {
+ log.error("Unsupported element type: "+c);
+ return false;
+ }
+ }
+
+ public MultiHashMap<Coord, Element> get(Area bbox, MultiHashMap<Coord, Element> resultList) {
if (isLeaf()) {
if (bbox.getMinLat() <= coveredBounds.getMinLat()
&& bbox.getMaxLat() >= coveredBounds.getMaxLat()
@@ -134,17 +235,18 @@
// the bounding box is contained completely in the bbox
// => add all points without further check
- resultList.addAll(points);
+ resultList.putAll(points);
} else {
// check each point
- for (Coord c : points) {
- if (bbox.contains(c)) {
- resultList.add(c);
+ for (Entry<Coord, List<Element>> e : points.entrySet()) {
+ if (bbox.contains(e.getKey())) {
+ for (Element el : e.getValue())
+ resultList.add(e.getKey(), el);
}
}
}
} else {
- for (QuadTreeNode child : children) {
+ for (ElementQuadTreeNode child : children) {
if (bbox.intersects(child.getCoveredBounds())) {
resultList = child.get(bbox, resultList);
}
@@ -153,17 +255,19 @@
return resultList;
}
- public ArrayList<Coord> get(QuadTreePolygon polygon, ArrayList<Coord> resultList) {
+ public MultiHashMap<Coord, Element> get(QuadTreePolygon polygon,
+ MultiHashMap<Coord, Element> resultList) {
if (polygon.getBbox().intersects(getBounds())) {
if (isLeaf()) {
- for (Coord c : points) {
- if (polygon.getArea().contains(c.getLongitude(),
- c.getLatitude())) {
- resultList.add(c);
+ for (Entry<Coord, List<Element>> e : points.entrySet()) {
+ if (polygon.getArea().contains(e.getKey().getLongitude(),
+ e.getKey().getLatitude())) {
+ for (Element el : e.getValue())
+ resultList.add(e.getKey(),el);
}
}
} else {
- for (QuadTreeNode child : children) {
+ for (ElementQuadTreeNode child : children) {
if (polygon.getBbox().intersects(child.getBounds())) {
java.awt.geom.Area subArea = (java.awt.geom.Area) polygon
.getArea().clone();
@@ -193,7 +297,7 @@
int halfLat = (bounds.getMinLat() + bounds.getMaxLat()) / 2;
int halfLong = (bounds.getMinLong() + bounds.getMaxLong()) / 2;
- children = new QuadTreeNode[4];
+ children = new ElementQuadTreeNode[4];
Area swBounds = new Area(bounds.getMinLat(), bounds.getMinLong(),
halfLat, halfLong);
@@ -204,21 +308,22 @@
Area neBounds = new Area(halfLat + 1, halfLong + 1, bounds.getMaxLat(),
bounds.getMaxLong());
- children[0] = new QuadTreeNode(swBounds);
- children[1] = new QuadTreeNode(nwBounds);
- children[2] = new QuadTreeNode(seBounds);
- children[3] = new QuadTreeNode(neBounds);
+ children[0] = new ElementQuadTreeNode(swBounds);
+ children[1] = new ElementQuadTreeNode(nwBounds);
+ children[2] = new ElementQuadTreeNode(seBounds);
+ children[3] = new ElementQuadTreeNode(neBounds);
- Collection<Coord> copyPoints = points;
+ MultiHashMap<Coord, Element> copyPoints = points;
points = null;
- for (Coord c : copyPoints) {
- add(c);
+ for (Entry<Coord, List<Element>> c : copyPoints.entrySet()) {
+ for (Element el : c.getValue())
+ add(c.getKey(), el);
}
}
public void clear() {
this.children = null;
- points = new HashSet<Coord>();
+ points = new MultiHashMap<Coord, Element>();
coveredBounds = new Area(Integer.MAX_VALUE, Integer.MAX_VALUE,
Integer.MIN_VALUE, Integer.MIN_VALUE);
}
Property changes on: src\uk\me\parabola\util\ElementQuadTreeNode.java
___________________________________________________________________
Added: svn:mime-type
+ text/plain
Index: src/uk/me/parabola/mkgmap/reader/osm/AddressHook.java
===================================================================
--- src/uk/me/parabola/mkgmap/reader/osm/AddressHook.java (revision 0)
+++ src/uk/me/parabola/mkgmap/reader/osm/AddressHook.java (revision 0)
@@ -0,0 +1,103 @@
+package uk.me.parabola.mkgmap.reader.osm;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+import java.util.TreeMap;
+
+import uk.me.parabola.imgfmt.app.Coord;
+import uk.me.parabola.log.Logger;
+import uk.me.parabola.util.ElementQuadTree;
+import uk.me.parabola.util.EnhancedProperties;
+import uk.me.parabola.util.MultiHashMap;
+
+public class AddressHook extends OsmReadingHooksAdaptor {
+ private static final Logger log = Logger.getLogger(AddressHook.class);
+
+ private ElementSaver saver;
+
+ private final TreeMap<Integer, String> levelTags = new TreeMap<Integer, String>() {
+ {
+ put(2,"addr:country");
+ put(3,"addr:province");
+ put(4,"addr:province");
+ put(5,"addr:district");
+ put(6,"addr:subdistrict");
+ put(7,"addr:subdistrict");
+ put(8,"addr:city");
+ put(9,"addr:city");
+ put(10,"addr:city");
+ }
+ };
+
+ public boolean init(ElementSaver saver, EnhancedProperties props) {
+ this.saver = saver;
+ return true;
+ }
+
+ @Override
+ public void end() {
+ List<Element> elements = new ArrayList<Element>(saver.getWays().size()
+ + saver.getNodes().size());
+
+ MultiHashMap<Integer, Way> boundaries = new MultiHashMap<Integer, Way>();
+
+ for (Node node : saver.getNodes().values()) {
+ if (node.getTagCount() > 0) {
+ elements.add(node);
+ }
+ }
+ for (Way way : saver.getWays().values()) {
+ if (way.getTagCount() == 0) {
+ continue;
+ }
+ if (way.isClosed()
+ && "administrative".equals(way.getTag("boundary"))
+ && way.getTag("admin_level") != null) {
+ {
+ try {
+ int adminlevel = Integer.valueOf(way
+ .getTag("admin_level"));
+ if (adminlevel >= 0 && adminlevel <= 10) {
+ boundaries.add(adminlevel, way);
+ }
+ } catch (NumberFormatException nfe) {
+ log.error(nfe, nfe);
+ }
+ }
+ }
+
+ // in any case add it to the element list
+ elements.add(way);
+
+ }
+
+ ElementQuadTree quadTree = new ElementQuadTree(elements);
+ elements.clear();
+
+ for (int adminlevel : levelTags.keySet()) {
+ String tag = levelTags.get(adminlevel);
+ List<Way> levelBoundaries = boundaries.get(adminlevel);
+ for (Way boundary : levelBoundaries) {
+ if (boundary.getName() == null) {
+ continue;
+ }
+
+ MultiHashMap<Coord, Element> elems = quadTree.get(boundary
+ .getPoints());
+ HashSet<Element> uniqueElems = new HashSet<Element>();
+ for (List<Element> elemList : elems.values()) {
+ uniqueElems.addAll(elemList);
+ }
+
+ for (Element elem : uniqueElems) {
+ if (elem.getTag(tag) == null) {
+ elem.addTag(tag, boundary.getName());
+ }
+ }
+ }
+ }
+
+ }
+
+}
Index: src/uk/me/parabola/mkgmap/reader/osm/ElementSaver.java
===================================================================
--- src/uk/me/parabola/mkgmap/reader/osm/ElementSaver.java (revision 1860)
+++ src/uk/me/parabola/mkgmap/reader/osm/ElementSaver.java (working copy)
@@ -564,6 +564,10 @@
map.put(p, inc);
}
+ public Map<Long, Node> getNodes() {
+ return nodeMap;
+ }
+
public Map<Long, Way> getWays() {
return wayMap;
}
Index: src/uk/me/parabola/mkgmap/reader/osm/OsmMapDataSource.java
===================================================================
--- src/uk/me/parabola/mkgmap/reader/osm/OsmMapDataSource.java (revision 1860)
+++ src/uk/me/parabola/mkgmap/reader/osm/OsmMapDataSource.java (working copy)
@@ -53,6 +53,7 @@
private final OsmReadingHooks[] POSSIBLE_HOOKS = {
new SeaGenerator(),
new HighwayHooks(),
+ new AddressHook(),
};
private OsmConverter converter;
private final Set<String> usedTags = new HashSet<String>();
Index: src/uk/me/parabola/mkgmap/reader/osm/Element.java
===================================================================
--- src/uk/me/parabola/mkgmap/reader/osm/Element.java (revision 1860)
+++ src/uk/me/parabola/mkgmap/reader/osm/Element.java (working copy)
@@ -27,6 +27,10 @@
private String name;
private long id;
+ public int getTagCount() {
+ return (tags == null ? 0 : tags.size());
+ }
+
/**
* Add a tag to the way. Some tags are recognised separately and saved in
* separate fields.
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
