Hi,
I implemented a shrinking remove in the elementquadtree which is used by
the LocationHook. If enough elements have been removed the depth of the
quadtree is shrinked.
Sometimes this improves the performance, sometimes not.
The patch seems to be not 100% correct because I do get different
numbers of query results from the quadtree (patched finds 24974922 in 66
tiles, unpatched finds 24974934 elements in 66 tiles).
WanMil
Index: src/uk/me/parabola/mkgmap/reader/osm/LocationHook.java
===================================================================
--- src/uk/me/parabola/mkgmap/reader/osm/LocationHook.java (revision 2166)
+++ src/uk/me/parabola/mkgmap/reader/osm/LocationHook.java (working copy)
@@ -226,6 +226,8 @@
return boundaries;
}
+ private static long assignedElements = 0;
+
private void assignPreprocBounds() {
long t1 = System.currentTimeMillis();
@@ -367,6 +369,7 @@
// search for all elements in the boundary area
Set<Element> elemsInLocation = quadTree.get(boundary.getArea());
+ assignedElements += elemsInLocation.size();
// create list of required tags that are not set by this boundary
List<String> requiredTags = new ArrayList<String>();
@@ -446,6 +449,7 @@
long dt = (System.currentTimeMillis() - t1);
log.info("Location hook finished in", dt, "ms");
+ log.info("Assigned elements: "+assignedElements);
}
Index: src/uk/me/parabola/mkgmap/main/Main.java
===================================================================
--- src/uk/me/parabola/mkgmap/main/Main.java (revision 2166)
+++ src/uk/me/parabola/mkgmap/main/Main.java (working copy)
@@ -93,9 +93,12 @@
* to be used for creating summary files like the TDB and gmapsupp.
*
* @param args The command line arguments.
+ * @throws InterruptedException
*/
- public static void main(String[] args) {
-
+ public static void main(String[] args) throws InterruptedException {
+// Thread.sleep(30000);
+
+
// We need at least one argument.
if (args.length < 1) {
System.err.println("Usage: mkgmap [options...] <file.osm>");
Index: src/uk/me/parabola/util/ElementQuadTreeNode.java
===================================================================
--- src/uk/me/parabola/util/ElementQuadTreeNode.java (revision 2166)
+++ src/uk/me/parabola/util/ElementQuadTreeNode.java (working copy)
@@ -40,7 +40,7 @@
private static final List<Coord> EMPTY_LIST = Collections.emptyList();
/** The maximum number of coords in the quadtree node. */
- private static final int MAX_POINTS = 1000;
+ private static final int MAX_ELEMENTS = 500;
/** Maps elements to its coords located in this quadtree node. */
private Map<Element, List<Coord>> elementMap;
@@ -49,9 +49,9 @@
private final Area bounds;
private final Rectangle boundsRect;
- /** Flag if this node and all subnodes are empty */
- private Boolean empty;
-
+ /** number of elements in this quadtree node and all subnodes */
+ private int elementSize;
+
/** The subnodes in case this node is not a leaf */
private ElementQuadTreeNode[] children;
@@ -95,28 +95,21 @@
* @return <code>true</code> this quadtree node does not contain any elements; <code>false</code> else
*/
public boolean isEmpty() {
- if (empty == null) {
- if (isLeaf()) {
- empty = elementMap.isEmpty();
- } else {
- empty = true;
- for (ElementQuadTreeNode child : children) {
- if (child.isEmpty()==false) {
- empty = false;
- break;
- }
- }
- }
- }
- return empty;
+ return elementSize == 0;
}
+ public int getElementSize() {
+ return elementSize;
+ }
/**
* Retrieves the number of coords hold by this quadtree node and all subnodes.
* @return the number of coords
*/
public long getSize() {
+ if (isEmpty()) {
+ return 0;
+ }
if (isLeaf()) {
int items = 0;
for (List<Coord> points : elementMap.values()) {
@@ -158,7 +151,7 @@
bounds.getWidth(), bounds.getHeight());
this.children = null;
elementMap =elements;
- empty = elementMap.isEmpty();
+ this.elementSize = elementMap.size();
checkSplit();
}
@@ -181,7 +174,8 @@
elementMap.put(el, EMPTY_LIST);
}
}
- empty = elementMap.isEmpty();
+ this.elementSize = elementMap.size();
+
checkSplit();
}
@@ -197,7 +191,7 @@
* Checks if this quadtree node exceeds the maximum size and splits it in such a case.
*/
private void checkSplit() {
- if (getSize() > MAX_POINTS) {
+ if (isLeaf() && getElementSize() > MAX_ELEMENTS) {
split();
}
}
@@ -207,24 +201,31 @@
* @param elem the element to be removed
* @param bbox the bounding box of the element
*/
- private void remove(Element elem, Area bbox) {
+ private int remove(Element elem, Area bbox) {
if (bbox == null || isEmpty()) {
- return;
+ return 0;
}
+ int elementSizeBefore = elementSize;
if (isLeaf()) {
elementMap.remove(elem);
- empty = elementMap.isEmpty();
+ elementSize = elementMap.size();
} else {
+
for (ElementQuadTreeNode child : children) {
if (child.getBounds().intersects(bbox)) {
- child.remove(elem, bbox);
- if (child.isEmpty()) {
- // update the empty flag
- empty = null;
- }
+ elementSize -= child.remove(elem, bbox);
}
}
+
+ if (elementSize <= MAX_ELEMENTS) {
+ reduce();
+ }
}
+
+ // return how many elements have been removed
+ // this can be more than 1 because a way might have been counted as 2 (or more) because
+ // it is split over more childs
+ return elementSizeBefore-elementSize;
}
/**
@@ -389,6 +390,32 @@
return elementMap != null;
}
+ private void reduce() {
+ // check if the node can be reduced
+ boolean allChildLeafs = true;
+ for (ElementQuadTreeNode child : children) {
+ if (child.isLeaf() == false) {
+ allChildLeafs = false;
+ break;
+ }
+ }
+ if (allChildLeafs && getElementSize() <= MAX_ELEMENTS) {
+ // reduce the node
+ elementMap = children[0].elementMap;
+ for (int childNo = 1; childNo < children.length; childNo++) {
+ ElementQuadTreeNode child = children[childNo];
+ for (Entry<Element, List<Coord>> childElems : child.elementMap.entrySet()) {
+ List<Coord> otherCoordList = elementMap.put(childElems.getKey(), childElems.getValue());
+ if (otherCoordList != null) {
+ childElems.getValue().addAll(otherCoordList);
+ }
+ }
+ }
+ children = null;
+ elementSize = elementMap.size();
+ }}
+
+
/**
* Splits this quadtree node into 4 subnodes.
*/
@@ -453,6 +480,12 @@
children[i] = new ElementQuadTreeNode(childBounds[i], childElems.get(i));
}
+ // recalculate the element size
+ elementSize = 0;
+ for (ElementQuadTreeNode child : children) {
+ elementSize += child.getElementSize();
+ }
+
elementMap = null;
}
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
