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

问题描述

我是 c 的新手.我有 n 个结构体，其中包含 4 个成员，第一个是唯一索引，三个浮点数代表 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.

推荐答案

您可能想要使用空间索引，例如 boost R-Tree.还有其他的，但据我所知，这是唯一一个带有 boost 的.

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.

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