根据坐标对点进行排序

Question

在我的软件中，我得到存储在向量中的二维轮廓的点 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

所以让我们添加一些 typedef 来简化代码：

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 2

我提议（注意：未测试）

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

Answer 3

注意：我正在为 C++11 兼容编译器编写。所以 >> 对模板完全有效 ;)

第一

向量的向量是存储三维数据的一种非常低效的方式。您应该考虑使用

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

而不是

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

我使用 std::array 作为示例。如果您需要 std::vector 作为一个点，只需使用此类型而不是 std::array

第二

如果搜索最近点，则不需要计算平方根。比较平方距离就可以了。

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

第三

如果您从 'matrix' 中删除已用点，为什么要为 'closestpoint' 函数提供开始和结束迭代器？

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

找到它

根据坐标对点进行排序

Sorting points according to their coordinates

c++

2d

vector

contour