Custom Latitude Longitude Index Interval using Binary Search

This week I was working on an interesting problem and found an interesting bug. The overall problem was to create a custom indexing scheme for latitude and longitude data by writing a function that accepts a lat-lon and returns a sector ID. As part of that problem I wanted to write a helper function that accepts a latitude (which ranges from -90.0 to +90.0) and returns which 0.1 degree interval the latitude falls in. Let me illustrate using a smaller fake example where “latitude” ranges from -1.0 to +10.0. For this example I want the following:

[-1.0 to -0.9) -> 0
[-0.9 to -0.8) -> 1
[-0.8 to -0.7) -> 2
. . .
[-0.1 to 0.0) -> 9
[ 0.0 to 0.1) -> 10
[ 0.1 to 0.2) -> 11
. . .
[ 0.9 to 1.0] -> 19

Notice that all but the last interval are open intervals, and the last is closed to capture the final 1.0 value. If an input is 0.245 then the output should be 12. I could do a sequential search but I wanted to use a binary search because I was going to call the function millions of times. My first attempt was this:

static int LatIndexOf(double latitude) // small experiment
{
// input is a fake latitude in [-1.0 +1.0]
// divide 0.1 degree intervals: [-1.0 -0.9) = 0, etc.

if (latitude == -1.0) return 0;
if (latitude == 1.0) return 19;

int lo = 0; //
int hi = 19;
int mid = (lo + hi) / 2;

bool found = false;
while (found == false)
{
double left = -1.0 + (0.1 * mid); // left part of interval
double right = left + 0.1; // right part of interval
if (latitude >= left && latitude < right)
return mid;
else if (latitude < left)
{
hi = mid – 1; mid = (lo + hi) / 2;
}
else
{
lo = mid + 1; mid = (lo + hi) / 2;
}
}
throw new Exception("LatIndexOf no value");
}

Because I was going to process hundreds of millions of real lat-lon data, I took the time to run pretty thorough tests on my function. As first written I ran into very nasty floating point errors that gave incorrect results for certain inputs. The hacky-fix was to round all floating point values:

static int LatIndexOf(double latitude)
{
latitude = Math.Round(latitude, 8); // round to 8 places
. . .

double left = -1.0 + (0.1 * mid);
left = Math.Round(left, 8);
. . .
double right = left + 0.1;
right = Math.Round(right, 8);
. . .

Moral: watch out for equality comparisons on floating point values.

Advertisements
This entry was posted in Software Test Automation. Bookmark the permalink.