Равномерное расстояние между точками

Question

Как я мог, имея путь, определенный несколькими точками, которые не находятся на одинаковом расстоянии друг от друга, переопределить вдоль того же пути то же количество точек, но с одинаковым расстоянием. Я пытаюсь сделать это в Objective-C с NSArray s CGPoint s, но пока мне не повезло с этим. Спасибо за любую помощь.

EDIT

Мне было интересно, поможет ли это уменьшить количество точек, например, при определении, коллинеарны ли 3 точки, мы могли бы удалить среднюю, но я не уверен, что это поможет.

EDIT

Иллюстрируя: Красные - это исходные очки, синие - после обработки очков:

альтернативный текст http://img139.imageshack.us/img139/3235/exampleg.jpg

Новый путь, определенный синими точками, не соответствует исходному.

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

Я чувствую, что это очень сложная проблема.

В основном это ограниченная проблема оптимизации. Целевая функция измеряет, насколько близка новая строка от старой. Ограничения обеспечивают, чтобы новые точки находились на одинаковом расстоянии друг от друга.

Найти хорошую целевую функцию довольно сложно, поскольку она должна быть дифференцируемой, и мы заранее не знаем, на каких сегментах будет лежать каждая новая точка: например, две новые точки могут лежать на очень длинный старый сегмент, и нет никаких новых точек, лежащих на каком-то очень коротком старом сегменте. Если вы как-то априори знаете, на каких сегментах будут лежать новые точки, вы можете суммировать расстояния между точками и их целевыми сегментами и использовать их в качестве целевой функции (обратите внимание, что эта функция расстояния нетривиальна, поскольку сегменты конечны: состоит из трех частей, а его наборы уровней имеют форму «таблетки».)

Или вы можете забыть о том, что новые точки должны лежать на старых сегментах, и просто искать новую ломаную линию, "близкую" к старой. Например, вы можете попытаться записать L2-подобную метрику между полилиниями и использовать ее в качестве целевой функции. Я не ожидаю, что этот показатель будет приятным для записи или дифференциации.

Answer 3

Я думаю, что проблема проста и легко решаема на самом деле:)

Основная идея такова:

• Сначала проверьте, если расстояние между вашей текущей точкой (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 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;
          }
     }
}

Последний шаг - это то, что делает его необоснованным, но это должно работать для вас.Где-то может быть небольшая математическая ошибка, которую я несколько раз проверил, но я мог кое-что пропустить.Поэтому, если кто-то что-то заметит, пожалуйста, сообщите мне, и я отредактирую это.

Надеюсь, это поможет, Гейл