Perf improvement in LawOfCosines

[yozhao]

When I use LawOfCosines calacutator， I found the perf is worse than Haversine and Vincenty.

I found the heaviest part of LawOfCosines is acos

public static double distLawOfCosinesRAD(double lat1, double lon1, double lat2, double lon2) {
//TODO validate formula

//(MIGRATED FROM org.apache.lucene.spatial.geometry.LatLng.arcDistance()) (Lucene 3x)
// Imported from mq java client.  Variable references changed to match.

// Check for same position
if (lat1 == lat2 && lon1 == lon2)
  return 0.0;

// Get the m_dLongitude difference. Don't need to worry about
// crossing 180 since cos(x) = cos(-x)
double dLon = lon2 - lon1;

double a = DEG_90_AS_RADS - lat1;
double c = DEG_90_AS_RADS - lat2;
double cosB = (Math.cos(a) * Math.cos(c))
    + (Math.sin(a) * Math.sin(c) * Math.cos(dLon));

// Find angle subtended (with some bounds checking) in radians
if (cosB < -1.0)
  return Math.PI;
else if (cosB >= 1.0)
  return 0;
else
  return Math.acos(cosB);

}

In most scenarios, we use distLawOfCosinesRAD as a distance filter.

For within calculation, we don't need get the angle, we can just compare the cosine value of the angles, since cosine function is monotonic decreasing.

We can just compare whether cosB is bigger than cos(radius) while cos(radius) can be computed only once for a query.

Another improvement is, when I change

double a = DEG_90_AS_RADS - lat1;

double c = DEG_90_AS_RADS - lat2;

double cosB = (Math.cos(a) * Math.cos(c))

    + (Math.sin(a) * Math.sin(c) * Math.cos(dLon));

to

double cosB = (Math.sin(lat1) * Math.sin(lat2))

    + (Math.cos(lat1) * Math.cos(lat2) * Math.cos(dLon));

which is the same result, but the performance is much better if latitude and longitude is random distributed in China or US region.

I am wondering what is the purpose of DEG_90_AS_RADS convert here.

[dsmiley]

You are right regarding needless subtraction of DEG_90_AS_RADS. I have since committed the tweaks you have here.

You make a very good point about the Math.acos() call being redundant if the formula is being used to check if the distance is more than or less than another distance that is constant over many iterations (i.e. doing many point-in-circle tests). Addressing this is an API issue. The DistanceCalculator abstraction as it is currently formed isn't so great. Perhaps instead it should be named WithinDistanceCalculator and you initialize it with a point and distance. Not only would LawOfCosines benefit, but the others would too, I think. I'll create another issue.

[yozhao]

Happy to see your quick response. Thanks!