реализация knn в трехмерном пространстве для n ближайших соседей - PullRequest
Новая
       13

реализация knn в трехмерном пространстве для n ближайших соседей

0 голосов
/ 15 апреля 2019

Я новичок в с.У меня есть n структур, содержащих 4 члена, 1-й уникальный индекс и три числа с плавающей точкой, представляющие особые координаты в трехмерном пространстве.Мне нужно найти 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;
 }

На данный момент я полностью потерян, любойведет по алгоритму будет действительно полезным.В частности, в моем наборе данных есть только трехмерные координаты, поэтому мне действительно нужно классифицировать точки?Заранее спасибо.

Ответы [ 2 ]

0 голосов
/ 17 апреля 2019

Возможно, вы захотите использовать пространственный индекс, например, boost R-Tree . Есть и другие, но, насколько я знаю, это единственное, что идет с повышением.

Другими (намного более простыми) пространственными индексами являются квадродерево и кД-деревья .

0 голосов
/ 15 апреля 2019

Вот код, который может вам помочь. Этот код просто для того, чтобы дать представление о подходе к проблеме, как задано в вопросе. 

// 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_data атома, для которого вы хотите найти соседей, а данные атома - весь массив. Теперь мы создаем новую переменную с плавающей точкой, которая хранит найденное минимальное расстояние, и инициализируем ее очень высоким значением. После этого мы перебираем atom_data и, если мы находим кандидата с расстоянием, меньшим, чем значение min, которое мы сохранили, мы обновляем значение min и добавляем структуру в наш массив nearNeighbours с помощью метода add, который мы создали выше. Как только мы пройдемся по всей структуре, у нас будет 4 ближайших atom_data внутри массива nearNeighbour. 

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. Если массив хранится отсортированным образом, эта временная сложность может быть значительно уменьшена.

...