Attached patch can be summarized very easy:
* Major speedup for mp code
Please test and commit if no problems arise.
WanMil
Index: src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
===================================================================
--- src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
(revision 1505)
+++ src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
(working copy)
@@ -1,9 +1,11 @@
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;
+import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
@@ -337,7 +339,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 +359,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 +813,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 +875,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 checkRoles
*/
private void checkRoles(List<Way> wayList, String checkRole) {
// QA: check that all ways carry the role "inner" and issue
warnings
@@ -886,37 +894,83 @@
* 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) {
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);
- BitSet bitSet = containsMatrix.get(i);
+ long t1 = System.currentTimeMillis();
+
+ if (log.isDebugEnabled())
+ log.debug("createContainsMatrix listSize:",
polygonList.size());
- for (int j = 0; j < poplygonList.size(); j++) {
- boolean contains;
- if (i == j) {
- // this is special: a way does not
contain itself for
- // our usage here
- contains = false;
+ // use this matrix to check which matrix element has been
+ // calculated
+ ArrayList<BitSet> finishedMatrix = new
ArrayList<BitSet>(polygonList
+ .size());
+
+ for (int i = 0; i < polygonList.size(); i++) {
+ BitSet matrixRow = new BitSet();
+ // a polygon does not contain itself
+ matrixRow.set(i);
+ finishedMatrix.add(matrixRow);
+ }
+
+ for (int rowIndex = 0; rowIndex < polygonList.size();
rowIndex++) {
+ JoinedWay potentialOuterRing =
polygonList.get(rowIndex);
+ BitSet containsColumns = containsMatrix.get(rowIndex);
+ BitSet finishedCol = finishedMatrix.get(rowIndex);
+
+ if (log.isDebugEnabled())
+ log.debug("check polygon", rowIndex);
+
+ // get all non calculated columns of the matrix
+ for (int colIndex = finishedCol.nextClearBit(0);
colIndex >= 0
+ && colIndex < polygonList.size();
colIndex = finishedCol
+ .nextClearBit(colIndex + 1)) {
+
+ JoinedWay innerPolygon =
polygonList.get(colIndex);
+
+ if (potentialOuterRing.getBounds().intersects(
+ innerPolygon.getBounds()) ==
false) {
+ // both polygons do not intersect
+ // we can flag both matrix elements as
finished
+
finishedMatrix.get(colIndex).set(rowIndex);
+
finishedMatrix.get(rowIndex).set(colIndex);
} else {
- contains = contains(tempRing,
poplygonList.get(j));
- }
+ boolean contains =
contains(potentialOuterRing,
+ innerPolygon);
+
+ 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);
- if (contains) {
- bitSet.set(j);
+ // 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);
}
}
if (log.isDebugEnabled()) {
+ long t2 = System.currentTimeMillis();
+ log.debug("createMatrix for", polygonList.size(),
"polygons took",
+ (t2 - t1), "ms");
+
log.debug("Containsmatrix");
for (BitSet b : containsMatrix) {
log.debug(b);
@@ -924,62 +978,6 @@
}
}
- /*
- * 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");
- // }
-
/**
* Checks if the ring with ringIndex1 contains the ring with ringIndex2.
*
@@ -994,7 +992,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) {
@@ -1004,6 +1002,7 @@
if (ring1.isClosed() == false) {
return false;
}
+
Polygon p = createPolygon(ring1.getPoints());
Coord p0 = ring2.getPoints().get(0);
@@ -1012,26 +1011,80 @@
// way2
return false;
}
+ // TODO check if p0 is on any of the lines of ring2
+
+ Iterator<Coord> it1 = ring1.getPoints().iterator();
+ Coord p1_1 = it1.next();
+ Coord p1_2 = null;
+
+ while (it1.hasNext()) {
+ p1_2 = p1_1;
+ p1_1 = it1.next();
+
+ if (ring2.linePossiblyIntersectsWay(p1_1, p1_2) ==
false) {
+ // don't check it - this segment of the outer
polygon
+ // definitely does not intersect the way
+ continue;
+ }
+
+ int lonMin = Math.min(p1_1.getLongitude(),
p1_2.getLongitude());
+ int lonMax = Math.max(p1_1.getLongitude(),
p1_2.getLongitude());
+ int latMin = Math.min(p1_1.getLatitude(),
p1_2.getLatitude());
+ int latMax = Math.max(p1_1.getLatitude(),
p1_2.getLatitude());
+
+ // check all lines of way1 and way2 for intersections
+ Iterator<Coord> it2 = ring2.getPoints().iterator();
+ Coord p2_1 = it2.next();
+ Coord p2_2 = null;
+
+ // for speedup we divide the area around the second
line into
+ // a 3x3 matrix with lon(-1,0,1) and lat(-1,0,1).
+ // -1 means below min lon/lat of bbox line p1_1-p1_2
+ // 0 means inside the bounding box of the line p1_1-p1_2
+ // 1 means above max lon/lat of bbox line p1_1-p1_2
+ int lonField = p2_1.getLongitude() < lonMin ? -1 : p2_1
+ .getLongitude() > lonMax ? 1 : 0;
+ int latField = p2_1.getLatitude() < latMin ? -1 : p2_1
+ .getLatitude() > latMax ? 1 : 0;
+
+ int prevLonField = lonField;
+ int prevLatField = latField;
+
+ while (it2.hasNext()) {
+ p2_2 = p2_1;
+ p2_1 = it2.next();
- // check all lines of way1 and way2 for intersections
- Iterator<Coord> it2 = ring2.getPoints().iterator();
- Coord p2_1 = it2.next();
- while (it2.hasNext()) {
- Coord p2_2 = p2_1;
- p2_1 = it2.next();
+ int changes = 0;
+ // check if the field of the 3x3 matrix has
changed
+ if ((lonField >= 0 && p1_1.getLongitude() <
lonMin)
+ || (lonField <= 0 &&
p1_1.getLongitude() > lonMax)) {
+ changes++;
+ lonField = p1_1.getLongitude() < lonMin
? -1 : p1_1
+ .getLongitude() >
lonMax ? 1 : 0;
+ }
+ if ((latField >= 0 && p1_1.getLatitude() <
latMin)
+ || (latField <= 0 &&
p1_1.getLatitude() > latMax)) {
+ changes++;
+ latField = p1_1.getLatitude() < latMin
? -1 : p1_1
+ .getLatitude() > latMax
? 1 : 0;
+ }
- Iterator<Coord> it1 = ring1.getPoints().iterator();
- Coord p1_1 = it1.next();
- while (it1.hasNext()) {
- Coord p1_2 = p1_1;
- p1_1 = it1.next();
+ // an intersection is possible if
+ // latField and lonField has changed
+ // or if we come from or go to the inner matrix
field
+ boolean intersectionPossible = (changes == 2)
+ || (latField == 0 && lonField
== 0)
+ || (prevLatField == 0 &&
prevLonField == 0);
- boolean intersects =
Line2D.linesIntersect(p1_1.getLongitude(),
- p1_1.getLatitude(),
p1_2.getLongitude(), p1_2
+ boolean intersects = intersectionPossible
+ &&
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)) {
@@ -1045,6 +1098,9 @@
return false;
}
}
+
+ prevLonField = lonField;
+ prevLatField = latField;
}
}
@@ -1079,19 +1135,80 @@
*/
private static class JoinedWay extends Way {
private final List<Way> originalWays;
- private boolean closedArtifical;
+ private boolean closedArtifical = false;
+
+ public int minLat;
+ public int maxLat;
+ public int minLon;
+ public int maxLon;
+ private Rectangle bounds = null;
public JoinedWay(Way originalWay) {
super(FakeIdGenerator.makeFakeId(), new
ArrayList<Coord>(
originalWay.getPoints()));
this.originalWays = new ArrayList<Way>();
addWay(originalWay);
+
+ // we have to initialize the min/max values
+ Coord c0 = originalWay.getPoints().get(0);
+ minLat = maxLat = c0.getLatitude();
+ minLon = maxLon = c0.getLongitude();
+
+ updateBounds(originalWay.getPoints());
}
public void addPoint(int index, Coord point) {
getPoints().add(index, point);
+ updateBounds(point);
+ }
+
+ public void addPoint(Coord point) {
+ super.addPoint(point);
+ updateBounds(point);
+ }
+
+ private void updateBounds(List<Coord> pointList) {
+ for (Coord c : pointList) {
+ updateBounds(c);
+ }
}
+ private void updateBounds(Coord point) {
+ if (point.getLatitude() < minLat) {
+ minLat = point.getLatitude();
+ bounds = null;
+ } else if (point.getLatitude() > maxLat) {
+ maxLat = point.getLatitude();
+ bounds = null;
+ }
+
+ if (point.getLongitude() < minLon) {
+ minLon = point.getLongitude();
+ bounds = null;
+ } else if (point.getLongitude() > maxLon) {
+ maxLon = point.getLongitude();
+ bounds = null;
+ }
+
+ }
+
+ public Rectangle getBounds() {
+ if (bounds == null) {
+ // note that we increase the rectangle by 1
because intersects
+ // checks
+ // only the interior
+ bounds = new Rectangle(minLat - 1, minLon - 1,
maxLat - minLat
+ + 2, maxLon - minLon + 2);
+ }
+
+ return bounds;
+ }
+
+ public boolean linePossiblyIntersectsWay(Coord p1, Coord p2) {
+ return getBounds().intersectsLine(p1.getLatitude(),
+ p1.getLongitude(), p2.getLatitude(),
p2.getLongitude());
+ }
+
public void addWay(Way way) {
if (way instanceof JoinedWay) {
for (Way w : ((JoinedWay)
way).getOriginalWays()) {
@@ -1145,6 +1262,7 @@
}
}
+ @Override
public String toString() {
StringBuilder sb = new StringBuilder(200);
sb.append(getId());
@@ -1180,4 +1298,5 @@
this.ring = ring;
}
}
+
}
_______________________________________________
mkgmap-dev mailing list
mkgmap-dev@lists.mkgmap.org.uk
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
