0

在我的代码中，我获得了存储在名为matrix. 这些点没有排序，所以我必须对它们进行排序。由于我不知道轮廓是否形成凸包，我必须修改 Graham 扫描。我决定使用以下程序。首先，我使用格雷厄姆扫描到凸包。我保存在一个新向量中的包。然后我从向量中删除凸包的点matrix。然后我必须只对新向量中的剩余点进行排序，为此我将使用距离和点积。

为此，我启动了 Graham 扫描程序。我把自己定位在这个链接上。

所以这是我到目前为止所拥有的：

int ccw(const std::array<double, 3>& s1, const std::array<double, 3>& s2,const std::array<double, 3>& origin)
{
  std::array<double, 3> v1, v2;
  int cp_z;

  v1[0] = (s1[0] - origin[0]); 
  v1[1] = (s1[1] - origin[1]);
  v2[0] = (s2[0] - origin[0]);
  v2[1] = (s2[1] - origin[1]);

  cp_z = v1[0] * v2[1] - v1[1] * v2[0];
  if(cp_z > 0)
       return CCW_LEFT_TURN;
  else if(cp_z < 0)
       return CCW_RIGHT_TURN;

  return CCW_COLINEAR;
}

bool compare_angle(const std::array<double, 3>& s1, const std::array<double, 3>& s2)
{
  int res;
  std::array<double, 3> p0;
  p0[0]=0;
  p0[1]=0;

  res = ccw(s1, s2, p0);

  if(res == CCW_LEFT_TURN)
       return true;
  else if(res == CCW_COLINEAR) {
       double da, db;
       da = Distance(p0, s1);
       db = Distance(p0, s2);
       if(da < db)
          return true;
  }

  return false;
}

void set_p0(std::vector<std::array<double, 3>> matrix)
{
  int i;
  for(i=1; i<matrix.size(); i++)
  {
    if(matrix[i][1] < matrix[0][1])
    {
        swap(matrix[0], matrix[1]);
    }
    else if(matrix[i][1] == matrix[0][1] && matrix[i][0] < matrix[0][0])
    {
        swap(matrix[0], matrix[i]);
    }
  }
}

void GrahamScan(std::vector<std::array<double, 3>> matrix, std::vector<std::array<double, 3>> chull)
{
  int i;
  bool done;
  std::array<double, 3> next2last, last;

  set_p0(matrix);

  sort(matrix.begin()+1, matrix.end(), compare_angle);

  chull.push_back(matrix[0]);
  chull.push_back(matrix[1]);

  for(i=2; i<matrix.size(); i++)
  {
    done = false;

    while(!done && chull.size() > 1) {
        last = chull.back();
        next2last = chull[chull.size()-2];

        if(ccw(last, matrix[i], next2last) != CCW_LEFT_TURN)
            chull.pop_back();
        else
            done = true;
    }

    chull.push_back(matrix[i]);
  }
}

void GeneratPath(const std::vector<std::vector<LineSegment>> &slicesWithLineSegments, const v3 &aabbSize, const double infill) {

  ofstream file ("data.csv");

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

  .
  .
  .

  if(matrix.size()>2)
    {
        GrahamScan(matrix, chull);
    }

 }

所以在函数中GeneratPath我想对点进行排序。为此，我将调用 GrahamScan 函数，它传递两个向量和 。matrix我首先使用 搜索具有最低 y 值的点。接下来我必须对点进行排序。因此我使用 C++ 提供的排序功能。作为参数，我使用函数。我找到的原始函数如下所示：chullGrahamScanset_p0compare_angle

struct point_angle_comp_p {
point_t p0;

point_angle_comp_p () : p0 (0, 0) { } 
point_angle_comp_p (const point_t &p) : p0 (p) { } 

bool operator() (const point_t &a, const point_t &b) 
{
    int res;

    res = ccw (a, b, p0);

    if (res == CCW_LEFT_TURN)
        return true;
    else if (res == CCW_COLINEAR) {
        double da, db;

        da = dist (p0, a);
        db = dist (p0, b);

        if (da < db)
            return true;
    }

    return false;
 }
};

由于我的模板中的函数是基于结构的，因此我不得不为我的目的重写该函数。但是，如果我现在发送程序，我会收到错误消息：表达式：向量迭代器 + 偏移超出范围。

我看不到我在哪里犯了错误，但不幸的是。有人可以在这里帮助我吗？

4

0 回答 0