I've found and fixed another performance bottleneck:
The init method of the LocationHook contained a check if there is any
bounds file in the boundary directory. On my computer this check
requires ~1200ms. This is done for each tile and must be perfomed once
only.
So attached patch saves additionally 1200ms for each tile :-)
WanMil
I tried to improve the first patch by removing anything not required in
the Quadtree and by using a different internal data structure.
I've seen performance improvements but please try and test yourself :-)
The most time is now spend in the creation of the Quadtree. So if you
want to search for more performance just start there.
WanMil
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
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
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)
@@ -54,7 +54,10 @@
.compile("[,;]+");
public static final String BOUNDS_OPTION = "bounds";
-
+
+ private static File checkedBoundaryDir;
+ private static boolean checkBoundaryDirOk;
+
private final static Hashtable<String, String> mkgmapTags = new Hashtable<String, String>() {
{
put("admin_level=1", "mkgmap:admin_level1");
@@ -92,57 +95,77 @@
nameTags.addAll(LocatorUtil.getNameTags(props));
if (autofillOptions.contains(BOUNDS_OPTION)) {
-
boundaryDir = new File(props.getProperty("bounds", "bounds"));
- if (boundaryDir.exists() == false) {
- log.error("Disable LocationHook because boundary directory does not exist. Dir: "
- + boundaryDir);
- return false;
- }
- File[] boundaryFiles = boundaryDir.listFiles(new FileFilter() {
- public boolean accept(File pathname) {
- return (pathname.isFile() && pathname.getName().endsWith(
- ".bnd"));
- }
+ long t1 = System.currentTimeMillis();
- });
- if (boundaryFiles == null || boundaryFiles.length == 0) {
- log.error("Disable LocationHook because boundary directory contains no boundary files. Dir: "
- + boundaryDir);
- return false;
+ synchronized (BOUNDS_OPTION) {
+ // checking of the boundary dir is expensive
+ // check once only and reuse the result
+ if (boundaryDir.equals(checkedBoundaryDir)) {
+ if (checkBoundaryDirOk == false) {
+ log.error("Disable LocationHook because boundary directory is unusable. Dir: "+boundaryDir);
+ return false;
+ }
+ } else {
+ checkedBoundaryDir = boundaryDir;
+ checkBoundaryDirOk = false;
+
+ if (boundaryDir.exists() == false) {
+ log.error("Disable LocationHook because boundary directory does not exist. Dir: "
+ + boundaryDir);
+ return false;
+ }
+ File[] boundaryFiles = boundaryDir.listFiles(new FileFilter() {
+ public boolean accept(File pathname) {
+ return (pathname.isFile() && pathname.getName()
+ .endsWith(".bnd"));
+ }
+ });
+ if (boundaryFiles == null || boundaryFiles.length == 0) {
+ log.error("Disable LocationHook because boundary directory contains no boundary files. Dir: "
+ + boundaryDir);
+ return false;
+ }
+
+ // passed all checks => boundaries are ok
+ checkBoundaryDirOk = true;
+ }
}
+ log.error("Checking bounds dir took "
+ + (System.currentTimeMillis() - t1) + " ms");
}
return true;
}
private void assignPreprocBounds() {
long t1 = System.currentTimeMillis();
- ElementQuadTree quadTree = new ElementQuadTree(saver.getBoundingBox());
+
+ List<Element> elemList = new ArrayList<Element>(saver.getNodes().size()+saver.getWays().size());
// add all nodes that might be converted to a garmin node (tagcount > 0)
for (Node node : saver.getNodes().values()) {
if (node.getTagCount() > 0) {
- quadTree.add(node);
+ elemList.add(node);
}
}
// add all ways that might be converted to a garmin way (tagcount > 0)
// and save all polygons that contains location information
for (Way way : saver.getWays().values()) {
- if (way.getTagCount() == 0) {
- continue;
+ if (way.getTagCount() > 0) {
+ elemList.add(way);
}
-
- // in any case add it to the element list
- quadTree.add(way);
}
+ log.error("Creating quadlist took "+(System.currentTimeMillis()-t1)+" ms");
+ ElementQuadTree quadTree = new ElementQuadTree(saver.getBoundingBox(), elemList);
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());
long tb2 = System.currentTimeMillis();
- log.info("Loading boundaries took "+(tb2-tb1)+" ms");
+ log.error("Loading boundaries took "+(tb2-tb1)+" ms");
// go through all boundaries, check if the necessary tags are available
// and standardize the country name to the 3 letter ISO code
@@ -190,11 +213,11 @@
Collections.reverse(boundaries);
- log.info("LocationHook prepared after",
- (System.currentTimeMillis() - t1), "ms");
+ log.error("Preproc bounds sorted after "+
+ (System.currentTimeMillis() - tb2)+ " ms");
- log.info("Quadtree depth: "+quadTree.getDepth());
- log.info("Quadtree coords: "+quadTree.getCoordSize());
+// log.info("Quadtree depth: "+quadTree.getDepth());
+// log.info("Quadtree coords: "+quadTree.getCoordSize());
// Map the boundaryid to the boundary for fast access
Map<String, Boundary> boundaryById = new HashMap<String, Boundary>();
@@ -338,8 +361,10 @@
}
bIter.remove();
- if (quadTree.getCoordSize() <= 0) {
- log.info("Finish Location Hook: Remaining boundaries: "+boundaries.size());
+ if (quadTree.isEmpty()) {
+ if (log.isInfoEnabled()) {
+ log.info("Finish Location Hook: Remaining boundaries: "+boundaries.size());
+ }
return;
}
}
@@ -373,6 +398,8 @@
return true;
}
+ private static long sumTime = 0;
+
public void end() {
long t1 = System.currentTimeMillis();
log.info("Starting with location hook");
@@ -381,8 +408,11 @@
assignPreprocBounds();
}
- log.info("Location hook finished in",
- (System.currentTimeMillis() - t1), "ms");
+ long dt = (System.currentTimeMillis() - t1);
+ log.error("Location hook finished in "+
+ dt+ " ms");
+ sumTime += dt;
+ log.error("Sum: "+sumTime);
}
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,14 @@
* @param args The command line arguments.
*/
public static void main(String[] args) {
-
+// try {
+// Thread.sleep(30000L);
+// } catch (InterruptedException exp) {
+// // TODO Auto-generated catch block
+// exp.printStackTrace();
+// }
+ long t1 = System.currentTimeMillis();
+
// We need at least one argument.
if (args.length < 1) {
System.err.println("Usage: mkgmap [options...] <file.osm>");
@@ -115,6 +122,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/ElementQuadTree.java
===================================================================
--- src/uk/me/parabola/util/ElementQuadTree.java (revision 2153)
+++ src/uk/me/parabola/util/ElementQuadTree.java (working copy)
@@ -13,41 +13,13 @@
public class ElementQuadTree {
private final ElementQuadTreeNode root;
- private long itemCount;
-
- public ElementQuadTree(Area bbox) {
- this.root = new ElementQuadTreeNode(bbox);
- this.itemCount = 0;
- }
-
- public ElementQuadTree(Collection<Element> elements) {
- this.root = new ElementQuadTreeNode(elements);
- this.itemCount = 0;
- }
- public boolean addAll(Collection<Element> elements) {
- boolean oneAdded = false;
- for (Element element : elements) {
- oneAdded = add(element) | oneAdded;
- }
- return oneAdded;
+ public ElementQuadTree(Area bbox, Collection<Element> elements) {
+ this.root = new ElementQuadTreeNode(bbox, elements);
}
- public boolean add(Element element) {
-
- boolean added = root.add(element);
- if (added) {
- itemCount++;
- }
- return added;
- }
-
- public boolean remove(Element element) {
- boolean removed = root.remove(element);
- if (removed) {
- itemCount--;
- }
- return removed;
+ public void remove(Element element) {
+ root.remove(element);
}
public Set<Element> get(Area bbox) {
@@ -81,9 +53,13 @@
public long getCoordSize() {
return root.getSize();
}
+
+ public boolean isEmpty() {
+ return root.isEmpty();
+ }
+
public void clear() {
- itemCount = 0;
root.clear();
}
}
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,9 +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.HashMap;
import java.util.List;
+import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
@@ -12,23 +15,22 @@
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 final class ElementQuadTreeNode {
- private static final Logger log = Logger.getLogger(ElementQuadTreeNode.class);
+ private static final Logger log = Logger
+ .getLogger(ElementQuadTreeNode.class);
+ private static final List<Coord> EMPTY_LIST = Collections.emptyList();
+
private static final int MAX_POINTS = 1000;
- private MultiHashMap<Coord, Element> points;
+ private Map<Element, List<Coord>> elementMap;
private final Area bounds;
- private Area coveredBounds;
- private long items = -1;
+ private final Rectangle boundsRect;
- public Area getCoveredBounds() {
- return coveredBounds;
- }
+ private Boolean empty;
private ElementQuadTreeNode[] children;
@@ -67,289 +69,197 @@
}
}
- public ElementQuadTreeNode(Area bounds) {
- this(bounds, Collections.<Element> emptyList());
- }
-
-
- 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;
-
- 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());
- }
-
- 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();
+ 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;
+ }
}
- points.add(c, el);
}
-
}
- coveredBounds = new Area(minLat, minLong, maxLat, maxLong);
- this.bounds = coveredBounds;
-
- if (points.size() > MAX_POINTS) {
- split();
- }
+ return empty;
}
+
public long getSize() {
if (isLeaf()) {
- return points.size();
+ int items = 0;
+ for (List<Coord> points : elementMap.values()) {
+ if (points == EMPTY_LIST) {
+ items++;
+ } else {
+ items += points.size();
+ }
+ }
+ return items;
} else {
- if (items < 0) {
- items = 0;
- for (ElementQuadTreeNode child : children) {
+ int items = 0;
+ for (ElementQuadTreeNode child : children) {
items += child.getSize();
- }
}
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);
+ // }
+ // }
+ // }
+
+ private ElementQuadTreeNode(Area bounds, Map<Element, List<Coord>> elements) {
+ this.bounds = bounds;
+ boundsRect = new Rectangle(bounds.getMinLong(), bounds.getMinLat(),
+ bounds.getWidth(), bounds.getHeight());
+ this.children = null;
+ elementMap =elements;
+ empty = elementMap.isEmpty();
+
+ checkSplit();
+ }
+
+
public ElementQuadTreeNode(Area bounds, Collection<Element> elements) {
this.bounds = bounds;
+ boundsRect = new Rectangle(bounds.getMinLong(), bounds.getMinLat(),
+ bounds.getWidth(), bounds.getHeight());
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>();
+ this.elementMap = new HashMap<Element, List<Coord>>();
+
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();
- }
+ if (el instanceof Way) {
+ List<Coord> points = ((Way) el).getPoints();
+ // no need to create a copy of the points because the list is never changed
+ elementMap.put(el, points);
} else if (el instanceof Node) {
- coords = Collections.singleton(((Node) el).getLocation());
+ elementMap.put(el, EMPTY_LIST);
}
-
- 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 (minLat > maxLat || minLong > maxLong) {
- 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();
- }
+ empty = elementMap.isEmpty();
+ checkSplit();
}
public Area getBounds() {
return this.bounds;
}
-
- public Rectangle getRectBounds() {
- return new Rectangle(bounds.getMinLong(), bounds.getMinLat(), bounds.getWidth(), bounds.getHeight());
- }
- private boolean add(Coord c, Element element) {
- items = -1;
- if (coveredBounds == null) {
- coveredBounds = new Area(c.getLatitude(), c.getLongitude(),
- c.getLatitude(), c.getLongitude());
- } else if (coveredBounds.contains(c) == false) {
- coveredBounds = new Area(Math.min(coveredBounds.getMinLat(),
- c.getLatitude()), Math.min(coveredBounds.getMinLong(),
- c.getLongitude()), Math.max(coveredBounds.getMaxLat(),
- c.getLatitude()), Math.max(coveredBounds.getMaxLong(),
- c.getLongitude()));
- }
- if (isLeaf()) {
- points.add(c,element);
- if (points.size() > MAX_POINTS)
- split();
- return true;
- } else {
- for (ElementQuadTreeNode nodes : children) {
- if (nodes.getBounds().contains(c)) {
- return nodes.add(c, element);
- }
- }
- return false;
- }
+ public Rectangle getRectBounds() {
+ return boundsRect;
}
- public boolean add(Element c) {
- items = -1;
- 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;
+ private void checkSplit() {
+ if (getSize() > MAX_POINTS) {
+ split();
}
}
- public boolean remove(Element c) {
- items = -1;
- 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 = remove(cp, c) && allOk;
- }
- return allOk;
- } else if (c instanceof Node) {
- return remove(((Node) c).getLocation(), c);
- } else {
- log.error("Unsupported element type: "+c);
- return false;
- }
- }
-
- private boolean remove(Coord c, Element elem) {
- items = -1;
+ public void remove(Element elem) {
if (isLeaf()) {
- return points.remove(c, elem) != null;
+ elementMap.remove(elem);
+ empty = elementMap.isEmpty();
} else {
- for (ElementQuadTreeNode child : children) {
- if (child.getCoveredBounds().contains(c)) {
- return child.remove(c, elem);
+ if (elem instanceof Node) {
+ Node n = (Node) elem;
+ for (ElementQuadTreeNode child : children) {
+ if (child.getBounds().contains(n.getLocation())) {
+ child.remove(elem);
+ if (child.isEmpty()) {
+ // update the empty flag
+ empty = null;
+ }
+ break;
+ }
+ }
+ } else if (elem instanceof Way) {
+ for (ElementQuadTreeNode child : children) {
+ for (Coord c : ((Way) elem).getPoints()) {
+ if (child.getBounds().contains(c)) {
+ // found one point covered by the child
+ // => remove the element and check the next child
+ child.remove(elem);
+ if (empty != null && child.isEmpty()) {
+ empty = null;
+ }
+ break;
+ }
+ }
}
}
- return false;
}
}
-
+
public Set<Element> get(Area bbox, Set<Element> resultList) {
- if (getSize() == 0) {
+ if (isEmpty()) {
return resultList;
}
if (isLeaf()) {
- if (bbox.getMinLat() <= coveredBounds.getMinLat()
- && bbox.getMaxLat() >= coveredBounds.getMaxLat()
- && bbox.getMinLong() <= coveredBounds.getMinLong()
- && bbox.getMaxLong() >= coveredBounds.getMaxLong()) {
+ if (bbox.getMinLat() <= bounds.getMinLat()
+ && bbox.getMaxLat() >= bounds.getMaxLat()
+ && bbox.getMinLong() <= bounds.getMinLong()
+ && bbox.getMaxLong() >= bounds.getMaxLong()) {
// the bounding box is contained completely in the bbox
// => add all points without further check
- for (List<Element> elem : points.values())
- resultList.addAll(elem);
+ resultList.addAll(elementMap.keySet());
} else {
// check each point
- for (Entry<Coord, List<Element>> e : points.entrySet()) {
- if (bbox.contains(e.getKey())) {
- resultList.addAll(e.getValue());
+ for (Entry<Element, List<Coord>> elem : elementMap.entrySet()) {
+ if (elem.getKey() instanceof Node) {
+ Node n = (Node) elem.getKey();
+ if (bbox.contains(n.getLocation())) {
+ resultList.add(n);
+ }
+ } else if (elem.getKey() instanceof Way) {
+ // no need to check - the element is already in the result list
+ if (resultList.contains(elem.getKey())) {
+ continue;
+ }
+ for (Coord c : elem.getValue()) {
+ if (bbox.contains(c)) {
+ resultList.add(elem.getKey());
+ break;
+ }
+ }
}
}
}
} else {
for (ElementQuadTreeNode child : children) {
- if (child.getSize() > 0 && bbox.intersects(child.getCoveredBounds())) {
+ if (child.isEmpty() == false
+ && bbox.intersects(child.getBounds())) {
resultList = child.get(bbox, resultList);
}
}
@@ -359,23 +269,49 @@
public Set<Element> get(ElementQuadTreePolygon polygon,
Set<Element> resultList) {
- if (getSize() > 0 && polygon.getBbox().intersects(getBounds())) {
+ if (isEmpty()) {
+ return resultList;
+ }
+ if (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 (Entry<Element, List<Coord>> elem : elementMap.entrySet()) {
+ if (resultList.contains(elem.getKey())) {
+ continue;
+ }
+ if (elem.getKey() instanceof Node) {
+ Node n = (Node)elem.getKey();
+ Coord c = n.getLocation();
+ if (polygon.getArea().contains(c.getLongitude(),
+ c.getLatitude())) {
+ resultList.add(n);
+ }
+ } else if (elem.getKey() instanceof Way) {
+ for (Coord c : elem.getValue()) {
+ if (polygon.getArea().contains(c.getLongitude(),
+ c.getLatitude())) {
+ resultList.add(elem.getKey());
+ break;
+ }
+ }
}
}
} else {
for (ElementQuadTreeNode child : children) {
- if (child.getSize() > 0 && polygon.getArea().intersects(child.getRectBounds())) {
+ if (child.isEmpty()==false
+ && 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(Java2DConverter.createBoundsArea(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);
}
}
}
@@ -384,51 +320,76 @@
}
- private java.awt.geom.Area createArea(Area bbox) {
- return new java.awt.geom.Area(new Rectangle(bbox.getMinLong(),
- bbox.getMinLat(), bbox.getWidth(), bbox.getHeight()));
- }
-
public boolean isLeaf() {
- return points != null;
+ return elementMap != null;
}
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;
}
int halfLat = (bounds.getMinLat() + bounds.getMaxLat()) / 2;
int halfLong = (bounds.getMinLong() + bounds.getMaxLong()) / 2;
children = new ElementQuadTreeNode[4];
-
- Area swBounds = new Area(bounds.getMinLat(), bounds.getMinLong(),
+ Area[] childBounds = new Area[4];
+
+ childBounds[0] = new Area(bounds.getMinLat(), bounds.getMinLong(),
halfLat, halfLong);
- Area nwBounds = new Area(halfLat, bounds.getMinLong(),
+ childBounds[1] = new Area(halfLat, bounds.getMinLong(),
bounds.getMaxLat(), halfLong);
- Area seBounds = new Area(bounds.getMinLat(), halfLong, halfLat,
+ childBounds[2] = new Area(bounds.getMinLat(), halfLong, halfLat,
bounds.getMaxLong());
- Area neBounds = new Area(halfLat, halfLong, bounds.getMaxLat(),
+ childBounds[3] = 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);
+
+ List<Map<Element, List<Coord>>> childElems = new ArrayList<Map<Element, List<Coord>>>(4);
+ for (int i = 0; i < 4; i++) {
+ childElems.add(new HashMap<Element, List<Coord>>());
+ }
+ for (Entry<Element,List<Coord>> elem : elementMap.entrySet()) {
+ if (elem.getKey() instanceof Node) {
+ Node node = (Node) elem.getKey();
+ for (int i = 0; i < childBounds.length; i++) {
+ if (childBounds[i].contains(node.getLocation())) {
+ childElems.get(i).put(node, EMPTY_LIST);
+ break;
+ }
+ }
+ } else if (elem.getKey() instanceof Way) {
+ List<List<Coord>> points = new ArrayList<List<Coord>>(4);
+ for (int i = 0; i < 4; i++) {
+ // usually ways are quite local
+ // therefore there is a high probability that only one child is covered
+ // dim the new list as the old list
+ points.add(new ArrayList<Coord>(elem.getValue().size()));
+ }
+ for (Coord c : elem.getValue()) {
+ for (int i = 0; i < childBounds.length; i++) {
+ if (childBounds[i].contains(c)) {
+ points.get(i).add(c);
+ break;
+ }
+ }
+ }
+ for (int i = 0; i< 4; i++) {
+ if (points.get(i).isEmpty()==false) {
+ childElems.get(i).put(elem.getKey(), points.get(i));
+ }
+ }
+ }
+ }
- MultiHashMap<Coord, Element> copyPoints = points;
- points = null;
- for (Entry<Coord, List<Element>> c : copyPoints.entrySet()) {
- for (Element el : c.getValue())
- add(c.getKey(), el);
+ for (int i = 0; i < 4; i++) {
+ children[i] = new ElementQuadTreeNode(childBounds[i], childElems.get(i));
}
+
+ elementMap = null;
}
public void clear() {
this.children = null;
- points = new MultiHashMap<Coord, Element>();
- coveredBounds = new Area(Integer.MAX_VALUE, Integer.MAX_VALUE,
- Integer.MIN_VALUE, Integer.MIN_VALUE);
+ elementMap = new HashMap<Element, List<Coord>>();
}
}
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
