Gerds patches inspired me to look for more things that could be improved.
I found that the Quadtree used in the LocationHook is not very optimal.
The patch is a first try to increase the performance. The time required
for the LocationHook is reduced by 10-50% which is great.
Warning: I haven't checked so far if the results are equal. So maybe
there are big bugs in the patch... (and the speedup comes from the poor
implementation)
I will do some more tests and optimizations but maybe some of you can
have a look on it, test it and comment it.
Have fun!
WanMil
Index: src/uk/me/parabola/mkgmap/reader/osm/LocationHook.java
===================================================================
--- src/uk/me/parabola/mkgmap/reader/osm/LocationHook.java (revision 2153)
+++ src/uk/me/parabola/mkgmap/reader/osm/LocationHook.java (working copy)
@@ -138,6 +138,7 @@
}
long tb1 = System.currentTimeMillis();
+ log.error("Creating quadtree took "+(tb1-t1)+" ms");
// Load the boundaries that intersect with the bounding box of the tile
List<Boundary> boundaries = BoundaryUtil.loadBoundaries(boundaryDir,
saver.getBoundingBox());
@@ -381,8 +382,8 @@
assignPreprocBounds();
}
- log.info("Location hook finished in",
- (System.currentTimeMillis() - t1), "ms");
+ log.error("Location hook finished in "+
+ (System.currentTimeMillis() - t1)+ " ms");
}
Index: src/uk/me/parabola/mkgmap/main/Main.java
===================================================================
--- src/uk/me/parabola/mkgmap/main/Main.java (revision 2153)
+++ src/uk/me/parabola/mkgmap/main/Main.java (working copy)
@@ -95,7 +95,8 @@
* @param args The command line arguments.
*/
public static void main(String[] args) {
-
+ long t1 = System.currentTimeMillis();
+
// We need at least one argument.
if (args.length < 1) {
System.err.println("Usage: mkgmap [options...] <file.osm>");
@@ -115,6 +116,9 @@
} catch (ExitException e) {
System.err.println(e.getMessage());
}
+ long t2 = System.currentTimeMillis();
+ System.out.println("Time: "+(t2-t1)+" ms");
+ log.error("Time: "+(t2-t1)+" ms");
}
/**
Index: src/uk/me/parabola/util/ElementQuadTreeNode.java
===================================================================
--- src/uk/me/parabola/util/ElementQuadTreeNode.java (revision 2153)
+++ src/uk/me/parabola/util/ElementQuadTreeNode.java (working copy)
@@ -1,10 +1,12 @@
package uk.me.parabola.util;
import java.awt.Rectangle;
+import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashSet;
import java.util.List;
-import java.util.Map.Entry;
import java.util.Set;
import uk.me.parabola.imgfmt.app.Area;
@@ -17,15 +19,68 @@
public final class ElementQuadTreeNode {
- private static final Logger log = Logger.getLogger(ElementQuadTreeNode.class);
+ private static final Logger log = Logger
+ .getLogger(ElementQuadTreeNode.class);
private static final int MAX_POINTS = 1000;
- private MultiHashMap<Coord, Element> points;
+ private MultiHashMap<Coord, Element> pointsOld;
+ private List<Object> points;
+ private int noPoints = 0;
+ private boolean sorted = true;
private final Area bounds;
private Area coveredBounds;
private long items = -1;
+ private final static class WayPoint extends HashSet<Coord> {
+ private final Way way;
+
+ public WayPoint(Way way) {
+ this.way = way;
+ }
+
+ public final Way getWay() {
+ return way;
+ }
+ }
+
+ private final static Comparator<Object> comp = new Comparator<Object>() {
+ private int getClassId(Object e) {
+ if (e instanceof Node) {
+ return 1;
+ }
+ if (e instanceof Way || e instanceof WayPoint) {
+ return 2;
+ }
+ if (e instanceof Relation) {
+ return 3;
+ }
+ return 4;
+ }
+
+ private long getId(Object e) {
+ if (e instanceof Element) {
+ return ((Element) e).getId();
+ } else if (e instanceof WayPoint) {
+ return ((WayPoint) e).getWay().getId();
+ }
+ return 0;
+ }
+
+ public int compare(Object o1, Object o2) {
+ if (o1 == o2) {
+ return 0;
+ }
+
+ long did = getId(o1) - getId(o2);
+ if (did != 0) {
+ return (did > 0 ? 1 : -1);
+ }
+
+ return getClassId(o1) - getClassId(o2);
+ }
+ };
+
public Area getCoveredBounds() {
return coveredBounds;
}
@@ -70,8 +125,7 @@
public ElementQuadTreeNode(Area bounds) {
this(bounds, Collections.<Element> emptyList());
}
-
-
+
public ElementQuadTreeNode(Collection<Element> elements) {
this.children = null;
@@ -80,7 +134,7 @@
int minLong = Integer.MAX_VALUE;
int maxLong = Integer.MIN_VALUE;
- this.points = new MultiHashMap<Coord, Element>();
+ this.pointsOld = new MultiHashMap<Coord, Element>();
for (Element el : elements) {
Collection<Coord> coords = null;
if (el instanceof Relation) {
@@ -88,14 +142,14 @@
} else if (el instanceof Way) {
Way w = (Way) el;
if (w.isClosed()) {
- coords = w.getPoints().subList(0, w.getPoints().size()-1);
+ coords = w.getPoints().subList(0, w.getPoints().size() - 1);
} else {
coords = w.getPoints();
}
} else if (el instanceof Node) {
coords = Collections.singleton(((Node) el).getLocation());
}
-
+
for (Coord c : coords) {
if (c.getLatitude() < minLat) {
minLat = c.getLatitude();
@@ -109,21 +163,21 @@
if (c.getLongitude() > maxLong) {
maxLong = c.getLongitude();
}
- points.add(c, el);
+ pointsOld.add(c, el);
}
}
coveredBounds = new Area(minLat, minLong, maxLat, maxLong);
this.bounds = coveredBounds;
-
- if (points.size() > MAX_POINTS) {
+
+ if (pointsOld.size() > MAX_POINTS) {
split();
- }
+ }
}
-
+
public long getSize() {
if (isLeaf()) {
- return points.size();
+ return noPoints;
} else {
if (items < 0) {
items = 0;
@@ -134,36 +188,38 @@
return items;
}
}
-
+
public int getDepth() {
if (isLeaf()) {
return 1;
} else {
int maxDepth = 0;
- for (ElementQuadTreeNode node :children) {
+ for (ElementQuadTreeNode node : children) {
maxDepth = Math.max(node.getDepth(), maxDepth);
}
- return maxDepth+1;
+ return maxDepth + 1;
}
}
-
-// public void outputBounds(String basename, int level) {
-//// if (level > 8 ) {
-//// return;
-//// }
-//
-// if (isLeaf()) {
-// GpxCreator.createAreaGpx(basename+level+"_"+points.keySet().size(), coveredBounds);
-//// GpxCreator.createGpx(basename+level+"p"+points.keySet().size(), new ArrayList<Coord>(), new ArrayList<Coord>(points.keySet()));
-// } else {
-//// GpxCreator.createAreaGpx(basename+level, coveredBounds);
-// int i = 0;
-// for (ElementQuadTreeNode node : children) {
-// i++;
-// node.outputBounds(basename+i+"_", level+1);
-// }
-// }
-// }
+
+ // public void outputBounds(String basename, int level) {
+ // // if (level > 8 ) {
+ // // return;
+ // // }
+ //
+ // if (isLeaf()) {
+ // GpxCreator.createAreaGpx(basename+level+"_"+points.keySet().size(),
+ // coveredBounds);
+ // // GpxCreator.createGpx(basename+level+"p"+points.keySet().size(), new
+ // ArrayList<Coord>(), new ArrayList<Coord>(points.keySet()));
+ // } else {
+ // // GpxCreator.createAreaGpx(basename+level, coveredBounds);
+ // int i = 0;
+ // for (ElementQuadTreeNode node : children) {
+ // i++;
+ // node.outputBounds(basename+i+"_", level+1);
+ // }
+ // }
+ // }
public ElementQuadTreeNode(Area bounds, Collection<Element> elements) {
this.bounds = bounds;
@@ -174,23 +230,41 @@
int minLong = Integer.MAX_VALUE;
int maxLong = Integer.MIN_VALUE;
- this.points = new MultiHashMap<Coord, Element>();
+ // this.pointsOld = new MultiHashMap<Coord, Element>();
+ points = new ArrayList<Object>(elements.size());
+ noPoints = 0;
for (Element el : elements) {
- Collection<Coord> coords = null;
+ // 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();
+ WayPoint wp = new WayPoint((Way) el);
+ wp.addAll(((Way) el).getPoints());
+ noPoints += wp.size();
+ for (Coord c : ((Way) el).getPoints()) {
+ 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(wp);
+ // 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());
- }
-
- for (Coord c : coords) {
+ // coords = Collections.singleton(((Node) el).getLocation());
+ Coord c = ((Node) el).getLocation();
if (c.getLatitude() < minLat) {
minLat = c.getLatitude();
}
@@ -203,27 +277,82 @@
if (c.getLongitude() > maxLong) {
maxLong = c.getLongitude();
}
- points.add(c, el);
+ noPoints++;
+ points.add(el);
}
+ // 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();
+ // }
+ // pointsOld.add(c, el);
+ // }
+
}
+ sorted = false;
if (minLat > maxLat || minLong > maxLong) {
- coveredBounds = new Area(bounds.getMinLat(), bounds.getMinLong(), bounds.getMinLat()+1, bounds.getMinLong()+1);
+ coveredBounds = new Area(bounds.getMinLat(), bounds.getMinLong(),
+ bounds.getMinLat() + 1, bounds.getMinLong() + 1);
} else {
coveredBounds = new Area(minLat, minLong, maxLat, maxLong);
}
- if (points.size() > MAX_POINTS) {
- split();
- }
+ // if (pointsOld.size() > MAX_POINTS) {
+ // split();
+ // }
+ checkSplit();
}
public Area getBounds() {
return this.bounds;
}
-
+
public Rectangle getRectBounds() {
- return new Rectangle(bounds.getMinLong(), bounds.getMinLat(), bounds.getWidth(), bounds.getHeight());
+ return new Rectangle(bounds.getMinLong(), bounds.getMinLat(),
+ bounds.getWidth(), bounds.getHeight());
+ }
+
+ private void ensureSorted() {
+ if (sorted) {
+ return;
+ }
+ Collections.sort(points, comp);
+ sorted = true;
+ }
+
+ private void addToList(Coord c, Element element) {
+ if (element instanceof Node) {
+ points.add(element);
+ noPoints++;
+ sorted = false;
+ } else if (element instanceof Way) {
+ ensureSorted();
+ int idx = Collections.binarySearch(points, element, comp);
+ if (idx < 0) {
+ WayPoint wp = new WayPoint((Way) element);
+ wp.add(c);
+ points.add(-(idx+1), wp);
+ } else {
+ WayPoint wp = (WayPoint) points.get(idx);
+ wp.add(c);
+ }
+ noPoints++;
+ }
+ }
+
+ private void checkSplit() {
+ if (noPoints > MAX_POINTS) {
+ split();
+ }
}
private boolean add(Coord c, Element element) {
@@ -239,9 +368,11 @@
c.getLongitude()));
}
if (isLeaf()) {
- points.add(c,element);
- if (points.size() > MAX_POINTS)
- split();
+ addToList(c, element);
+ checkSplit();
+ // pointsOld.add(c,element);
+ // if (pointsOld.size() > MAX_POINTS)
+ // split();
return true;
} else {
for (ElementQuadTreeNode nodes : children) {
@@ -264,11 +395,11 @@
Way w = (Way) c;
List<Coord> points;
if (w.isClosed()) {
- points = w.getPoints().subList(0, w.getPoints().size()-1);
+ 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;
@@ -277,7 +408,7 @@
} else if (c instanceof Node) {
return add(((Node) c).getLocation(), c);
} else {
- log.error("Unsupported element type: "+c);
+ log.error("Unsupported element type: " + c);
return false;
}
}
@@ -293,11 +424,11 @@
Way w = (Way) c;
List<Coord> points;
if (w.isClosed()) {
- points = w.getPoints().subList(0, w.getPoints().size()-1);
+ points = w.getPoints().subList(0, w.getPoints().size() - 1);
} else {
points = w.getPoints();
}
-
+
boolean allOk = true;
for (Coord cp : points) {
allOk = remove(cp, c) && allOk;
@@ -306,15 +437,32 @@
} else if (c instanceof Node) {
return remove(((Node) c).getLocation(), c);
} else {
- log.error("Unsupported element type: "+c);
+ log.error("Unsupported element type: " + c);
return false;
- }
+ }
}
-
+
private boolean remove(Coord c, Element elem) {
items = -1;
if (isLeaf()) {
- return points.remove(c, elem) != null;
+ ensureSorted();
+ int idx = Collections.binarySearch(points, elem, comp);
+ if (idx < 0) {
+ // not found
+ return false;
+ }
+
+ if (elem instanceof Node) {
+ points.remove(idx);
+ } else if (elem instanceof Way) {
+ WayPoint wp = (WayPoint) points.get(idx);
+ wp.remove(c);
+ if (wp.isEmpty()) {
+ points.remove(idx);
+ }
+ }
+ return true;
+ // return pointsOld.remove(c, elem) != null;
} else {
for (ElementQuadTreeNode child : children) {
if (child.getCoveredBounds().contains(c)) {
@@ -324,7 +472,7 @@
return false;
}
}
-
+
public Set<Element> get(Area bbox, Set<Element> resultList) {
if (getSize() == 0) {
return resultList;
@@ -337,19 +485,46 @@
// the bounding box is contained completely in the bbox
// => add all points without further check
- for (List<Element> elem : points.values())
- resultList.addAll(elem);
+ for (Object elem : points) {
+ if (elem instanceof Node) {
+ resultList.add((Node) elem);
+ } else if (elem instanceof WayPoint) {
+ resultList.add(((WayPoint) elem).getWay());
+ }
+ }
+ // for (List<Element> elem : pointsOld.values())
+ // resultList.addAll(elem);
} else {
// check each point
- for (Entry<Coord, List<Element>> e : points.entrySet()) {
- if (bbox.contains(e.getKey())) {
- resultList.addAll(e.getValue());
+ for (Object elem : points) {
+ if (elem instanceof Node) {
+ if (bbox.contains(((Node) elem).getLocation())) {
+ resultList.add((Node) elem);
+ }
+ } else if (elem instanceof WayPoint) {
+ // no need to check - the element is already in the result list
+ if (resultList.contains(((WayPoint) elem).getWay())) {
+ continue;
+ }
+ for (Coord c : (WayPoint) elem) {
+ if (bbox.contains(c)) {
+ resultList.add(((WayPoint) elem).getWay());
+ break;
+ }
+ }
}
}
+ //
+ // for (Entry<Coord, List<Element>> e : pointsOld.entrySet()) {
+ // if (bbox.contains(e.getKey())) {
+ // resultList.addAll(e.getValue());
+ // }
+ // }
}
} else {
for (ElementQuadTreeNode child : children) {
- if (child.getSize() > 0 && bbox.intersects(child.getCoveredBounds())) {
+ if (child.getSize() > 0
+ && bbox.intersects(child.getCoveredBounds())) {
resultList = child.get(bbox, resultList);
}
}
@@ -361,21 +536,52 @@
Set<Element> resultList) {
if (getSize() > 0 && polygon.getBbox().intersects(getBounds())) {
if (isLeaf()) {
- for (Entry<Coord, List<Element>> e : points.entrySet()) {
- if (polygon.getArea().contains(e.getKey().getLongitude(),
- e.getKey().getLatitude())) {
- resultList.addAll(e.getValue());
+ for (Object elem : points) {
+ if (elem instanceof Node) {
+ if (resultList.contains(elem)) {
+ continue;
+ }
+ Coord c = ((Node) elem).getLocation();
+ if (polygon.getArea().contains(c.getLongitude(),
+ c.getLatitude())) {
+ resultList.add((Node) elem);
+ }
+ } else if (elem instanceof WayPoint) {
+ if (resultList.contains(((WayPoint) elem).getWay())) {
+ continue;
+ }
+ for (Coord c : (WayPoint) elem) {
+ if (polygon.getArea().contains(c.getLongitude(),
+ c.getLatitude())) {
+ resultList.add(((WayPoint) elem).getWay());
+ break;
+ }
+ }
}
}
+
+ // for (Entry<Coord, List<Element>> e : pointsOld.entrySet()) {
+ // if (polygon.getArea().contains(e.getKey().getLongitude(),
+ // e.getKey().getLatitude())) {
+ // resultList.addAll(e.getValue());
+ // }
+ // }
} else {
for (ElementQuadTreeNode child : children) {
- if (child.getSize() > 0 && polygon.getArea().intersects(child.getRectBounds())) {
+ if (child.getSize() > 0
+ && polygon.getArea().intersects(
+ child.getRectBounds())) {
java.awt.geom.Area subArea = (java.awt.geom.Area) polygon
.getArea().clone();
-
- subArea.intersect(createArea(new Area(child.getBounds().getMinLat()-1,child.getBounds().getMinLong()-1,child.getBounds().getMaxLat()+1, child.getBounds().getMaxLong()+1)));
+
+ subArea.intersect(createArea(new Area(child.getBounds()
+ .getMinLat() - 1, child.getBounds()
+ .getMinLong() - 1, child.getBounds()
+ .getMaxLat() + 1, child.getBounds()
+ .getMaxLong() + 1)));
if (subArea.isEmpty() == false)
- child.get(new ElementQuadTreePolygon(subArea), resultList);
+ child.get(new ElementQuadTreePolygon(subArea),
+ resultList);
}
}
}
@@ -395,7 +601,7 @@
private void split() {
if (bounds.getHeight() <= 5 || bounds.getWidth() <= 5) {
- log.error("Do not split more due to too small bounds: "+bounds);
+ log.error("Do not split more due to too small bounds: " + bounds);
return;
}
@@ -411,23 +617,37 @@
bounds.getMaxLong());
Area neBounds = new Area(halfLat, halfLong, bounds.getMaxLat(),
bounds.getMaxLong());
-
+
children[0] = new ElementQuadTreeNode(swBounds);
children[1] = new ElementQuadTreeNode(nwBounds);
children[2] = new ElementQuadTreeNode(seBounds);
children[3] = new ElementQuadTreeNode(neBounds);
-
- MultiHashMap<Coord, Element> copyPoints = points;
+
+ List<Object> copyPoints = points;
points = null;
- for (Entry<Coord, List<Element>> c : copyPoints.entrySet()) {
- for (Element el : c.getValue())
- add(c.getKey(), el);
+// MultiHashMap<Coord, Element> copyPoints = pointsOld;
+// pointsOld = null;
+ for (Object elem : copyPoints) {
+ if (elem instanceof Node) {
+ add(((Node) elem).getLocation(),(Node)elem);
+ } else if (elem instanceof WayPoint) {
+ for (Coord c : (WayPoint)elem) {
+ add(c,((WayPoint) elem).getWay());
+ }
+ }
}
+// 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 MultiHashMap<Coord, Element>();
+ // pointsOld = new MultiHashMap<Coord, Element>();
+ noPoints = 0;
+ points = new ArrayList<Object>();
+ sorted = true;
coveredBounds = new Area(Integer.MAX_VALUE, Integer.MAX_VALUE,
Integer.MIN_VALUE, Integer.MIN_VALUE);
}
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
