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' 不在任何一个原始线段上，那么整个路径都是新的，除了它的端点。

那么，你想要新路径和旧路径之间的关系是什么？

编辑：更多的是扩展评论，就像我的“答案”一样，但评论框太小了。

我仍然不清楚你想如何定义新路径以及它与旧路径有什么关系。首先，您想保持相同数量的点，但在您的编辑中您说这不是必需的。您同意用新点替换点将改变路径。您是否想要一条从点 0 到点 N-1 的新路径，由在笛卡尔平面上绘制时使新旧路径之间的区域最小化的路径上均匀分布的 N 个点定义？

或者，也许您可​​以首先定义一条穿过原始点的多项式（或样条曲线或其他简单曲线）路径，然后沿着曲线来回移动这些点，直到它们均匀分布？

于 2010-06-08T18:28:09.590 回答
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 回答
1

我的感觉是，这是一个非常困难的问题。

它基本上相当于一个有约束的优化问题。目标函数衡量新线与旧线的接近程度。约束强制新点之间的距离相同。

找到一个好的目标函数是一个棘手的问题，因为它必须是可微的，而且我们不知道每个新点将位于哪些段上：例如，两个新点可能位于超长旧段，并且在一些超短的旧段上没有新点。如果您以某种方式先验地知道新点将位于哪些段上，则可以将点与其目标段之间的距离相加并将其用作您的目标函数（请注意，此距离函数是非平凡的，因为这些段是有限的：它是由三块组成，其水平组呈“药丸状”。）

或者您可能忘记了要求新点位于旧线段上，而只是寻找与旧线段“接近”的新折线。例如，您可能会尝试在折线之间写下类似 L2 的度量，并将其用作您的目标函数。我不认为这个指标写下来或区分是令人愉快的。

于 2010-06-08T19:02:56.127 回答
0

这将使用相当多的向量数学，但实际上非常简单。

首先，您需要找到路径的总距离。根据路径点的存储方式，您将执行此操作。这是伪代码中二维路径的基本示例。

// 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 回答
0

我认为一种微扰方法将适用于此。

我假设：

  1. 我们知道如何沿着路径滑动一个点并重新计算距离（非常简单），并且
  2. 端点必须保持固定（否则整个问题变得微不足道）。

只需遍历剩余的 (n-2) 点：如果点 k 比点 (k+1) 更接近点 (k-1)，则沿路径向前移动一点。同样，如果它更接近点 (k+1)，则沿路径向后移动一点。

最好从大步长（为了速度）开始，然后让它们更小（为了精确）。即使这些点彼此通过，我认为这种方法会将它们重新排序。

于 2010-06-08T20:06:08.813 回答