点之间的均匀距离

Question

如果路径是由多个彼此距离不均匀的点定义的，那么我怎么能沿着同一条路径重新定义相同数量但距离均匀的点呢？我正在尝试在 Objective-C 中使用 CGPoint 的 NSArray 来完成此操作，但到目前为止我还没有遇到任何运气。 感谢您的帮助。

编辑

我想知道这是否有助于减少点数，例如当检测 3 个点是否共线时，我们可以删除中间的一个，但我不确定这会有所帮助。

编辑

插图： 红色是原始点，蓝色是后处理点：

蓝点定义的新路径与原始路径不对应。

Answer 1

我认为你不能做你所说的你想做的事。但这可能是我的误解。例如，我从您的评论中了解到，连续点之间的路径是笔直的，而不是弯曲的。

例如，一条由 3 个点 (0,1,2) 和 2 条不同长度的线段 (0-1,1-2) 组成的简单路径。将点 0 和 2 保留在原处，并引入一个新点 1'，该点与点 0 和 2 等距。如果点 1' 位于线段 0-1、1-2 之一上，则线段 0 之一上-1', 1'-2 与 0-1, 1-2 不一致。 （更容易绘制它，我建议您这样做。）如果点 1' 不在任何一条原始线段上，则除了端点之外，整个路径都是新的。

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

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

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

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

Answer 2

我认为这个问题很简单，实际上很容易解决:)

基本思想是：

• 首先检查当前点（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);
}

Answer 3

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

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

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

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

Answer 4

我认为扰动方法适用于此。

我假设：

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

只需迭代剩余的 (n-2) 个点：如果点 k 距离点 (k-1) 比点 (k+1) 更近，则将其沿路径向前移动一点。同样，如果它更接近点 (k+1)，则沿着路径向后移动一点。

最好从较大的步长开始（为了速度），然后减小步长（为了精度）。即使这些点相互交叉，我认为这种方法也会将它们重新排序。

Answer 5

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

首先，您需要找到路径的总距离。您将如何执行取决于路径点的存储方式。这是伪代码中的二维路径的基本示例。

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

最后一步是让它不合理的原因，但这应该对你有用。
某处可能存在一个小的数学错误，我多次检查了这一点，但可能有一些我错过的东西。因此，如果有人注意到某些内容，请通知我，我将对其进行编辑。

希望这有帮助，
大风