Como reamose equidistante em uma linha (ou curva)?

Question

Eu tenho uma linha l_1 Dado com uma série de pontos p_1,...,p_n. Agora eu quero uma nova linha l_2 tendo k pontos: q_1,...,q_k. Mas para todos i \in {1,...,k-1}: abs( q_i - q_i+1 ) = const, significando os segmentos de l_2 são equidistantes ou uniformes.

• k >= 2
• e p_1 e p_n deve estar em l_2.
• abs( p_i - p_i+1 ) não const

Uma solução é aproximar uma linha com um spline e sub -amostrar novamente, ter segmentos de comprimento uniforme na época. Posso fazer melhor? Existe algum código C ++ para isso?

Ah, eu perdi um detalhe específico: aqueles q_i deve estar dentro l_1, o que significa que eles estão nos segmentos de linha de l_1 ou eles são pontos de amostra de l_1.

Answer 1

Usando uma função paramétrica

Você pode definir uma função paramétrica por partes:

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

Em seguida, selecione seus pontos q, idealmente espaçados menos que o mínimo p [i+1] -p [i

Finalmente, amostra F [q] em intervalos T iguais.

Resultado da amostra:

Aqui você pode ver o efeito de reduzir o tamanho do intervalo do maior para o menor da amostra original:

Você pode avaliar a bondade da aproximação, adicionando as áreas (integrando) entre as curvas originais e re-amostradas:

Se você plotar as integrais para diferentes tamanhos de intervalo, poderá decidir o que é uma boa amostragem:

Apenas para o registro, o código em 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]}];

Editar: Respondendo ao seu comentário

Comentado código PGM:

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*)

Answer 2

Depende dos seus pontos de linha - o que são? Se eles definirem uma linha suave, reamostrar uma spline cúbica é uma boa aposta.

Essencialmente, se você está tornando os pontos equidistantes, precisa definir o que deseja ver entre os pontos - a suavidade é mais importante do que permanecer fiel à linha original? Existe uma restrição de velocidade?

Tanto quanto posso ver, é provável que você acabará com um processo iterativo aqui, porque se seus pontos originais definirem uma linha suave, não é simples calcular nem mesmo o comprimento dessa linha, muito menos dividir isso em peças iguais e determine as coordenadas desses pontos.

Se você usar splines cúbicos, para cada spline, poderá calcular seu comprimento através da fórmula em Artigo de comprimento do arco da Wikipedia. No entanto, exige que você faça integração - quando você faz integração numérica, é conhecida como 'quadratura'. Para um cúbico (para calcular o comprimento de um segmento de linha entre dois pontos originais), isso deve acabar como uma soma ponderada dos coeficientes do spline cúbico - principalmente se você usar a quadratura gaussiana.

No entanto, você provavelmente pode obter uma resposta razoável usando polinômios cúbicos por partes (gerar um polinômio cúbico a partir de 2 pontos e os 2 pontos de ambos os lados) e um algoritmo iterativo que melhora os valores de adivinhação de Xi para dar pontos equidistantes. Mas isso supõe que você queira velocidade em vez da precisão.