Hi Mark, Am 16.06.2009 um 09:18 schrieb Mark Burton:
At the distances we're (mostly) interested in, the curvature of the earth's surface has a tiny effect (much less than the effect of hills & valleys) so I guess (hope) that leaving out that factor is OK.
The curvature may have a tiny effect, but nonetheless you should consider the coordinate system you are using. Interpreting lat and lon as cartesian coordinates (don't know whether you are really doing that) will give large errors at high latitudes.
I know that this isn't your code but it's as good a place as any to comment about it: looking at the DP code (for the first time), I immediately see that the loop that finds the max distance is (potentially) doing many more sqrts and divisions than it needs to. So even if the code is correct, it could be somewhat faster which would be worthwhile given that it gets called for every line. Eg, it could be changed to look like this:
// Find point with highest distance. // Loop runs downwards, as the list length gets modified while running for(int i = endIndex-1; i > startIndex; i--) { Coord p = points.get(i); double ap = p.distance(a); double bp = p.distance(b); double abpa = (ab+ap+bp)/2; double dd = abpa * (abpa-ab) * (abpa-ap) * (abpa-bp); if (dd > maxDistance) { maxDistance = dd; maxIndex = i; } } maxDistance = 2 * Math.sqrt(maxDistance) / ab;
Also - you get a division by zero if ab is 0, perhaps adding a test for that before the loop would be advisable.
Do you understand that formula for the distance calculation? If so could you explain it for me? I don't get it.
Another minor nit - the comment is inaccurate as the list length doesn't change in this loop.
It is accurate, because the list length does get changed by the way the recursion works. It is not obvious, therefore this comment is really needed! Another question, just out of curiosity: Does it really mattern in Java how many sqrts or sin or cos I do? Doesn't that kind of difference get swamped by all that interpretation and memory allocation things etc. going on? With modern FPUs that kind of operation isn't that expensive (if it is done native). I would start working on the DP code if it makes sense. If somebody understands that distance formula and could explain it it would be very much appreciated. Otherwise I will have to make up my own formula (sigh...) Regards Thilo