4

互いに均一な距離にないいくつかのポイントで定義されたパスを使用して、同じパスに沿って同じ数のポイントを均一な距離で再定義するにはどうすればよいでしょうか。私はNSArrays of CGPoints を使用して Objective-C でこれを実行しようとしていますが、これまでのところうまくいきませんでした。助けてくれてありがとう。

編集

3 つのポイントが同一線上にあるかどうかを検出するときに中央のポイントを削除できるように、ポイントの数を減らすのに役立つかどうか疑問に思っていましたが、それが役立つかどうかはわかりません。

編集

説明: 赤は元のポイント、青は後処理されたポイントです。

代替テキスト

青い点で定義された新しいパスは、元のパスに対応していません。

4

5 に答える 5

3

やりたいと言ったことはできないと思います。しかし、それは私の誤解かもしれません。たとえば、あなたのコメントから、連続するポイント間のパスは曲線ではなく直線であることがわかりました。

たとえば、3 つの点 (0,1,2) と長さの異なる 2 つの線分 (0-1,1-2) の単純なパスを考えてみましょう。ポイント 0 と 2 をそのままにして、ポイント 0 と 2 から等距離にある新しいポイント 1' を導入します。ポイント 1' が線分 0-1、1-2 のいずれかにある場合、線分 0 のいずれか-1', 1'-2 は 0-1, 1-2 と一致しません。（これを描く方が簡単です。そうすることをお勧めします。）ポイント1'が元の線分のどちらにもない場合、終点を除いてパス全体が新しい.

では、新しいパスと古いパスの間にどのような関係が必要ですか?

編集：私の「答え」のように、実際には拡張されたコメントですが、コメントボックスが小さすぎます。

新しいパスをどのように定義したいのか、古いパスとどのような関係があるのか​​ 、まだ明確ではありません。最初は同じ数のポイントを保持したかったのですが、編集でこれは必要ないと言っています。ポイントを新しいポイントに置き換えると、パスがシフトすることに同意します。おそらく、デカルト平面に描画されたときに古いパスと新しいパスの間の領域を最小化するパス上に均一に配置された N 個のポイントによって定義される、ポイント 0 からポイント N-1 への新しいパスが必要ですか?

または、最初に元の点を通る多項式 (またはスプラインまたはその他の単純な曲線) パスを定義してから、点が均一な間隔になるまで曲線に沿って前後に移動できますか?

于 2010-06-08T18:28:09.590 に答える
1

私の感覚では、これは非常に難しい問題です。

これは基本的に、制約付き最適化の問題になります。目的関数は、新しい行が古い行からどれだけ近いかを測定します。制約により、新しいポイントは同じ距離だけ離れていることが強制されます。

微分可能でなければならず、それぞれの新しい点がどのセグメントにあるかを前もって知らないので、良い目的関数を見つけるのは難しいビットです。たとえば、2つの新しい点が非常に長い上にある可能性があります。古いセグメントであり、非常に短い古いセグメントに新しいポイントはありません。新しいポイントがどのセグメントにあるかを事前に知っている場合は、ポイントとそのターゲットセグメント間の距離を合計し、それを目的関数として使用できます（セグメントは有限であるため、この距離関数は重要です。 3つのピースで構成され、そのレベルセットは「ピル型」です。）

または、新しいポイントを古いセグメント上に配置する必要があることを忘れて、古いポリラインに「近い」新しいポリラインを探すこともできます。たとえば、ポリライン間のL2のようなメトリックを書き留めて、それを目的関数として使用しようとする場合があります。この指標を書き留めたり、区別したりするのが楽しいとは思いません。

于 2010-06-08T19:02:56.127 に答える
1

問題は単純で、実際には簡単に解決できると思います:)

基本的な考え方は次のとおりです。

  • まず、現在の点 (P) と現在の線分の終点の間の距離が、P と次の点 (Q) の間の距離 >= であるかどうかを確認します。

  • もしそうなら、それを理解するために簡単な三角法を使用します。

  • それ以外の場合は、(順序に従って) 隣接する線分に移動し、P と現在の線分の終点との間の距離を差し引いて、プロセスを続行します。

擬似コード:

以前に定義された

struct LineSegment
{
  Point start,end;
  int ID;
  double len; // len = EuclideanDistance(start,end);
  LineSegment *next_segment;
  double theta; // theta = atan2(slope_of_line_segment);
}

Function [LineSegment nextseg] = FindNextLineSegment(LineSegment lineseg)
Input: LineSegment object of the current line segment
Output: LineSegment object of the adjacent line segment in your ordering. 
nextseg.ID = -1 if there are no more segments

機能: パスに沿って次のポイントを見つける

Function [Point Q, LineSegment Z] = FindNextPt(Point P, LineSegment lineseg, int dist): 
Input: The current point P, the distance between this point and the next, and the LineSegment of the line segment which contains P.
Output: The next point Q, and the line segment it is on

Procedure:
distToEndpt = EuclideanDistance(P,lineseg->end);
if( distToEndpt >= d )
{
 Point Q(lineseg->start.x + dist*cos(lineseg.theta), lineseg->start.y + dist*sin(lineseg.theta));
 Z = lineseg;
}
else
{
 nextseg = lineseg->next_segment;
    if( nextseg.ID !=-1 )
    {
  [Q, Z] = FindNextPt(nextseg->start,nextseg->ID,dist-distToEndpt);
 }
    else
    {
  return [P,lineseg];
 }
}
 return [Q,Z]

エントリーポイント

Function main()
Output: vector of points
Procedure:

vector<LineSegment> line_segments;
// Define it somehow giving it all the properties
// ....

vector<Point> equidistant_points;
const int d = DIST;

[Q Z] = FindNextPoint(line_segments[0].start,line_segments[0],DIST);
while( Z.ID != -1 )
{
 equidistant_points.push_back(Q);
 [Q Z] = FindNextPt(Q,Z,d);
}
于 2010-06-08T18:50:29.870 に答える
0

これには摂動アプローチが有効だと思います。

私が想定し：

  1. パスに沿ってポイントをスライドさせ、距離を再計算する方法を知っています（非常に簡単です）。
  2. エンドポイントは固定されたままである必要があります（そうでない場合、問題全体が些細なものになります）。

残りの（n-2）ポイントを繰り返し処理します。ポイントkがポイント（k + 1）よりもポイント（k-1）に近い場合は、パスに沿って少し前方に移動します。同様に、ポイント（k + 1）に近い場合は、パスに沿って少し後ろに移動します。

ステップサイズを大きくして（速度を上げるため）、次に小さくする（精度を上げるため）のがおそらく最善です。ポイントがすれ違う場合でも、このアプローチで順番に並べ替えられると思います。

于 2010-06-08T20:06:08.813 に答える
0

これはかなりのベクトル演算を使用しますが、実際には非常に単純です。

まず、パスの合計距離を見つける必要があります。パスのポイントがどのように保存されているかによって、それを行う方法が異なります。疑似コードでの 2 次元パスの基本的な例を次に示します。

// This would generally be done with vectors, however I'm not sure
// if you would like to make your own class for them as I do so I will use arrays.

// The collection of points
int Points[4][2] = { {0,0}, {1,2}, {5,4}, {6,5} };
int Points2 = Points;

// goes to 3 because there are 4 points
for(int i=0; i<3; i++) {
     x = Points[i+1][0] - Points[i][0];
     y = Points[i+1][1] - Points[i][1];
     d += sqrt(( x * x ) + ( y * y ));
}

// divide distance by number of points to get uniform distance
dist = d/4;

// now that you have the new distance you must find the points
// on your path that are that far from your current point
// same deal here... goes to 3 because there are 4 points
for(int i=0; i<3; i++) {
     // slope
     m = ( Points[i+1][1] - Points[i][1] ) / ( Points[i+1][0] - Points[i][0] );
     // y intercept
     b = -(M * Points[i][0]) + Points[i][1];
     // processor heavy which makes this problem difficult
     // if some one knows a better way please say something
     // check every degree grabbing the points till one matches
     // if it doesn't then check next segment.
     for(float j=0; j<360; j += 0.1) {
          x = dist * sin(j);
          y = sqrt((dist * dist) - ( x * x ));
          if (y - (M * x + C)) {
               // then the point is on the line so set it
               Points2[i+1][0] = x;
               Points2[i+1][1] = y;
          }
     }
}

最後のステップはそれを不合理にするものですが、これはうまくいくはずです. これを数回再確認したところに小さな数学エラーがあるかもしれませんが、見落としがある可能性があります。誰かが何かに気づいたら、私に知らせてください、私はそれを編集します。

これが役に立てば幸いです、ゲイル

于 2010-06-08T18:48:30.407 に答える