Added distanceInDegreesSquared() to be used where relative distances
are required (i.e. finding closest city).
Now quickDistance() just calls distanceInDegreesSquared() and applies
the sqrt and scaling.
Still using quickDistance() instead of slowDistance() for all other
distance calculations.
Folks,
OK, so the parallelisation code has not been very successful so far but
we can still speed up mkgmap.
You have probably noticed that it spends a huge proportion of its time
in Math.acos() which is being called from Coord.distance().
The attached patch renames distance() to slowDistance() and introduces
a new quickDistance() function that is based on the code that was in
the MultipolygonRelation class. I have tested quickDistance() against
slowDistance() and for maps in the UK and Germany it produces distances
that are very similar (within 0.5% or better).
It is substantially faster and so I believe we should change to using
it as long as it doesn't introduce any issues.
So please try out this patch and report:
a - if any breakage is observed
b - performance increase/decrease
Cheers,
Mark
diff --git a/src/uk/me/parabola/imgfmt/Utils.java b/src/uk/me/parabola/imgfmt/Utils.java
index 97e0887..8e69270 100644
--- a/src/uk/me/parabola/imgfmt/Utils.java
+++ b/src/uk/me/parabola/imgfmt/Utils.java
@@ -165,14 +165,14 @@ public class Utils {
* Convert an angle in map units to degrees.
*/
public static double toDegrees(int val) {
- return (double) val / ((1 << 24) / 360.0);
+ return (double) val * (360.0 / (1 << 24));
}
/**
* Convert an angle in map units to radians.
*/
public static double toRadians(int mapunits) {
- return toDegrees(mapunits) * Math.PI / 180;
+ return toDegrees(mapunits) * (Math.PI / 180);
}
public static void closeFile(Closeable f) {
diff --git a/src/uk/me/parabola/imgfmt/app/Coord.java b/src/uk/me/parabola/imgfmt/app/Coord.java
index 240c225..54cdc5f 100644
--- a/src/uk/me/parabola/imgfmt/app/Coord.java
+++ b/src/uk/me/parabola/imgfmt/app/Coord.java
@@ -95,6 +95,10 @@ public class Coord implements Comparable {
* Distance to other point in meters.
*/
public double distance(Coord other) {
+ return quickDistance(other);
+ }
+
+ public double slowDistance(Coord other) {
if (equals(other))
return 0;
@@ -112,6 +116,49 @@ public class Coord implements Comparable {
return Math.acos(cangle) * R;
}
+ public double quickDistance(Coord other){
+ double qd = 40075000 * Math.sqrt(distanceInDegreesSquared(other)) / 360;
+ final boolean testing = false;
+ if(testing) {
+ double sd = slowDistance(other);
+ double delta = Math.abs(qd - sd);
+ if(delta > sd / 500)
+System.err.println("quickDistance() = " + qd + " slowDistance() = " + sd + " (" + (100 * delta / sd) + "% difference)");
+ }
+ return qd;
+ }
+
+ public double distanceInDegreesSquared(Coord other) {
+ if (equals(other))
+ return 0;
+
+ double lat1 = Utils.toDegrees(getLatitude());
+ double lat2 = Utils.toDegrees(other.getLatitude());
+ double long1 = Utils.toDegrees(getLongitude());
+ double long2 = Utils.toDegrees(other.getLongitude());
+
+ double latDiff;
+ if (lat1 < lat2)
+ latDiff = lat2 - lat1;
+ else
+ latDiff = lat1 - lat2;
+ if (latDiff > 90)
+ latDiff -= 180;
+
+ double longDiff;
+ if (long1 < long2)
+ longDiff = long2 - long1;
+ else
+ longDiff = long1 - long2;
+ if (longDiff > 180)
+ longDiff -= 360;
+
+ // scale longDiff by cosine of average latitude
+ longDiff *= Math.cos(Math.PI / 180 * Math.abs((lat1 + lat2) / 2));
+
+ return (latDiff * latDiff) + (longDiff * longDiff);
+ }
+
public Coord makeBetweenPoint(Coord other, double fraction) {
return new Coord((int)(latitude + (other.latitude - latitude) * fraction),
(int)(longitude + (other.longitude - longitude) * fraction));
diff --git a/src/uk/me/parabola/mkgmap/general/MapPointFastFindMap.java b/src/uk/me/parabola/mkgmap/general/MapPointFastFindMap.java
index 3a36b97..1f33a99 100644
--- a/src/uk/me/parabola/mkgmap/general/MapPointFastFindMap.java
+++ b/src/uk/me/parabola/mkgmap/general/MapPointFastFindMap.java
@@ -146,7 +146,7 @@ public class MapPointFastFindMap{
for (MapPoint actPoint: list)
{
-double distance = actPoint.getLocation().distance(p.getLocation());
+double distance = actPoint.getLocation().distanceInDegreesSquared(p.getLocation());
if(distance < minDist)
{
diff --git a/src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java b/src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
index 0abde51..ebcc500 100644
--- a/src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
+++ b/src/uk/me/parabola/mkgmap/reader/osm/MultiPolygonRelation.java
@@ -96,7 +96,7 @@ public class MultiPolygonRelation extends Relation {
for (Coord c1: l1){
for(Coord c2: l2){
-double newDistance = distance(c1, c2);
+double newDistance = c1.distanceInDegreesSquar
