n个最近邻居在3d空间中的knn实现 [英] knn implementation in 3d space for n closest neighbours

问题描述

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

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

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

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.

推荐答案

您可能要使用空间索引，例如

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.

其他(更简单)的空间索引是四叉树和 kD树.

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

这篇关于n个最近邻居在3d空间中的knn实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！