knn implementation in 3d space for n closest neigh

Question

I am newbie to c. I have n structs holding the 4 members, 1st the unique index of and three floats representing special coordinates in 3D space. I need to find k nearest struct according to Euclidian distances.

//struct for input csv data
struct oxygen_coordinates
{
    unsigned int index; //index of an atom
    //x,y and z coordinates of atom 
    float x;
    float y;
    float z;
};

struct oxygen_coordinates atom_data[n];

//I need to write a function something like,

 knn(atom_data[i], atom_data, k); // This should return to 4 closest struct based on Euclidian distances. 
 //I have already written a function to get distances.

 //Distance function for two pints in a struct
 float getDistance(struct oxygen_coordinates a, struct oxygen_coordinates b)
 {
    float distance;
    distance = sqrt((a.x - b.x) * (a.x - b.x) + (a.y-b.y) *(a.y-b.y) + (a.z - b.z) * (a.z - b.z));
    return distance;
 }

At this point I am totally lost, any leads on algorithm will be really helpful. Particularly, in my data set there are only 3d coordinates therefore do I really need to classify points ? Thank you in advance.

Answer 1

Here is some code that might help you. This code is just to give an idea about the approach to the problem, as asked in the question.

// declare a global array that will hold the 4 nearest atom_data...
struct oxygen_coordinates nearestNeighbours[4];

// This function adds the structure passed to it until it becomes full, after that it replaces the structure added from the first...
    void addStructure(struct oxygen_coordinates possibleNeighbour) {
         static int counter = 0;
         int length = sizeof(nearestNeighbour)/sizeof(possibleNeighbour);
         if(length < 3) {
            nearestNeighbours[length] = possibleNeighbour;
         }
         else {
            nearestNeighbours[counter%4] = possibleNeighbour;
            counter++;
        }
    }

Given atom is the atom_data of the atom you want to find the neighbours of and atom data is the whole array. Now we make a new float variable which stores the min distance found so far, and initialize it with a very high value. After that we loop through the atom_data and if we find a candidate with distance less than the min value we have stored, we update the min value and add the structure to our nearestNeighbours array via the add method we created above. Once we loop through the entire structure, we will have the 4 nearest atom_data inside the nearestNeighbour array.

knn(given_atom, atom_data, k) {
        float minDistance = 10000; // Some large value...
        for(int i=0; i<n; i++) {
            int tempDistance = getDistance(given_atom, atom_data[i])
            if(tempDistance<minDistance) {
                addStructure(atom_data[i])
            }
        }
    }

The time complexity will depend on the length of the atom_data, i.e. n. If the array is stored in a sorted manner, this time complexity can be reduced significantly.

Answer 2

You may want to use a spatial index, such as the boost R-Tree. There are others, but this is the only one that comes with boost, as far as I am aware.

Other (much simpler) spatial indexes are quadtrees and kD-trees.