Depending on the sea complexity some countries really take a lot more
time for rendering now. (Norway went from 5 minutes to 45 minutes). I
don't really mind as my upload speed is still a lot slower than my PC
compiling on my weekly updates.
This is caused by the new mp code. The methods contains(JoinedWay,
JoinedWay) and createContainsMatrix(..) are not optimal for large and
lots of polygons (both apply to Norway).
Attached patch is a first try to speedup these methods. I haven't tested
this patch very much (not enough time yet). At least I didn't measure if
it really speeds up the calculation. I expect a minimum speedup of
factor two.
So if you don't want to be a kind of test candidate please throw it
away. Otherwise feel free to compile Norway with it. I am curious about
the results.
WanMil
Index: src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
===================================================================
--- src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
(revision 1502)
+++ src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
(working copy)
@@ -1,6 +1,7 @@
package uk.me.parabola.mkgmap.reader.osm;
-import java.awt.*;
+import java.awt.Polygon;
+import java.awt.Rectangle;
import java.awt.geom.Area;
import java.awt.geom.Line2D;
import java.awt.geom.PathIterator;
@@ -8,6 +9,7 @@
import java.util.Arrays;
import java.util.BitSet;
import java.util.Collections;
+import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
@@ -16,6 +18,7 @@
import java.util.concurrent.LinkedBlockingQueue;
import java.util.logging.Level;
+import sun.awt.image.IntegerComponentRaster;
import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.log.Logger;
@@ -337,7 +340,7 @@
log.info("from",
way.getPoints().get(0).toOSMURL());
log.info("to",
way.getPoints().get(way.getPoints().size() - 1)
.toOSMURL());
- // mark this ways as artificially closed
+ // mark this ways as artifically closed
way.closeWayArtificial();
}
}
@@ -357,8 +360,9 @@
JoinedWay tempWay = it.next();
if (tempWay.isClosed() == false) {
if (first) {
- log.warn(
- "Cannot join the following ways
to closed polygons. MP-Relation",
+ log
+ .warn(
+ "Cannot
join the following ways to closed polygons. MP-Relation",
toBrowseURL());
}
logWayURLs(Level.WARNING, "- way:", tempWay);
@@ -810,7 +814,9 @@
*/
private Way singularAreaToWay(Area area, long wayId) {
if (area.isSingular() == false) {
- log.warn("singularAreaToWay called with non singular
area. Multipolygon ",
+ log
+ .warn(
+ "singularAreaToWay
called with non singular area. Multipolygon ",
toBrowseURL());
}
if (area.isEmpty()) {
@@ -870,6 +876,9 @@
/**
* This is a QA method. All ways of the given wayList are checked if
they
* they carry the checkRole. If not a warning is logged.
+ *
+ * @param wayList
+ * @param checkRole
*/
private void checkRoles(List<Way> wayList, String checkRole) {
// QA: check that all ways carry the role "inner" and issue
warnings
@@ -886,28 +895,32 @@
* Creates a matrix which polygon contains which polygon. A polygon
does not
* contain itself.
*
- * @param poplygonList
+ * @param polygonList
* a list of polygons
*/
- private void createContainsMatrix(List<JoinedWay> poplygonList) {
+ private void createContainsMatrix(List<JoinedWay> polygonList) {
+ if (polygonList.size() > 10) {
+ createContainsMatrixForBigLists(polygonList);
+ return;
+ }
containsMatrix = new ArrayList<BitSet>();
- for (int i = 0; i < poplygonList.size(); i++) {
+ for (int i = 0; i < polygonList.size(); i++) {
containsMatrix.add(new BitSet());
}
// mark which ring contains which ring
- for (int i = 0; i < poplygonList.size(); i++) {
- JoinedWay tempRing = poplygonList.get(i);
+ for (int i = 0; i < polygonList.size(); i++) {
+ JoinedWay tempRing = polygonList.get(i);
BitSet bitSet = containsMatrix.get(i);
- for (int j = 0; j < poplygonList.size(); j++) {
- boolean contains;
+ for (int j = 0; j < polygonList.size(); j++) {
+ boolean contains = false;
if (i == j) {
// this is special: a way does not
contain itself for
// our usage here
contains = false;
} else {
- contains = contains(tempRing,
poplygonList.get(j));
+ contains = contains(tempRing,
polygonList.get(j));
}
if (contains) {
@@ -928,57 +941,65 @@
* this is an alternative createContainsMatrix method seems to speed up
only
* if lots of inner ways are in the mulitpolygon
*/
- // private void createContainsMatrix(List<JoinedWay> wayList) {
- // long t1 = System.currentTimeMillis();
- //
- // for (int i = 0; i < wayList.size(); i++) {
- // containsMatrix.add(new BitSet());
- // }
- //
- // // use this matrix to check which matrix element has been
- // // calculated
- // ArrayList<BitSet> finishedMatrix = new
ArrayList<BitSet>(wayList.size());
- //
- // for (int i = 0; i < wayList.size(); i++) {
- // BitSet matrixRow = new BitSet();
- // // an element does not contain itself
- // matrixRow.set(i);
- // finishedMatrix.add(matrixRow);
- // }
- //
- // for (int rowIndex = 0; rowIndex < wayList.size(); rowIndex++) {
- // Way potentialOuterRing = wayList.get(rowIndex);
- // BitSet containsColumns = containsMatrix.get(rowIndex);
- // BitSet finishedCol = finishedMatrix.get(rowIndex);
- //
- // // get all non calculated columns of the matrix
- // for (int colIndex = finishedCol.nextClearBit(0); colIndex >= 0 &&
- // colIndex < wayList.size(); colIndex = finishedCol
- // .nextClearBit(colIndex + 1)) {
- //
- // boolean contains = contains(potentialOuterRing,
wayList.get(colIndex));
- //
- // if (contains) {
- // containsColumns.set(colIndex);
- //
- // // we also know that the inner ring does not contain the outer ring
- // // so we can set the finished bit for this matrix element
- // finishedMatrix.get(colIndex).set(rowIndex);
- //
- // // additionally we know that the outer ring contains all rings
- // // that are contained by the inner ring
- // containsColumns.or(containsMatrix.get(colIndex));
- // finishedCol.or(containsColumns);
- // }
- //
- // // this matrix element is calculated now
- // finishedCol.set(colIndex);
- // }
- // }
- //
- // long t2 = System.currentTimeMillis();
- // log.warn("createMatrix",(t2-t1),"ms");
- // }
+ private void createContainsMatrixForBigLists(List<JoinedWay> wayList) {
+ long t1 = System.currentTimeMillis();
+
+ log.debug("createContainsMatrix listSize:",wayList.size());
+ containsMatrix = new ArrayList<BitSet>(wayList.size());
+ for (int i = 0; i < wayList.size(); i++) {
+ containsMatrix.add(new BitSet());
+ }
+
+ // use this matrix to check which matrix element has been
+ // calculated
+ ArrayList<BitSet> finishedMatrix = new
ArrayList<BitSet>(wayList.size());
+
+ for (int i = 0; i < wayList.size(); i++) {
+ BitSet matrixRow = new BitSet();
+ // an element does not contain itself
+ matrixRow.set(i);
+ finishedMatrix.add(matrixRow);
+ }
+
+ for (int rowIndex = 0; rowIndex < wayList.size(); rowIndex++) {
+ JoinedWay potentialOuterRing = wayList.get(rowIndex);
+ BitSet containsColumns = containsMatrix.get(rowIndex);
+ BitSet finishedCol = finishedMatrix.get(rowIndex);
+
+ log.debug("check polygon",rowIndex);
+
+
+ // get all non calculated columns of the matrix
+ for (int colIndex = finishedCol.nextClearBit(0);
colIndex >= 0
+ && colIndex < wayList.size(); colIndex
= finishedCol
+ .nextClearBit(colIndex + 1)) {
+
+ boolean contains = contains(potentialOuterRing,
wayList
+ .get(colIndex));
+
+ if (contains) {
+ containsColumns.set(colIndex);
+
+ // we also know that the inner ring
does not contain the
+ // outer ring
+ // so we can set the finished bit for
this matrix element
+
finishedMatrix.get(colIndex).set(rowIndex);
+
+ // additionally we know that the outer
ring contains all
+ // rings
+ // that are contained by the inner ring
+
containsColumns.or(containsMatrix.get(colIndex));
+ finishedCol.or(containsColumns);
+ }
+
+ // this matrix element is calculated now
+ finishedCol.set(colIndex);
+ }
+ }
+
+ long t2 = System.currentTimeMillis();
+ log.warn("createMatrix for", wayList.size(),"polygons took",
(t2 - t1), "ms");
+ }
/**
* Checks if the ring with ringIndex1 contains the ring with ringIndex2.
@@ -994,7 +1015,7 @@
*
* @param ring1
* a closed way
- * @param ring2 A second closed way.
+ * @param ring2
* @return true if ring1 contains ring2
*/
private boolean contains(JoinedWay ring1, JoinedWay ring2) {
@@ -1012,26 +1033,57 @@
// way2
return false;
}
+ // TODO check if p0 is on any of the lines of ring2
// check all lines of way1 and way2 for intersections
Iterator<Coord> it2 = ring2.getPoints().iterator();
Coord p2_1 = it2.next();
+ Coord p2_2 = null;
while (it2.hasNext()) {
- Coord p2_2 = p2_1;
+ p2_2 = p2_1;
p2_1 = it2.next();
+ int lonMin = Math.min(p2_1.getLongitude(),
p2_2.getLongitude());
+ int lonMax = Math.max(p2_1.getLongitude(),
p2_2.getLongitude());
+ int latMin = Math.min(p2_1.getLatitude(),
p2_2.getLatitude());
+ int latMax = Math.max(p2_1.getLatitude(),
p2_2.getLatitude());
+// Rectangle bbox2 = new Rectangle(lonMin, latMin,
lonMax-lonMin, latMax-latMin);
+
Iterator<Coord> it1 = ring1.getPoints().iterator();
Coord p1_1 = it1.next();
+ Coord p1_2 = null;
+
+ int lonStatus = p1_1.getLongitude()<lonMin ? -1 :
p1_1.getLongitude() > lonMax ? 1 : 0;
+ int latStatus = p1_1.getLatitude()<latMin ? -1 :
p1_1.getLatitude() > latMax ? 1 : 0;
+
while (it1.hasNext()) {
- Coord p1_2 = p1_1;
+ p1_2 = p1_1;
p1_1 = it1.next();
- boolean intersects =
Line2D.linesIntersect(p1_1.getLongitude(),
+ int changes = 0;
+ if (lonStatus < 0 && p1_1.getLongitude() <
lonMin) {
+ } else if (lonStatus > 0 && p1_1.getLongitude()
> lonMax) {
+ } else {
+ changes++;
+ lonStatus = p1_1.getLongitude()<lonMin
? -1 : p1_1.getLongitude() > lonMax ? 1 : 0;
+ }
+ if (latStatus < 0 && p1_1.getLatitude() <
latMin) {
+ } else if (latStatus > 0 && p1_1.getLatitude()
> latMax) {
+ } else {
+ changes++;
+ latStatus = p1_1.getLatitude()<latMin ?
-1 : p1_1.getLatitude() > latMax ? 1 : 0;
+ }
+
+ boolean intersects =
+ ((lonStatus == 0 && latStatus==0) ||
changes == 2)
+ &&
Line2D.linesIntersect(p1_1.getLongitude(),
p1_1.getLatitude(),
p1_2.getLongitude(), p1_2
.getLatitude(),
p2_1.getLongitude(), p2_1
.getLatitude(),
p2_2.getLongitude(), p2_2
.getLatitude());
+ // TODO check if one of the points only touches
the other ring
+
if (intersects) {
if ((ring1.isClosedArtificially() &&
it1.hasNext() == false)
||
(ring2.isClosedArtificially() && it2.hasNext() == false)) {
@@ -1079,7 +1131,7 @@
*/
private static class JoinedWay extends Way {
private final List<Way> originalWays;
- private boolean closedArtifical;
+ private boolean closedArtifical = false;
public JoinedWay(Way originalWay) {
super(FakeIdGenerator.makeFakeId(), new
ArrayList<Coord>(
@@ -1145,6 +1197,7 @@
}
}
+ @Override
public String toString() {
StringBuilder sb = new StringBuilder(200);
sb.append(getId());
@@ -1175,6 +1228,7 @@
JoinedWay ring;
public RingStatus(boolean outer, int index, JoinedWay ring) {
+ super();
this.outer = outer;
this.index = index;
this.ring = ring;
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
