Défi logique : Insertion d'un point dans une courbe

[TheReveller]

Bonjour,

Dans le cadre d’un travail dans le domaine de l’ingénierie mécanique, j’ai voulu programmer un petit utilitaire de modélisation de courbe graphique.

Je rencontre un problème de logique pour l’insertion d’un point sur la courbe, je parle ici d’une option qui insère un point à la courbe et non qui ajoute le prochain point.

Bref, j’ai un tableau des coordonnées où chaque point est lié au prochain point, soit xy[0] à xy[n] où on a xy[i][0] la coordonnée x et xy[i][1] la coordonnée y. J’aimerais faire en sorte qu’avec cette option, si on clique au point (p[0], p[1]), soit respectivement les coordonnées (x, y), on insère ce point à l’endroit le plus logique entre deux points existants ou au tout début ou à la toute fin si cela semble plus logique. Ainsi, si on a les points 1, 2 et 3 et qu’on clique entre les points 1 et 2, le nouveau point inséré sera le point 2 tandis que les anciens points 2 et 3 deviennent les points 3 et 4.

Pour ce faire, j’ai pensé calculer pour chaque groupe de deux points successifs le point se situant au milieu de ces deux points et ensuite calculer la distance directe entre ce point milieu et le point à insérer. On insère le point à la position où la distance calculée est la plus courte. Par contre, cela ne gère pas le cas où la logique serait d’insérer le point au début ou à la fin de la courbe, les extrémités me posent problème.

De plus, il faudrait sûrement prévoir un ratio de distance entre les deux points analysés. Je m’explique : on a les points 1, 2 et 3 qui forment un L. La distance entre les points 1 et 2 est très grande tandis que la distance entre les points 2 et 3 est très petite. Même si la distance entre l’endroit où on a cliqué et le point milieu des points 2 et 3 est légèrement plus petite que celle pour les points 1 et 2, il est plus probable que l’endroit où l’on veut insérer le point soit entre les points 1 et 2.

C’est difficile d’être clair textuellement, j’essayerai de vous faire des cas plus visuels avec des captures d’écran pour les cas d’exception.

Proposez-moi vos idées et n’oubliez pas de me répondre d’un point de vue de langage informatique,

Merci.

[bombastus]

Salut,

Ce serais plus clair avec un exemple! Je pense avoir compris l'idée mais la logique d'insertion des points dépend en grande partie des caractéristiques des courbes que tu modélises...

[TheReveller]

Je vais donner quelques exemples, mais je ne peux pas pour l'instant.

Pour ce qui est de la logique d'insertion, je voudrais justement que ça soit une logique générale. Que tu dessines une courbe quadratique ou sinusoïdale, arctan ou une spirale, un zigzag, une maison, un chien ou un chat, il trouvera la position qui serait la plus logique à insérer même s'il ne semble pas y avoir de logique.

Merci.

[TheReveller]

Voici un screenshot pour exemple :

http://img7.imageshack.us/img7/7779/exemplep.jpg

Soit les numéros de points en blanc p[0] à p[4] et les points en noir les points #1 à #5.

Le but est d'offrir l'option d'insérer un point à la position qui semble la plus logique.

Verbalisation :

Si on dit qu'on insère le point #1 à la position p[1], alors on aura :
p[0] = p[0]
p[2] = p[1]
p[3] = p[2]
p[4] = p[3]
p[5] = p[4]
p[1] = #1

Questionnements et suppositions sur les calculs logiques :

Le point #1 devrait être inséré logiquement à la position p[1].
Le point #2 qui est à une distance considérable devrait-il être inséré à la position p[0] ou p[1] ?
Le point #3 devrait être inséré logiquement à la position p[4].
Le point #4 devrait être inséré logiquement à la positon p[4].
Le point #5 devrait être inséré logiquement à la position p[6].

Comment créer les conditions logiques ?

Définir si le point se trouve dans la zone projetée perpendiculairement à la ligne entre deux points. Ce que je veux dire, c'est qu'on a une pente créée par la ligne entre p[3] et p[4] par exemple où cette zone serait définie entre la droite perpendiculaire à cette pente passant par le point p[3] jusqu'à la droite perpendiculaire à cette pente passant par le point p[4]. Bref, le point #5 ne se trouve dans aucune de ces zones. Comment effectuer ce calcul de condition en code de boucles et conditions ?

Trouver la distance entre le point à insérer et chacune des droites qui contient ce point dans sa zone.

Pour le cas du point #2, comme définir que le point est rendu trop éloigné pour être inséré à la position p[1] et qu'il serait plus logique qu'il soit plutôt inséré à la position p[0] ? Il faut prévoir tenir compte de la longueur de la ligne de p[0] à p[1], puisque si la longueur de cette ligne était la même que celle de p[4] à p[5], il semblerait encore plus évidant que le point #2 devrait être inséré à la position p[0] au lieu de p[1].

Autres suggestions et idées ?

[fatal_error]

Salut,

d'abord une quote :

Ainsi, si on a les points 1, 2 et 3 et qu’on clique entre les points 1 et 2, le nouveau point inséré sera le point 2 tandis que les anciens points 2 et 3 deviennent les points 3 et 4.

Tout d'abord, c'est pe mieux de travailler avec des listes chainees, ou il te suffit d'insérer un point entre deux points existants, et qui te permet d'éviter le decalage de tous les autres points.
Ensuite, par "logique", je pense que la question c'est de minimiser la distance entre chaque point.
La comme ca et en non obtimisé :
Soit Y le point à insérer.
Soit d(YX_i) la distance du point Y a X_i

Code: Tout sélectionner

Xdeb = X_0 //on inserera le point entre Xdeb et Xfin
Xfin = X_1
Pour tous les points X_i (les X_i se suivants) Faire
...si d(YX_i)+d(YX_{i+1}) < dref
...alors Xdeb=X_i et Xfin=X_{i+1} et dref = d(YX_i)+d(YX_{i+1})
fin Fait
si Xdeb=X_0 et d(YXdeb)<d(YXfin)
alors Insérer Y en tete de liste
sinon si Xdeb=Xfin et d(YXfin)<d(YX_{fin -1})
alors Inserer Y en fin de liste
sinon Insérer Y entre Xdeb et Xfin

Concernant les points limite :
L'insertion en tete de liste se fait si le point Y est plus proche de X_0 que de tout autre point.
L'insertion en fin de liste se fait si le point Y est le plus proche de X_fin que de tout autre point.

Par contre, j'ai pas pris la même distance que toi ou je crois que toi tu projettes sur des droites alors que moi jfais une bete somme de distances.

[TheReveller]

Si je comprends bien, tu me dis de calculer la somme de la distance entre le point à insérer et les deux points successifs. Bref, si on veut insérer le point #1, on calcule sa distance de #1 à p[0] + #1 à p[1] et si cette distance est la plus petite par rapport aux distances de #1 à p[n] + #1 à p[n+1], alors on l'insère à p[1], sinon à p[n+1] ?

Par contre, je ne comprends pas comment tu gères les extrémités.

Et dans le cas de cette somme de distance, le point #4 serait inséré entre p[4] et p[5], de même que le point #3 serait inséré entre p[2] et p[3], tandis que je crois plutôt que ces deux points devraient être insérés entre p[3] et p[4].

J'ai mis en jaune ce que j'ai compris de ta méthode et en bleu ce que je pensais essayer comme méthode.

http://img17.imageshack.us/img17/1530/exemple2t.jpg

[fatal_error]

re,

en relisant plus attentivement ton message et grace a ta deuxieme figure, je vois a peu pres ce que tu veux faire.
Pour l'instant j'ai ca que pe ca peut aider :

Comment effectuer ce calcul de condition en code de boucles et conditions ?

Soit A et B deux points consécutifs.
Soit P le point qu'on veut insérer.
on peut projeter P sur AB :

Si , ca veut dire que P n'appartient pas a la zone.
Sinon, c'est qu'il appartient a la zone.

Trouver la distance entre le point à insérer et chacune des droites qui contient ce point dans sa zone.
Pour la distance, c'est tres facile. On a calculé la projection P' sur le segment [AB]. On a donc AP'P qui est rectangle en P. Avec pythagore ca devrait aller.

Pour le point P2 je t'avourrai ne pas avoir vraiment compris.

Concernant ton dernier post :

Par contre, je ne comprends pas comment tu gères les extrémités.

Si un point P est plus pres du point en tete de liste courant que tous les autres points, je voulais insérer en tete de liste, mais ca rend pas trop bien. Le coup du produit scalaire de ta méthode me parait mieux.

[TheReveller]

Ok, merci, je vais regarder ça quand j'aurai un peu plus de temps et je te reviens là-dessus plus tard.

Ce que je veux dire à propos des points qui me causent problèmes aux extrémités, c'est de savoir quand est-ce qu'il doit être inséré entre deux points ou inséré à une des extrémités.

J'ai ajouté le point #6 pour aider :

http://img208.imageshack.us/img208/9673/exemple3.jpg

On voit ici que le point #1 devrait logiquement être inséré entre les points p[0] et p[1] puisqu'il est très proche de cette ligne.

Par contre, le point #2 est considérablement loin de cette ligne, alors il devrait peut-être plutôt être inséré comme extrémité et devenir le point p[0].

Cependant, il faudrait considérer un certain ratio, puisque si on se fit à la ligne bleue, le point #6 est plus proche de la ligne p[4]-p[5] que le point #2 l'est de la ligne p[0]-p[1], mais puisque la distance qui sépare les deux points p[4] et p[5] (ligne orange) est très petite, le point #6 devrait être inséré à l'extrémité en tant que point p[6] au lieu d'être inséré entre les points p[4] et p[5].

Ce que je veux dire en plus simple : Comparons le point #1 et le point #6. Leur distance en ligne bleue et en ligne jaune est approximativement égale. Toutefois, il est plus logique d'insérer le point #1 entre p[0] et p[1] au lieu de le mettre à l'extrémité tandis qu'au contraire il est plus logique d'insérer le point #6 à l'extrémité au lieu de le mettre entre p[4] et p[5]. Qu'est-ce qui fait cette différence logique ? La distance entre p[0] et p[1] (ligne orange) comparativement à celle entre p[4] et p[5] (ligne orange) ou peut-être le ratio longeur ligne jaune divisé par longueur ligne bleue ou un peu des trois, je ne sais pas quoi faire de logique.

[Dlzlogic]

Bonjour,
Je suis un petit nouveau sur ce forum.
J'ai vu ce sujet, je ne peux pas m'empêcher de répondre.
D'abord sur un point très informatique, il est certain que la solution des listes chainées pour des lignes est à adopter dans tous les cas.
Concernant le problème d'insertion. Si on veut insérer un point, c'est à dire rajouter un point qui déformera la ligne, il ne me parait pas qu'il y de solution plus ou moins logique qu'une autre. Le calcul de la distance la plus faible aux segments de la ligne donnera la déformation la plus faible, mais qui dit que c'est justement cela que l'on cherche.
Donc pour ce problème, la solution que j'ai adoptée (il y a bien longtemps) est de commencer par cliquer sur un point proche du segment où sera inséré le point, et ensuite, cliquer sur le point à insérer.Il faur admettre que cette solution ne permet pas d'insérer un point au début ou à la fin de la ligne.
La solution que j'ai adopté dans ce cas là est de créer une nouvelle ligne, le nouveau point et le premier (ou le dernier et le nouveau), puis de raccorder les 2 lignes.

Là il s'agit naturellement l'insertion d'un point par un opérateur.
S'il s'agit d'un algorithme qui doit insérer un point, le raisonnement n'est pas très différent, le segment d'insertion est défini par l'algorithme, pour les insertions en limite, c'est pareil.

Cordialement.

[fatal_error]

salut,

j'ai gardé le sujet dans un coin de l'oeil. Du coup j'en profite pour te sous-tirer des infos

Le calcul de la distance la plus faible aux segments de la ligne donnera la déformation la plus faible, mais qui dit que c'est justement cela que l'on cherche.

Jusqu'a la je te suis.

Donc pour ce problème, la solution que j'ai adoptée (il y a bien longtemps) est de commencer par cliquer sur un point proche du segment où sera inséré le point, et ensuite, cliquer sur le point à insérer

La je ne te comprends plus.
Si on prends un segment [AB]. On se pose son "curseur" pas trop loin du segment, et on clique. On clique ensuite sur le point a insérer.
Mais a quoi refere la "ligne"? au segment créé par les deux cliques? ou a la ligne AMB avec M le point inséré a l'endroit du premier clic?



Concernant la logique j'avais reussi a trouver ca :
Etant donné n points x_1,...,x_n, l'insertion du point M est considéré comme logique si :
- si le segment x_ix_j donnant la ligne x_iMx_j ne coupe aucune autre ligne
- si le segment x_ix_j donnant la ligne x_iMx_j cree la deformation la moins importante (le pic est applati)
Mais caracteriser le pic est pas facile...

Ta méthode m'interesse, le problème est que je ne la comprends pas trop

[Dlzlogic]

Bonjour,
Je ne travaille pas en mécanique mais en topographie.
Donc, le contexte est celui-là : on veut créer un réseau de tuyaux rigides, donc un polygone. Ce polygone peut se refermer mais pas se recouper.
Je veux rajouter un angle dans ce polygone. J'identifie le segment dans lequel sera inséré le nouveau point. Le segment cherché est le segment parmi toutes les lignes disponibles qui sera le plus près du point utilisé poit l'identification, c'est à dire que la distance du point à sa projection sur le segment sera la plus faible. Une fois le segment trouvé, et donc la ligne, on peut cliquer sur le point à insérer, qui peut être n'importe où.

Cette méthode fonctionne parfaitement aussi lorsque les segments de ligne sont des arcs de cercle ou des arcs de parabole. C'est l'insertion du nouveau point qui est un peu plus compliquée.

Dans les deux cas (segment ou arc), la logique est strictement la même si l'opération de saisie est manuelle ou fait partie d'un algorithme.

Pour bien réaliser qu'aucune méthode "logique-automatique" n'est possible, il suffit d'imaginer que le point à insérer se trouve sur la bissectrice de l'angle formé par deux segments successifs.

Pour illustrer ce problème d'insertion : soit un réseau d'alimentation de candélabres. Il sera, par exemple, parallèle à la bordure de trottoir. On a positionné les candélabres, en général un à la fois parce qu'on s'arrange pour qu'ils ne soient pas n'importe où. Mais il faut alimenter les candélabres. Deux solution, d'abord la mauvaise, on dévie le réseau pour qu'il passe par les candélabres, ensuite la bonne : lorsque le réseau passe près du candélabre, on crée deux petits arcs de cercles pour l'alimenter. Cette opération, très longue à la main, est rendue automatique. Le choix du segment ( de droite ou d'arc) se fait par un test de proximité, l'insertion des différents points définissant les petits arcs est basée sur le même principe.
Par contre si il faut insérer un nouveau candélabre "très éloigné" du réseau déjà dessiné, il est impossible de déterminer "logiquement" à partir de quel tronçon la dérivation doit être faite. Là on utilise la méthode manuelle interactive.

Je suis très content d'avoir évoqué ce point qui m'a fait perdre quelques cheveux.
Cordialement.

[Dlzlogic]

Bonjour,
Je ne suis pas habitué à ce forum, et j'ai l'impression que mes post s'égarent ou partent je ne sais où Par exemple, l'avais répondu au message de fatal_error du 14 avril, et je ne le vois plus. Bref...
J'ai une autre application concernant l'insertion d'un point dans une ligne : il s'agit de trouver la courbe qui contient tous les points d'un semi de points.
On prend 3 points et on forme un triangle fermé qui tourne dans le sens horaire.

Pour le premier côté du triangle, on cherche le point qui se projette sur ce segment et qui en est le plus loin à gauche. On insère ce point dans le premier segment.
On recommence cette étape tant que l'on trouve un point à insérer.
Ensuite, on étudie le segment suivant de la ligne, jusqu'à ne plus trouver de point à insérer.
Dans la pratique, il vaut mieux dégrossir le problème en calculant un "grand rectangle", au lieu d'un petit triangle. De grand rectangle pourra par exemple avoir pour sommet le points les plus éloignés dans chacun des 4 quadrans. De toute façon il faut prendre les points de dapart qui seront certainement sur la ligne enveloppe recherchée, à moins de prévoir un algorithme de suppression de point.

Cordialement.