Speed up suggestion for _geoToClosestFace by using LookUp table instead of 122 iteration for loop.

[SkybuckFlying]

I am worried about this internal function of UBER/H3 library, it may be too slow for my purposes: _geoToClosestFace

For a raytracer many Lat/Long points would have to be converted to H3Index using the latLngToCell which among others calls this seemingly slow function _geoToClosestFace. I am not yet sure if it's slow but it seems slow to me. This would mean it would do a loop of 122 items for each pixel + 122 branches for example pixels and some other stuff.

Since the lat/long is on the sphere anyway I propose a lookup table of 360 by 360 or even larger like 3600 by 3600 or even larger like 36000 by 36000 where the lat long is looked up. This would consume a lot of memory, like 1,2 gigabyte for the biggest option.
This could at least reduce the "search time" for the LatLong to closest Face.

So I propose a SetOption API routine for H3... where this option can be enabled. Then the H3 library allocates enough memory, possibly also returning false or true if the memory allocation succeeded. The level of accuracy could also be mentioned like:
LookUpAccuracyLevel1,LookUpAccuracyLevel2, LookUpAccuracyLevel3.

Then the user can try highest level accuracy first, if that fails, level2, if that fails level1. Or the library could also provide some routine to estimated which accuracy level is available knowing the ammount of free ram.

Once the option is set a branch is added to this function below which then uses the lookup table to quicken the search.

I will post both codes, the original code and then the modified/idea/pseudo code:

// ORIGINAL CODE:

void _geoToClosestFace(const LatLng *g, int *face, double *sqd) {
    Vec3d v3d;
    _geoToVec3d(g, &v3d);

    // determine the icosahedron face
    *face = 0;
    // The distance between two farthest points is 2.0, therefore the square of
    // the distance between two points should always be less or equal than 4.0 .
    *sqd = 5.0;

    // POSSIBLY PERFORMANCE PROBLEM ZONE:
    for (int f = 0; f < NUM_ICOSA_FACES; ++f) {
        double sqdT = _pointSquareDist(&faceCenterPoint[f], &v3d);
        if (sqdT < *sqd) {
            *face = f;
            *sqd = sqdT;
        }
    }
}

void _geoToClosestFace(const LatLng *g, int *face, double *sqd) {
    Vec3d v3d;
    _geoToVec3d(g, &v3d);

    // determine the icosahedron face
    *face = 0;
    // The distance between two farthest points is 2.0, therefore the square of
    // the distance between two points should always be less or equal than 4.0 .
    *sqd = 5.0;

    if (OptionFastClosestFaceLookUpEnabled == 1)
{
  if (ClosestFaceLookUpAccuracy == LookUpAccuracyLevel1) 
  {
     *face = ClosestFaceLookUpLevel1[ RoundTo360(Lat), RoundTo360(Long) ];
  } else
  if (ClosestFaceLookUpAccuracy == LookUpAccuracyLevel2) 
  {
     *face = ClosestFaceLookUpLevel2[ RoundTo3600(Lat), RoundTo3600(Long) ];
  } else 
   if (ClosestFaceLookUpAccuracy == LookUpAccuracyLevel3) 
  {
     *face = ClosestFaceLookUpLevel3[ RoundTo36000(Lat), RoundTo36000(Long) ];
  } 
}
else
{
    for (int f = 0; f < NUM_ICOSA_FACES; ++f) {
        double sqdT = _pointSquareDist(&faceCenterPoint[f], &v3d);
        if (sqdT < *sqd) {
            *face = f;
            *sqd = sqdT;
        }
    }
}
}

Pseudo code for SetOption API:

void SetOption( OptionName, OptionValue )
{
  if (OptionName == OptionClosestFaceLookUpEnabled)
  {
        CleanUpPreviousLevel1LookupTable;
        CleanUpPreviousLevel2LookupTable;
        CleanUpPreviousLevel3LookupTable;

     if (OptionName == ClosestFaceLookUpAccuracyLevel1)
     {
        AllocateLevel1LookupTable;     
    } else
     if (OptionName == ClosestFaceLookUpAccuracyLevel2)
     {
        AllocateLevel2LookupTable;     
    } else
     if (OptionName == ClosestFaceLookUpAccuracyLevel3)
     {
        AllocateLevel3LookupTable;     
    } else
}

I hope you want to experiment together with me to see if this idea will speedup the H3 Library at the expensive of more memory usage.

If interested this could be developed on a seperate branch and then made available to me as well so I can also test it.

And then maybe later it can be integrated into the main branch.

I write this idea to you so you can try and implement it, this would save me some time, eventually others can then also benefit from this ! ;)