Точки сортировки в соответствии с их координатами

Question

В моем программном обеспечении я получаю точки 2D-контура, хранящиеся в векторе matrix Моя задача теперь состоит в том, чтобы отсортировать эти точки, чтобы получить контур. Сначала я попробовал функцию atan2, ведьма работала хорошо для обычных случаев. Но в случае для невыпуклого контура это не работает. Итак, после поиска в google и после некоторых ответов здесь я попытаюсь рассчитать ближайшие точки. Таким образом, у меня есть функция, которая вычисляет расстояние между двумя точками.

double distancepoints(vector<double> const& s1, vector<double> const& s2) 
{ 
    return sqrt((s1[0] - s2[0])*(s1[0] - s2[0]) + (s1[1] - s2[1])*(s1[1] - s2[1])); 
} 

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

int closestpoint(vector<double> const& p, begin, end) 
{ 
    double d=0; 
    result = begin; 
    while(begin != end) 
    { 
     double d2 = distancepoints(p, begin); 
     if(d2 < d) 
     { 
     d = d2; 
     result = begin; 
     } 
    } 
    return result; 
} 

Здесь я не знаю, как передать начало и конец вектора.

Если у меня есть указатель на следующую точку, я бы сохранил эту точку в векторе Hull и удалил ее из вектора matrix. Это должно произойти до тех пор, пока matrix не будет полностью стерта.

vector<vector<double> > matrix; 
vector<vector<double> > hull; 

int columns = 3; 

const std::vector<LineSegment> &lss = slicesWithLineSegments[i]; 
rows = 2*lss.size(); 

matrix.resize(rows); 

for(size_t i=0; i<matrix.size(); i++) { 
    matrix[i].resize(columns); 
} 

for(size_t i=0; i<hull.size(); i++) { 
    hull[i].resize(columns); 
} 

vector<vector<double> > startpoint; 

for(size_t i=0; i<startpoint.size(); i++) { 
    startpoint[i].resize(columns); 
} 

startpoint[0][0]=matrix[0][0]; 
startpoint[0][1]=matrix[0][1]; 
startpoint[0][2]=matrix[0][2]; 

matrix.erase(matrix.begin()); 

while (matrix.size()) 
{ 
// Find next point (the one closest to p) and return index 
int it = closestpoint(startpoint, matrix.begin(), matrix.end()); 

// Store nearest point 
hull.push_back(std::vector<double>(3, 0)); 
r = hull.size()-1; 
hull[r][0] = matrix[it][0]; 
hull[r][1] = matrix[it][1]; 
hull[r][2] = matrix[it][2]; 
// Our new p is the point we just found 
startpoint = matrix[it]; 
// Remove the point we just found from the vector of points 
matrix.erase(matrix[it]); 
} 

Но почему-то мне удается не просто запрограммировать функцию. Может, у кого-то есть идея, что я делаю неправильно?

Answer 1

Примечание: Я пишу для компилятора, совместимого с C++ 11. Так >> совершенно справедливо для шаблонов;)

Первый

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

std::vector<std::array<double, 3>> 

вместо

std::vector<std::vector<double>> 

Я использую зЬй :: массив для примеров. Если вам нужен зЬй :: вектор для одной точки просто использовать этот тип вместо станда :: массив

Второго

Вам не нужно вычислить квадратный корень, если вы ищете для nearst точки. Сравнение квадратного расстояния будет работать.

double squareDistancePoints(const std::array<double, 3>& a, const std::array<double, 3>& b) 
{ 
    return pow(a[0]-b[0], 2) + pow(a[1]-b[1], 2) + pow(a[2]-b[2], 2); 
} 

Для векторных точек это было бы

double squareDistancePoints(const std::vector<double>& a, const std::vector<double>& b) 
{ 
    assert(a.size() == b.size()); 
    double sum = 0; 
    for(size_t i = 0; i < a.size(); ++i) 
     sum += pow(a[i]-b[i], 2); 
    return sum; 
} 

Третий

Если удалить используемые пункты из вашей «матрицы», почему вы поставить в начало и конец итераторы к вашему " ближайшая точка "?

std::vector<std::array<double, 3>>::const_iterator closestPoint(const std::array<double, 3>& point, const std::vector<std::array<double, 3>>& matrix) 
{ 
    return std::min_element(matrix.begin(), matrix.end(), [=](const auto& a, const auto& b) { 
     return squareDistancePoints(point, a) < squareDistancePoints(point, b); 
    }); 
} 

Для этого вам не нужна функция closestPoint(). Вам нужна std :: min_element из стандартной библиотеки. Это немного медленнее, потому что расстояние для лучшей точки вычисляется несколько раз, но если ваш sqrt() был достаточно быстр, этот код также будет достаточно быстрым.

Более быстрый, но более длинная версия здесь:

std::vector<std::array<double, 3>>::const_iterator closestPoint(const std::array<double, 3>& point, const std::vector<std::array<double, 3>>& matrix) 
{ 
    double bestDistance = DBL_MAX; 
    auto bestIt = matrix.end(); 

    for(auto it = matrix.begin(); it != matrix.end(); ++it) 
    { 
     const auto distance = squareDistancePoints(point, *it); 
     if (distance < bestDistance) 
     { 
      bestDistance = distance; 
      bestIt = it; 
     } 
    } 

    return bestIt; 
} 

Пример

std::vector<std::array<double, 3>> matrix; 
std::vector<std::array<double, 3>> hull; 

... // populate matrix 

// Add first point to hull 
hull.push_back(matrix.back()); 
matrix.pop_back(); 

// Add additional points to hull 
while(!matrix.empty()) 
{ 
    auto it = closestPoint(hull.back(), matrix); 
    hull.push_back(*it); 
    matrix.erase(it); 
} 

Инлайн Пример без использования функции closestPoint(), поскольку это бы требуют closestPoint (), которая принимает начало и конец итератора.

std::vector<std::array<double, 3>> points; 

... // populate points with matrix data 

for(auto it = points.begin(); it != points.end(); ++it) 
{ 
    auto bestIt = points.end(); 
    double bestSquareDistance = DBL_MAX; 
    for(auto nextIt = it + 1; nextIt != points.end(); ++nextIt) 
    { 
     const auto squareDistance = squareDistancePoints(*it, *nextIt); 
     if (squareDistance < bestSquareDistance) 
     { 
      bestSquareDistance = squareDistance; 
      bestIt = nextIt; 
     } 
    } 
    if (bestIt != points.end()) 
     std::swap(*(it+1), *bestIt); 
} 

Короткие Инлайн Пример (короткий, но очень неэффективно; Используется при небольших наборов точек)

std::vector<std::array<double, 3>> points; 

... // populate points with matrix data 

for(auto it = points.begin(); it != points.end() && it+1 != points.end(); ++it) 
    std::sort(it+1, points.end(), [=](const auto& a, const auto& b) { 
     return squareDistancePoints(*it, a) < squareDistancePoints(*it, b); 
    }); 

// vector 'points' now contains all hull points in correct order 

Полный пример я создал небольшой пример программы, которая сортирует точки 2D-прямоугольник. Вы можете найти его на http://ideone.com/OeCpdG

Answer 2

Итак, давайте добавим несколько определений типов для упрощения кода:

typedef std::vector<double> Point; // I still think std::array<double,3> 
            // would be better here. 
typedef std::vector<Point> PointList; 

size_t closestpoint(const Point& p, const PointList& plist) 
{ 
    if (plist.empty()) 
    { 
     throw ???; // Call is meaningless if plist is empty. 
    } 
    size_t result = 0; 
    double best = distancepoints(p, plist[result]); 
    for (size_t i = 1; i < plist.size(); i++) 
    { 
     const double dist = distancepoints(p, plist[i]); 
     if (dist < best) 
     { 
      result = i; 
      best = dist; 
     } 
    } 
    return result; 
} 

Вызов является:

size_t it = closestpoint(startpoint, matrix); 

Answer 3

Я предлагаю (осторожно: не тестировалось)

int closestpoint (std::vector<std::vector<double> > const & p, 
        std::vector<std::vector<double> >::const_iterator & it, 
        std::vector<std::vector<double> >::const_iterator & end) 
{ 
    double d=DBL_MAX; 
    int result=0; 
    for (int i = 0 ; it != end ; ++it, ++i) 
    { 
     double d2 = distancepoints(p, *it); 
     if(d2 < d) 
     { 
     d  = d2; 
     result = i; 
     } 
    } 
    return result; 
}