Сортировка вектора координат C++

У меня есть график, в котором задан один узел, я должен сгенерировать упорядоченный вектор всех остальных узлов графа, упорядоченных ближайшим расстоянием.Сортировка вектора координат C++

Итак, у меня есть вектор со всеми координатами и отдельной координатой, чтобы сравнить его со всеми остальными. Моя идея - создать карту, которая будет сохранять для любого координатора (узла), вектор со всеми другими координатами, упорядоченными по ближайшей позиции.

Могу ли я сделать это с помощью std :: sort? Или любой способ упростить это?

Благодаря

источник

2014-02-16 Frion3L

Это не является полезным вопрос. Конечно, вы можете сортировать вектор, используя std :: sort, пока вы каким-то образом заполняете вектор, вы можете использовать std :: copy и объект функции (который вычисляет расстояние), а затем сортировать его. –

Проблема, с которой я сталкиваюсь, заключается в том, что я не знаю, как использовать std :: sort для сравнения всего вектора только с заданным элементом. Я даже не знаю, возможно ли это, или мне нужно найти другое решение. Мне просто нужно некоторое руководство – Frion3L

Могу ли я сделать это с помощью зЬй :: рода?

Я думаю, что вы идете в неправильном направлении. Если вы сохраняете вектор с координатами всех узлов и сортируете их на основе расстояния от текущего узла, он не обязательно будет сравнивать 2 координаты в заданном векторе! ,
Это требуется std::sort.
Чтобы преодолеть это, вам необходимо предварительно рассчитать расстояния всех узлов от данного узла, а затем определить свою функцию compare() для std::sort(), которая сравнивается на основе наименьшего расстояния.
Общая сфера сложности: O(N logN).

Или любой способ упростить это?

Вместо этого есть более простой способ.
Учитывая ваш узел, сделайте breadth first search используя очередь. При выполнении BFS вы 1-й посещаете ВСЕ узлы на расстоянии 1 от исходного узла, затем на расстоянии 2 и т. Д .... Это именно то, что требуется.
Общая сфера сложности: O(N).

Надеюсь, это поможет!

источник

2014-02-16 10:14:14

Проблема с BFS заключается в том, что я потерял связь между узлами. У меня просто есть координаты, между ними нет пути. – Frion3L

Тогда вам просто нужно создать график со всеми узлами, связанными друг с другом. Занимает пространство «O (N)». –

дайте мне знать, если у вас есть какие-либо сомнения. –

Если предположить, что у вас есть свой узел как глобальный вы можете сделать что-то вроде этого

#include <vector> 
#include <iostream> 
#include <utility> 

std::pair<float,float> MyNode(10,20); 

struct CalculateDistance{ 
    float operator()(std::pair<float,float> temp) { 
     //Use MyNode to calculate the distance between MyNode and temp and return it 
    } 
}; 

int main(){ 
    std::vector<std::pair<float,float> > listOfCoordinates; 

    listOfCoordinates.push_back(std::make_pair(10.20,30.2)); 
    listOfCoordinates.push_back(std::make_pair(9.20,31.2)); 
    listOfCoordinates.push_back(std::make_pair(12.20,39.2)); 
    listOfCoordinates.push_back(std::make_pair(15.20,-30.2)); 

    std::vector<float> distances; 

    std::copy(listOfCoordinates.begin(),listOfCoordinates.end(),distances.begin(),CalculateDistance()); 
    std::sort(distances.begin(),distances.end()); 
}

Но это только путь, вы должны размещать код или быть более точным, так кто-то может помочь вам. Я не делал фактических вычислений, CalculateDistance() должен возвращать поплавок, представляющий расстояние. Я не компилировал свой код, просто чтобы показать вам основную идею.

Если вы хотите сохранить отношения между узлами и расстояния, вы можете сделать что-то вроде:

typedef std::pair<float,float> Coordinate; 
typedef float Distance; 
typedef std::pair<Coordinate,Distance> Node;

и использовать вектор узла

источник

2014-02-16 10:25:40

Сортировка вектора координат C++

ответ

Смежные вопросы