c - n个最近邻居在3d空间中的knn实现

我是c的新手。我有n个结构，其中包含4个成员，第1个是唯一索引，三个浮点数表示3D空间中的特殊坐标。我需要根据欧几里得距离找到k最近的结构。

//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];

//我需要编写类似的函数，

 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;
 }

在这一点上我完全迷失了，算法上的任何线索都将真正有用。特别是，在我的数据集中只有3d坐标，因此我真的需要对点进行分类吗？先感谢您。

最佳答案

这是一些可能对您有帮助的代码。这段代码只是为了给出解决问题的方法的想法，正如问题所要求的那样。

// 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++;
        }
    }

给定的atom是您要查找其邻居的atom的atom_data，atom数据是整个数组。
现在，我们创建一个新的float变量，该变量存储到目前为止找到的最小距离，并使用很高的值对其进行初始化。
之后，我们遍历atomic_data，如果找到距离小于我们存储的最小值的候选对象，我们将更新最小值，并通过上面创建的add方法将结构添加到我们的NearestNeighbours数组中。
一旦遍历整个结构，我们将在NearestNeighbour数组中拥有4个最近的atom_data。

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])
            }
        }
    }

时间复杂度将取决于atomic_data的长度，即n。如果以排序的方式存储数组，则此时间复杂度可以大大降低。

关于c - n个最近邻居在3d空间中的knn实现，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55695927/