Как сделать эквидистантную повторную выборку линии (или кривой)? - PullRequest
Новая
       16

Как сделать эквидистантную повторную выборку линии (или кривой)?

8 голосов
/ 29 октября 2010

У меня есть линия l_1 с точечным рядом p_1,...,p_n. Теперь я хочу новую линию l_2, имеющую k точек: q_1,...,q_k. Но для всех i \in {1,...,k-1}: abs( q_i - q_i+1 ) = const, то есть сегменты l_2 равноудалены или однородны.

  • k >= 2
  • и p_1 и p_n должны быть в l_2.
  • abs( p_i - p_i+1 ) не постоянно

Одним из решений является аппроксимация линии сплайном, а затем повторная выборка, чтобы получить сегменты одинаковой длины. Могу ли я сделать лучше? Есть ли какой-нибудь код C ++ для этого?

Ах, я пропустил конкретную деталь: эти q_i должны быть в l_1, что означает, что они либо находятся на отрезках линии l_1, либо они являются точками выборки l_1.

Ответы [ 2 ]

7 голосов
/ 29 октября 2010

Использование параметрической функции

Вы можете определить кусочно-параметрическую функцию: 

 f[t_] := Piecewise[
      When x[i] <= t <= x[i + 1]

         f[t]= (y[i+1]-y[i]) (t - x[i]) / (x[i+1]-x[i]) + y[i], 

      For {i, 1 ... N};

Затем выберите ваши точки q, идеально расположенные на расстоянии меньше минимального p [i + 1] -p[i]

Наконец, выборка f [q] с равными t интервалами.

Результат выборки:

alt text

Здесь вы можете увидеть эффект уменьшения размера интервала от самого большого до самого маленького в исходном образце:

alt text

Вы можете оценить качество аппроксимации, суммируя области (интегрирование) между исходной и повторно выбранной кривыми:

alt text

Если вы построите графики интегралов для разных размеров интервалов, вы можете решить, что такое хорошая выборка:

alt text

Только для записи, код в Mathematica: 

a = 0;
p = Table[{   a = a + RandomReal[], RandomReal[]}, {10}];
f[t_, h_] := Piecewise[Table[{(h[[i + 1, 2]] - h[[i, 2]]) (t - h[[i, 1]]) /
                              (h[[i + 1, 1]] - h[[i, 1]]) + h[[i, 2]],
                       h[[i, 1]] <= t <= h[[i + 1, 1]]}, 
                       {i, 1, Length[h] - 1}]];

minSeg[h_] := Min[Table[Norm[h[[i, 1]] - h[[i + 1, 1]]], {i, Length[h] - 1}]];

newSegSize[h_] := (h[[Length@h, 1]] - h[[1, 1]])/
                  Ceiling[(h[[Length@h, 1]] - h[[1, 1]])/minSeg[h]]

qTable = Table[{t, f[t, p]}, {t, p[[1, 1]], p[[Length@p, 1]], newSegSize[p]}];

Редактировать: Отвечая на ваш комментарий

Комментируемый код ПГМ: 

a = 0; (* Accumulator to ensure an increasing X Value*)

p = Table[{a = a + RandomReal[], 
    RandomReal[]}, {10}]; (*Generates 10 {x,y} Rnd points with \
                            increasing x Value*)

f[t_, h_] :=  (* Def. a PWise funct:
                Example of resulting function:
                     f[t,{{1,2},{2,2},{3,4}}]
                Returns teh following function definition:

                    Value          for Range
                     2             1<=t<=2
                 2+2*(-2+t)        2<=t<=3
                     0             True
              *)
  Piecewise[
   Table[{(h[[i + 1, 2]] - 
           h[[i, 2]]) (t - h[[i, 1]])/(h[[i + 1, 1]] - h[[i, 1]]) + h[[i, 2]],
           h[[i, 1]] <= t <= h[[i + 1, 1]]},
           {i, 1, Length[h] - 1}]];

  minSeg[h_] := (* Just lookup the min input point separation*)
               Min[Table[Norm[h[[i, 1]] - h[[i + 1, 1]]], {i, Length[h] - 1}]];

  newSegSize[h_] := (* Determine the new segment size for having
                       the full interval length as a multiple of the
                       segment size *)
                   (h[[Length@h, 1]] - h[[1, 1]])/
                    Ceiling[(h[[Length@h, 1]] - h[[1, 1]])/minSeg[h]]

   qTable =     (*Generates a table of points using the PW function *)
         Table[
               {t, f[t, p]},
               {t, p[[1, 1]], p[[Length@p, 1]],newSegSize[p]}];

   ListLinePlot[{qTable, p}, PlotStyle -> {Red, Blue}] (*Plot*)
2 голосов
/ 29 октября 2010

Зависит от ваших точек - какие они?Если они определяют гладкую линию, то хорошая выборка - это повторная выборка кубического сплайна.

По сути, если вы делаете точки равноудаленными, вам нужно определить, что вы хотите видеть между точками - важнее ли гладкостьчем оставаться верным оригинальной линии?Есть ли ограничение по скорости?

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

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

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

...