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

Question

我是c的新手。我有 n 个结构体，其中包含 4 个成员，第一个是唯一索引，三个 float 表示 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 坐标，因此我真的需要对点进行分类吗？先感谢您。

Answer 1

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

// 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 data是整个数组。现在我们创建一个新的浮点变量来存储迄今为止找到的最小距离，并用一个非常高的值对其进行初始化。之后，我们循环遍历atom_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])
            }
        }
    }

时间复杂度取决于atom_data的长度，即n。如果数组按照排序的方式存储，这个时间复杂度可以显着降低。