Algoritmo per l'interpolazione 2D

Question

Ho due forme che sono sezioni trasversali di un canale. Voglio calcolare la sezione trasversale di un punto intermedio tra i due punti definiti. Qual è l'algoritmo più semplice (relativamente semplice?) Da utilizzare in questa situazione?

P.S .: Ho trovato diversi algoritmi come il vicino naturale e il poisson, che sembravano complessi. Sto cercando una soluzione semplice, che potrebbe essere implementata rapidamente.

EDIT: ho tolto la parola "più semplice" dal titolo dal momento che potrebbe essere fuorviante

Answer 1

Questo è semplice:

1. Su ogni sezione trasversale disegnare N punti a intervalli regolari lungo il confine di la sezione trasversale.
2. Traccia le linee rette dal n-esimo punto sulla sezione trasversale 1 al n ° punto sulla sezione 2.
3. Togliere la nuova sezione alla distanza desiderata tra le vecchie sezioni trasversali.

ancora più semplice:

1. Utilizzare una delle sezioni esistenti senza modifiche.

Questo secondo suggerimento potrebbe essere troppo semplice, suppongo, ma scommetto che nessuno ne suggerisce uno più semplice!

EDIT seguente commento di OP: (troppo per una ri-commento)

Beh, hai chiesto per un metodo semplice! Non sono sicuro di vedere lo stesso problema con il primo metodo come fai tu. Se le sezioni trasversali non sono troppo strane (probabilmente meglio se sono poligoni convessi) e non fai nulla di strano come mappare il lato sinistro di una sezione trasversale sul lato destro dell'altro (forzando così molte linee di incrocio) quindi il metodo dovrebbe produrre una sorta di sezione trasversale sensibile. Nel caso tu suggerisca un triangolo e un rettangolo, supponi che il triangolo sia seduto sulla sua base, un vertice in alto. Mappare quel punto verso, ad esempio, l'angolo in alto a sinistra del rettangolo, quindi procedere nella stessa direzione (in senso orario o antiorario) attorno ai limiti di entrambe le sezioni che uniscono i punti corrispondenti. Non vedo linee di attraversamento e vedo una forma ben definita a qualsiasi distanza tra le due sezioni.

Answer 2

Nota ci sono alcune ambiguità sulle risposte di High Performance Mark che probabilmente dovrai affrontare e definiremo la qualità dell'output del suo metodo. Il più importante è che, quando si disegnano i punti n su entrambe le sezioni trasversali, quale tipo di corrispondenza si determina tra di loro, ovvero se lo si fa in quel modo suggerito High Performance Mark, allora l'ordine di etichettatura dei punti diventa importante .

Suggerisco di ruotare il piano (ortogonale) simultaneamente attraverso entrambe le sezioni trasversali, quindi l'insieme di punti che intersecano quel piano su una sezione trasversale deve solo essere abbinato all'insieme di punti che intersecano quel piano sull'altra sezione trasversale. Ipoteticamente, non c'è limite al numero di punti in questi set, ma certamente riduce la complessità del problema di corrispondenza nella situazione originale.

Answer 3

Ecco un'altra prova del problema, che ritengo sia un tentativo molto migliore.

Date le due sezioni C_1, C_2

Posizionare ogni C_i in un sistema di riferimento globale con sistema (x,y) coordinate in modo che il modo in cui sono situati relativamente senso. Dividere ogni C_i in una curva superiore e inferiore U_i e L_i. L'idea è che vorrete deformare continuamente la curva U_1 a U_2 e L_1 a L_2. (Nota è possibile estendere questo metodo per dividere ogni C_i in curve m se lo si desidera.)

Il modo per farlo è il seguente. Per ogni campione campione n e determinare il polinomio interpolatore P{T_i}(x). Come indicato di seguito, i polinomi interpolanti sono suscettibili di oscillazione, specialmente sui punti finali. Invece del polinomio interpolatore, si può invece usare il polinomio di minimi quadrati che sarebbe molto più robusto. Per indicare la deformazione del polinomio P{U_1}(x) = a_0 + a_1 * x + ... + a_n * x^n a P{U_2}(x) = b_0 + b_1 * x + ... + b_n * x^n come Q{P{U_1},P{U_2}}(x, t) = (t * a_0 + (1 - t) b_0) + ... + (t * a_n + (1-t) * b_n) * x^n dove la deformazione Q è definita su 0<=t<=1 dove t definisce in quale punto la deformazione è a (cioè a t=0 siamo a U_2 ea t=1 siamo a U_1 e ad ogni altro t siamo a una deformazione continua dei due.) Lo stesso identico segue per Q{P{L_1},P{L_2}}(x, t). Queste due deformazioni ti costruiscono una rappresentazione continua tra le due sezioni trasversali che puoi campionare in qualsiasi t.

Nota tutto ciò che si sta facendo è linearmente l'interpolazione dei coefficienti dei polinomi di interpolazione dei due pezzi di entrambe le sezioni. Nota anche quando dividi le sezioni trasversali dovresti probabilmente mettere il vincolo che devono essere divisi ai punti finali che corrispondono, altrimenti potresti avere dei "buchi" nella tua deformazione.

Spero sia chiaro.

modifica: ha affrontato il problema dell'oscillazione nei polinomi interpolanti.