0

私のコードでは、 というベクトルに格納された点の座標を取得しますmatrix。ポイントはソートされていないので、ソートする必要があります。輪郭が凸包を形成するかどうかわからないので、グラハム スキャンを修正する必要があります。次の手順を使用することにしました。最初に、凸包へのグラハム スキャンを検索するために使用します。凸包を新しいベクトルに保存します。次に、ベクトルから凸包のポイントを削除しmatrixます。次に、残りのポイントを新しいベクトルでのみ並べ替える必要があります。これには、距離と内積を使用します。

このために、Graham scan プログラムを開始しました。私はこのリンクに自分自身を向けました。

だからここに私が今まで持っているものがあります：

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でポイントを並べ替えたいと思います。matrixこのために、2 つのベクトルとを渡す GrahamScan 関数を呼び出しますchull。GrahamScanまず、 を使用して y 値が最も低い点を検索しset_p0ます。次に、ポイントを並べ替える必要があります。したがって、C++ が提供するソート関数を使用します。引数として、関数を使用しますcompare_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;
 }
};

テンプレートの関数が構造体ベースになったため、目的に合わせて関数を書き直す必要がありました。しかし、ここでプログラムを送信すると、次のエラー メッセージが表示されます。 Expression: vector iterator + offset out of range.

どこで間違えたのかわかりませんが、残念です。誰かがここで私を助けることができますか?

4

0 に答える 0