Algorithme d'interpolation 2D

Question

J'ai deux formes qui sont des sections transversales d'un canal. Je veux calculer la section transversale d'un point intermédiaire entre les deux points définis. Quel est l'algorithme le plus simple (relativement simple ?) à utiliser dans cette situation ?

P.S. : Je suis tombé sur plusieurs algorithmes comme natural neighbor et poisson, qui me semblent complexes. Je suis à la recherche d'une solution simple, qui pourrait être mise en œuvre rapidement.

EDIT : J'ai enlevé le mot "Simplest" du titre car il peut être trompeur.

Answer 1

C'est simple :

1. Sur chaque section transversale, tracez N points à intervalles réguliers le long de la limite de la section transversale.
2. Tracez des lignes droites du n-ième point de la coupe transversale 1 au n-ième point de la coupe transversale 2.
3. Décollez votre nouvelle section à la distance souhaitée entre les anciennes sections.

Encore plus simple :

1. Utiliser une des sections transversales existantes sans modification.

Cette deuxième suggestion est peut-être trop simple, je suppose, mais je parie que personne n'en propose une plus simple !

EDIT suivant le commentaire de l'OP : (trop pour un re-commentaire)

Eh bien, vous avez demandé une méthode simple ! Je ne suis pas sûr de voir le même problème que vous avec la première méthode. Si les sections transversales ne sont pas trop bizarres (il vaut mieux qu'elles soient des polygones convexes) et que vous ne faites rien d'étrange, comme par exemple faire correspondre le côté gauche d'une section transversale avec le côté droit de l'autre (ce qui force beaucoup de lignes de croisement), alors la méthode devrait produire une sorte de section transversale raisonnable. Dans le cas que vous suggérez d'un triangle et d'un rectangle, supposons que le triangle est assis sur sa base, avec un sommet au sommet. Mettez ce point en correspondance avec, par exemple, le coin supérieur gauche du rectangle, puis continuez dans la même direction (dans le sens des aiguilles d'une montre ou dans le sens inverse) autour des limites des deux sections transversales en joignant les points correspondants. Je ne vois pas de lignes qui se croisent, et je vois une forme bien définie à n'importe quelle distance entre les deux sections transversales.

Answer 2

Notez qu'il y a quelques ambiguïtés sur les réponses de High Performance Mark que vous devrez probablement aborder et qui définiront la qualité du résultat de sa méthode. La plus importante est la suivante : lorsque vous dessinez les n points sur les deux coupes transversales, quelle sorte de correspondance déterminez-vous entre eux, c'est-à-dire si vous le faites de cette manière que High Performance Mark a suggéré, alors l'ordre d'étiquetage des points devient important.

Je suggère de faire tourner un plan (orthogonal) simultanément à travers les deux sections transversales, puis de faire correspondre l'ensemble des points qui coupent ce plan sur une section transversale avec l'ensemble des points qui coupent ce plan sur l'autre section transversale. Hypothétiquement, il n'y a pas de limite au nombre de points dans ces ensembles, mais cela réduit certainement la complexité du problème de correspondance dans la situation originale.

Answer 3

Voici une autre tentative de résolution du problème, qui me semble bien meilleure.

Étant donné les deux coupes transversales C_1 , C_2

Placez chaque C_i dans un cadre de référence global avec un système de coordonnées (x,y) de sorte que la façon dont ils sont relativement situés a un sens. Divisez chaque C_i en une courbe supérieure et une courbe inférieure U_i y L_i . L'idée est que vous voulez déformer continuellement la courbe U_1 a U_2 y L_1 a L_2 . (Notez que vous pouvez étendre cette méthode pour diviser chaque C_i en m courbes si vous le souhaitez).

La méthode à suivre est la suivante. Pour chaque T_i = U_i, or L_i échantillon n points, et déterminer le polynôme d'interpolation P{T_i}(x) . Comme on l'a dûment noté ci-dessous, les polynômes d'interpolation sont susceptibles d'osciller, surtout aux extrémités. Au lieu du polynôme d'interpolation, on peut utiliser le polynôme d'ajustement des moindres carrés qui serait beaucoup plus robuste. On définit alors la déformation du polynôme 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 comme 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 où la déformation Q est défini sur 0<=t<=1 donde t définit à quel point la déformation se situe (c'est-à-dire à t=0 nous sommes à U_2 et à t=1 nous sommes à U_1 et à tous les autres t nous sommes à une déformation continue des deux). Il en va exactement de même pour Q{P{L_1},P{L_2}}(x, t) . Ces deux déformations vous construisent une représentation continue entre les deux sections transversales que vous pouvez échantillonner à tout moment. t .

Notez que tout ce que cela fait réellement est une interpolation linéaire des coefficients des polynômes d'interpolation des deux morceaux des deux sections transversales. Notez également que lorsque vous divisez les sections transversales, vous devriez probablement imposer la contrainte qu'elles doivent être divisées à des points d'extrémité qui correspondent, sinon vous pouvez avoir des "trous" dans votre déformation.

J'espère que c'est clair.

edit : abordé la question de l'oscillation dans les polynômes d'interpolation.