Comment mapper un point sur une grille déformée

Question

Disons que vous avez une collection de points avec des coordonnées sur un système de coordonnées cartésiennes.

Vous souhaitez tracer un autre point et connaissez ses coordonnées dans le même système de coordonnées cartésiennes.

Cependant, le tracé sur lequel vous dessinez est déformé par rapport à l'original. Imaginez que vous preniez l'avion d'origine, l'imprimiez sur une feuille de caoutchouc, que vous l'étiriez à certains endroits et que vous le pinciez à d'autres endroits, de manière asymétrique (sans chevauchement ni complexe).

( source )

Vous connaissez les coordonnées étirées et non étirées de chacun de vos ensembles de points, mais pas la fonction d'étirement sous-jacente. Vous connaissez les coordonnées non étirées d'un nouveau point.

Comment pouvez-vous estimer où tracer le nouveau point dans les coordonnées étirées en fonction des positions étirées des points proches? Cela n’a pas besoin d’être exact, car vous ne pouvez pas déterminer la fonction d’étirement réelle à partir d’un ensemble de points remappés, à moins d’avoir plus d’informations.

autres mots-clés possibles: coordonnée du plan du maillage de la grille déformée déformée

Answer 1

D'accord, cela ressemble à une déformation d'image. Voici ce que vous devriez faire:

1. Créez une triangulation de Delaunay de votre grille non distancée et utilisez vos connaissances du correspondances entre la grille déformée et non quadrillée pour créer la triangulation de la grille déformée. Vous connaissez maintenant les triangles correspondants dans chaque image et, en l’absence de chevauchement, vous devriez pouvoir effectuer l’étape suivante sans trop de difficulté.

2. Maintenant, pour trouver le point correspondant A , dans l'image déformée:

   1. Recherchez le triangle Un réside dans la transformation entre le triangle de la grille non masquée et la grille déformée pour déterminer la nouvelle position.

Ceci est expliqué explicitement en détail ici .

Une autre méthode (beaucoup plus compliquée) est la Spline à plaque mince (qui est également expliquée dans les diapositives ci-dessus).

Answer 2

J'ai compris que vous aviez une correspondance individuelle entre les points de grille enveloppés et non enveloppés. Et je suppose que la déformation n’est pas si extrême que vous pourriez avoir des lignes de grille qui se croisent (comme l’image que vous montrez).

La stratégie est exactement ce que suggère Jacob: Triangulez les deux grilles de telle sorte qu’il existe une correspondance un-à-un entre les triangles, localisez le point à cartographier dans la triangulation, puis utilisez les coordonnées barycentriques du triangle correspondant pour calculer la distance. nouvel emplacement de point.

Prétraitement

1. Générez la triangulation de Delaunay des points de la grille enveloppée, appelons-la WT .
2. Pour chaque triangle dans WT , ajoutez un triangle entre les sommets correspondants dans la grille non enveloppée. Cela donne une triangulation UWT des points non enveloppés.

Mappez un point p dans la grille enveloppée

1. Recherchez le triangle T (p1, p2, p3) dans le UWT qui contient p .
2. Calculez les coordonnées barycentriques (b1, b2, b3) de p dans T (p1, p2, p3)
3. Soit Tw (q1, q2, q3) le triangle dans WT correspondant à T (p1, p2, p3) . La nouvelle position est
   b1 * q1 + b2 * q2 + b3 * q3 .

Remarques Cela donne une fonction de déformation sous forme de spline linéaire . Pour un comportement plus lisse, on pourrait utiliser la même triangulation mais faire une approximation d'ordre supérieur, ce qui conduirait à un calcul un peu plus compliqué à la place des coordonnées barycentriques.

Answer 3

Les autres réponses sont excellentes. La seule chose que j’ajouterais, c’est que vous voudriez jeter un coup d’œil sur Déformation de forme libre pour décrire les déformations.

Si cela vous est utile, il est tout à fait possible d’adapter une grille / un réseau de déformation à vos paires connues et vous disposez alors d’une méthode très rapide pour déformer les points futurs.

Answer 4

Cela dépend beaucoup du nombre de points existants. Si vous n'en avez qu'un, vous ne pouvez pas vraiment en faire plus: vous pouvez compenser le deuxième point du même montant dans la même direction, mais vous ne disposez pas de suffisamment de données pour vraiment faire mieux que cela.

Si vous avez un nombre suffisant de points existants, vous pouvez ajuster la surface entre ces points et l'utiliser pour déterminer approximativement la position correcte du nouveau point. Si vous avez N points, vous pouvez toujours obtenir un ajustement parfait avec un polynôme d'ordre N, mais vous voulez rarement le faire. Vous devez plutôt deviner que la fonction d'étirement est une fonction d'ordre relativement faible (par exemple, quadratique ou cubique) et une surface aux points sur cette base. Vous placez ensuite votre nouveau point en fonction de la fonction de votre surface ajustée.