Uniform distance between points

How could I, having a path defined by several points that are not in a unifor开发者_如何学Cm distance from each other, redefine along the same path the same number of points but with a uniform distance. I'm trying to do this in Objective-C with NSArrays of CGPoints but so far I haven't had any luck with this. Thank you for any help.

EDIT

I was wondering if it would help to reduce the number of points, like when detecting if 3 points are collinear we could remove the middle one, but I'm not sure that would help.

EDIT

Illustrating: Reds are the original points, blues the post processed points:

The new path defined by the blue dots does not correspond to the original one.

---

I don't think you can do what you state that you want to do. But that could be a misunderstanding on my part. For example, I have understood from your comment that the path is straight between successive points, not curved.

Take, for example, a simple path of 3 points (0,1,2) and 2 line segments (0-1,1-2) of different lengths. Leave points 0 and 2 where they are and introduce a new point 1' which is equidistant from points 0 and 2. If point 1' is on one of the line segments 0-1, 1-2, then one of the line segments 0-1', 1'-2 is not coincident with 0-1, 1-2. (Easier to draw this, which I suggest you do.) If point 1' is not on either of the original line segments then the entire path is new, apart from its endpoints.

So, what relationship between the new path and the old path do you want ?

EDIT: more of an extended comment really, like my 'answer' but the comment box is too small.

I'm still not clear how you want to define the new path and what relationship it has to the old path. First you wanted to keep the same number of points, but in your edit you say that this is not necessary. You agree that replacing points by new points will shift the path. Do you want, perhaps, a new path from point 0 to point N-1, defined by N points uniformly spaced on a path which minimises the area between the old and new paths when drawn on the Cartesian plane ?

Or, perhaps you could first define a polynomial (or spline or other simple curve) path through the original points, then move the points to and fro along the curve until they are uniformly spaced ?

---

I think the problem is simple and easily solvable actually :)

The basic idea is:

• First check if the distance between your current point (P) and the end point of the line segment you are on is >= the distance between P and the next point (Q).

• If it is, great, we use some simple trigonometry to figure it out.

• Else, we move to the adjacent line segment (in your ordering) and deduct the distance between P and the endpoint of the line segment you are on and continue the process.

Pseudocode:

Defined previously

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: Find the next point along your path

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]

Entry point

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

---

My sense is that this is a very hard problem.

It basically amounts to a constrained optimization problem. The objective function measures how close the new line is from the old one. The constraints enforce that the new points are the same distance apart.

Finding a good objective function is the tricky bit, since it must be differentiable, and we don't know ahead of time on which segments each new point will lie: for instance, it's possible for two new points to lie on an extra-long old segment, and no new points lying on some extra-short old segment. If you somehow know a priori on which segments the new points will lie, you can sum the distances between points and their target segments and use that as your objective function (note that this distance function is nontrivial, since the segments are finite: it is composed of three pieces and its level-sets are "pill-shaped.")

Or you might forget about requiring the new points to lie on old segments, and just look for a new polyline that's "close" to the old one. For instance, you might try to write down an L2-like metric between polylines, and use that as your objective function. I don't expect this metric to be pleasant to write down, or differentiate.

---

I think a perturbative approach will work for this one.

I assume:

1. we know how to slide a point along the path and recalculate the distances (pretty trivial), and
2. the end points must remain fixed (otherwise the whole problem becomes trivial).

just iterate over the remaining (n-2) points: if point k is closer to point (k-1) than to point (k+1), move it a little forward along the path. Likewise if it's closer to point (k+1), move a little back along the path.

It's probably best to start with large step sizes (for speed) then make them smaller (for precision). Even if the points pass each other, I think this approach will sort them back into order.

---

This will use quite a bit of vector math but is quite simple really.

First you will need to find the total distance of the path. Depending on how the points of the path are stored is how you will do it. Here is a basic example on a 2 Dimensional Path in Pseudo-code.

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

The last step is what makes it unreasonable but this should work for you. There may be a small math error somewhere I double checked this several times but there could be something I missed. So if anyone notices something please inform me and I will edit it.

Hope this helps, Gale