Discussion :

[kaukau]

Salut!
J'ai une courbe du plan, représentée par une liste de points comme ceci:
[(x,y)].
On considère que les points sont reliés entres eux par des petits segments de droite.
Cette courbe peut former des boucles, et ce que je cherche à faire c'est justement "couper" ces boucles!
Si une boucle est détectée, il suffit purement et simplement de la supprimer de la liste.
Une technique élégante pour faire ça??

Corentin

[GnuVince]

Salut!
J'ai une courbe du plan, représentée par une liste de points comme ceci:
[(x,y)].
On considère que les points sont reliés entres eux par des petits segments de droite.
Cette courbe peut former des boucles, et ce que je cherche à faire c'est justement "couper" ces boucles!
Si une boucle est détectée, il suffit purement et simplement de la supprimer de la liste.
Une technique élégante pour faire ça??

Corentin

Former des boucles, donc les valeurs de x peuvent revenir en arrière? Exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
[(0, 3), (1, 3), (2, 3), (1, 3), (4, 3)]

[Jedai]

Former des boucles, donc les valeurs de x peuvent revenir en arrière? Exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
[(0, 3), (1, 3), (2, 3), (1, 3), (4, 3)]

Je suppose que tu voudrais que cela devienne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

[(0, 3), (1, 3), (4, 3)]

Mais qu'en serait-il de :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
[(0, 3), (1, 3), (2, 3), (1, 3), (4, 3), (2, 3)]

??

Tu dois d'abord lever toutes les ambiguïtés de ce genre, ça t'aidera même à voir comment faire au final.

Autre facteur important : quelle taille font tes listes à peu près ? Et quelles sont les exigences de vitesse ?

--
Jedaï

[Jedai]

Par exemple une petite solution qui coupe toujours la dernière boucle possible :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
import Data.List
import qualified Data.Map as M
 
cutLasts :: (Ord a) => [a] -> [a]
cutLasts = reverse . fst . foldl' updateMapAndList ([],M.empty)
    where
      updateMapAndList (xs, m) x =
          if x `M.member` m
          then (m M.! x, m)
          else let xxs = x:xs in (xxs, M.insert x xxs m)

Mais ce n'est peut-être pas ce qui te conviendrait le mieux.

--
Jedaï

[kaukau]

GnuVince: oui

Mes listes sont grosses, puisqu'elles représentent vraiment des courbes avec plein de points. Les points sont très rapprochés les uns des autres.
Par exemple, le courbe peut ressembler à un "lambda", ou un "gamma".
Il faudra alors supprimer la boucle de la liste!!


Jedai: Je n'ai pas bien compris ta solution, je suis assez novice en Haskell!!!

Notez que la courbe peut se recroiser sur elle même sans qu'aucun des points constitutifs ne soient égaux...

Mon raisonnement impératif serait de faire un double parcours pour trouver les intersections... Pas terrible!

[Jedai]

Notez que la courbe peut se recroiser sur elle même sans qu'aucun des points constitutifs ne soient égaux

Ca change pas mal les choses !
Un double parcours semble légèrement suboptimal (pour être poli)... Peut-être une partition de l'espace serait-elle plus adaptée ? Type quadtree ? On pourrait ensuite utiliser une logique proche de celle employée dans ma méthode.

--
Jedaï

[Jedai]

Jedai: Je n'ai pas bien compris ta solution, je suis assez novice en Haskell!!!

Rien de bien compliqué en fait : Je fait un fold gauche sur la liste en passant deux informations : une Map et la liste sans boucle des points jusqu'ici (à l'envers). La Map associe chaque point à la liste sans boucle de points jusqu'à lui-même (à l'envers). A chaque nouveau point, il me suffit de consulter la Map pour savoir s'il a déjà été rencontré dans la liste, dans ce cas je remplace la liste sans boucle par la valeur associé au point dans la Map, sinon, je rajoute le point au début de ma liste et je place le couple (point, liste jusqu'ici) dans la Map.

Si tu veux plus de détails, n'hésite pas à poser des questions plus précises.

--
Jedaï