Challenge 12

Matt666 · le 8 octobre 2007

Et Bing encore un !!

il s'agit de supprimer les points alignés et au milieu de 2 autres dans une liste de points...

Ex :

(remove-align '((18.0071 2.97385 0.000000) (18.0071 11.0191 0.000000) (21.4685 11.0191 0.000000) (24.8363 11.0191 0.000000) (24.8363 7.93200 0.000000) (24.8363 2.97385 0.000000) (18.0071 2.97385 0.000000)))

->

 ((18.0071 2.97385 0.000000) (18.0071 11.0191 0.000000) (24.8363 11.0191 0.000000) (24.8363 2.97385 0.000000) (18.0071 2.97385 0.000000))

je sais pas si c'est assez clair...

Voilà ! bon courage !

Matt.

bseb67 · le 8 octobre 2007

Salut MAt666!

Pour le challenge11, je n'ai pas encore corriger le pb des points qui se suivent.

Pour ce nouveau challenge, il faut tester toutes les combinaisons possibles entre les points?

Ou seulement se dire que le point p1 et p2 forme une première ligne l1, p2 et p3 une deuxième l2, ...

et donc devoir si l2 est une continuité de l1 ?

Si c'est cela, je crois que j'ai du faire un truc dans ce genre, car pour tester un réseau, je vérifiai la superposition et le prolongement pour remplacer des morceaux de ligne par une seule ligne.

Là je dois retourner bosser, si ma femme me laisse tranquille ce soir, je reprendrai mon lisp pour répondre à ce challenge.

bseb67 · le 8 octobre 2007

Salut MAt666!

Pour le challenge11, je n'ai pas encore corriger le pb des points qui se suivent.

Pour ce nouveau challenge, il faut tester toutes les combinaisons possibles entre les points?

Ou seulement se dire que le point p1 et p2 forme une première ligne l1, p2 et p3 une deuxième l2, ...

et donc devoir si l2 est une continuité de l1 ?

Si c'est cela, je crois que j'ai du faire un truc dans ce genre, car pour tester un réseau, je vérifiai la superposition et le prolongement pour remplacer des morceaux de ligne par une seule ligne.

Là je dois retourner bosser, si ma femme me laisse tranquille ce soir, je reprendrai mon lisp pour répondre à ce challenge.

Bred · le 8 octobre 2007

si ma femme me laisse tranquille ce soir

Vantar ! ;) :)

Matt666 · le 8 octobre 2007

il faut tester toutes les combinaisons possibles entre les points?

Non, Il faut prendre 3 points par 3 points, et si les 3 points sont alignés, supprimer le point superflu... C'est tout.... Si les 3 points ne le sont pas, on passe aux autres !

Mais bon on peut faire cette variante aussi !

Ou seulement se dire que le point p1 et p2 forme une première ligne l1, p2 et p3 une deuxième l2, ... et donc devoir si l2 est une continuité de l1 ?

je ne pense pas qu'il faille fonctionner comme ça... Les points sont des points, c'est tout... Vois plutôt ces points comme les sommets d'une polyligne...

Ce qui fait une nouvelle contrainte en fait (je viens d'y penser)... Zut c'est pas très clair mon truc....

Dans la fouchette des trois points à vérifier, il faut que le point milieu soit strictement entre les deux points précédents...

Voilà... je change l'énoncé...

Merci bseb67 !!

PS : Tout à fait d'accord bred :cool:

A bientot !

[Edité le 8/10/2007 par Matt666]

Matt666 · le 8 octobre 2007

Au fait Gile sera un peu avantagé, voire il doit avoir déjà une fonction similaire... il s'est déjà penché sur des fonctions d'alignement...

Mais bon, cela ne veut peut être rien dire...

Quoique.. :P

bseb67 · le 8 octobre 2007

Re-salut!

Petite correction, ou plus tot précision:

si ma femme me laisse tranquille ce soir

Signifiai si j'ai le droit d'aller sur le pc :), pas de ne pas sortir du lit ;).

Comme je ne suis pas là 12h/24 et que je suis toute la journée sur un pc, le soir elle veut que l'on reste ensemble. Mais c'est vrai que des fois j'aime bien jouer le soir et seul :cool:

(gile) · le 8 octobre 2007

Salut,

Tout ça n'est pas très clair.

Il s'agirait de "nettoyer" une polyligne des sommets alignés intermédiares, pour ne conserver que les sommet à l'extémité de chaque segment, c'est ça ?

http://img261.imageshack.us/img261/4383/challenge12za2.png

Ça demande quand même quelques précisions :

- s'il y a plus d'un sommet intermédiare (4 points alignés ou plus), il faut bien tous les supprimer ?

- dans la liste de points, les sommets sont-ils dans l'ordre (comme quand on récupère les sommets d'une polyligne) ?

Si la réponse aux deux question est oui j'ai une solution en quelques lignes de code (j'attends un peu...)

bseb67 · le 8 octobre 2007

Autre petite question Mat666,

Ton exemple comporte des "faux" points 3D, faut-il faire une méthode 2D et une 3D?

Et oui, je suis sur mon pc perso :cool: !! Ma femme est fatigué et va donc se coucher! :D

(gile) · le 8 octobre 2007

Salut,

faut-il faire une méthode 2D et une 3D?

Une méthode 3d marchera forcément en 2d.

Matt666 · le 8 octobre 2007

Gile c'est exactement ça !

Par contre autre exemple :

(remove-align '((114.03 270.06) (153.248 270.06) (153.248 259.453) (153.248 250.23) (153.248 239.162) (153.248 227.633) (153.248 217.949) (135.715 217.949) (135.715 205.498) (153.248 205.498) (153.248 194.43) (153.248 187.974) (153.248 176.445) (114.03 176.445)))

->

((114.03 270.06) (153.248 270.06) (153.248 217.949) (135.715 217.949) (135.715 205.498) (153.248 205.498) (153.248 176.445) (114.03 176.445))

Ca veut dire que si des points sont alignés mais ne se suivent pas, ne pas les supprimer !

Bseb67, des points 2D suffisent... 3D si tu veux, mais ça change pas grand-chose je pense...

Et aussi, c'est MATT, pas Mat.. didon... :D

Merci pour ces précisions vous deux !!

A bientôt..

Matt.

[Edité le 8/10/2007 par Matt666]

bseb67 · le 9 octobre 2007

Salut!

Désolé Matt666 :o, j'espère que tu m'en voudra pas ;).

Sinon petit message pour (gile), j'ai un premier jet pour ce challenge, je cherche à l'améliorer en me servant de benchmark, et bien il n'est pas très fiable :P .

J'ai voulu tester mes deux méthodes pour une sous fonction, j'obtiens 1.00 pour la plus lente (lap lus lente aura toujours 1.00), mais l'autre le coef va de 1.00 à 1.30 :o. Des fois c'est plus rapide, des fois non :casstet: .

Donc pour la mesure de temps, il faudrai rien faire d'autre sur le pc. Comme on ne peut mesurer le temps CPU (comme je le faisais en C++).

Il me reste aussi à corriger le challenge10, j'ai un petit souci pour des suites de "." dans une suite de chiffres.

(gile) · le 9 octobre 2007

je cherche à l'améliorer en me servant de benchmark, et bien il n'est pas très fiable

Non, il n'est pas très précis, et l'auteur précise dans ces commentaires que les résultats sont altérés par les taches de fond, tout comme l'est d'ailleurs une interprétation d'expression LISP hors Benchmark.

Je pense tout de même qu'il peut être utilisé en en faisant plusieurs de suite, on arive à trouver une moyenne et il faut penser à relativiser les résultats : 32768 itérations en 1047 ou 1063 secondes, ça fait une différence moyenne de environ 0.0005 millisecondes pour une évaluation.

(benchmark '((/ 3 2.0) (* 3 0.5)))

Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

(* 3 0.5).....1047 / 1.02

(/ 3 2.0).....1063 / 1

_$

_$ (benchmark '((/ 3 2.0) (* 3 0.5)))

Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

(/ 3 2.0).....1047 / 1

(* 3 0.5).....1047 / 1

_$ (benchmark '((/ 3 2.0) (* 3 0.5)))

Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

(/ 3 2.0).....1047 / 1

(* 3 0.5).....1047 / 1

_$ (benchmark '((/ 3 2.0) (* 3 0.5)))

Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):

(/ 3 2.0).....1047 / 1.01

(* 3 0.5).....1062 / 1

bseb67 · le 9 octobre 2007

Salut (gile)!

Je suis un peu décu qu'il n'y a pas beaucoup de différence entre 3/2.0 et 3*0.5,

car la division par 2 est censé être la division (après 1) la plus rapide. A croire que *0.5

est traduit en /2.0.

Bonne soirée :)

Bred · le 9 octobre 2007

Salut.....

Ben je suis largué !...

en fait je pense qu'il n'y a qu'une seule manière de résoudre ton problème : un fonction récursive ... ;)

et je sais que (gile) est sur les starting-bloc....

Le truc que j'ai essayé de faire c'est de tester un l'angle d'un point avec tous les autres pour ressortir les points alignés... puis à partir de ces points alignés je teste la distance pour ressortir les plus éloigné et suprimer les autres...

mais je plante lamentablement sur la manière d'interroger TOUS les points, dans toutes les configurations possibles....

J'abandonne pour l'instant....

Un challenge trés interressant !...

La routine pour tester une multitude de points les uns par rapport aux autre me semble être un trés bon outils !....

(gile) · le 10 octobre 2007

Bon, beacoup de digressions et aucune réponse pour l'instant.

Je vais essayer de poser l'énnoncé de manière claire et concise (du moins tel que je l'ai compris et que Matt666 l'a confirmé).

Soit une liste de points successifs ordonnée comme celle des sommets d'une polyligne :

((3.0 2.0) (5.0 2.0) (8.0 2.0) (10.0 4.0) (11.0 5.0) (11.0 2.0) (13.0 2.0) (15.0 2.0) (18.0 2.0))

Il s'agit, pour toutes les séquences de points alignés dans la liste de ne conserver que le premier et le dernier de chaque séquence :

((3.0 2.0) (8.0 2.0) (11.0 5.0) (11.0 2.0) (18.0 2.0))

http://img186.imageshack.us/img186/8955/challenge122ky3.png

PS : Bred, si tu testes l'alignement des deux premiers points avec tous les autres points de la liste, tu ne conserveras pas les deux segments horizontaux de l'exemple.

D'autre part, il me semble qu'il est démontré que toute fonction récursive a au moins un équivalent itératif.

Bred · le 10 octobre 2007

:casstet:

une liste de points successifs ordonnée

Hey !!!!

je n'avais pas compris ça !

Si c'est ordonnée, ça change tout !!!!!

PS : Bred, si tu testes l'alignement des deux premiers points avec tous les autres points de la liste, tu ne conserveras pas les deux segments horizontaux de l'exemple.

En effet, merci, ton exemple est trés parlant.

D'autre part, il me semble qu'il est démontré que toute fonction récursive a au moins un équivalent itératif.

Certainement, mais je pense que pour un traitement de "boucle de boucle" par élément à comparer à x éléments, la récursivité semble être la meilleur arme... si on sait la manier....

[Edité le 10/10/2007 par Bred]

Bred · le 10 octobre 2007

Re,

alors, ma première proposition vite fait et pas trés stylé :

(defun remove-align (lst / i lst-t)
 (setq i 0
lst-t lst)
 (repeat (- (length lst) 2)
   (if (equal (angle (car lst-t) (cadr lst-t))
       (angle (car lst-t) (caddr lst-t)))
     (setq lst (vl-remove (cadr lst-t) lst)))
   (setq lst-t (vl-remove (car lst-t) lst-t)
  )
   )
 lst
 )

... j'essaye de faire mieux....

bseb67 · le 10 octobre 2007

Bon, alors je dépose aussi. Mon truc est plus long, car je ne suppose pas que pi est entre pi-1 et pi+1 et s'il n'y a pas des points confondus.

On peut tomber sur des mickeys qui font des aller-retour ou

clique deux fois au même endroit ;)!

 
;------------------------------;
; nom: points_egaux            ;
; role: test si les deux points;
;       sont égaux ou non      ;
; param: p1 => point n°1       ;
;        p2 => point n°2       ;
; retour: t si oui             ;
;         nil sinon            ;
; date: 25/04/2007             ;
; BLAES Sébastien              ;
;------------------------------;
(defun points_egaux( p1 p2 / res)

(setq res t marge 1e-9)

; on compare x
(if (> (abs (- (car p1) (car p2))) marge)
	(setq res nil)
	; on compare y
	(if (> (abs (- (cadr p1) (cadr p2))) marge)
		(setq res nil)
		; on compare z
		(if (> (abs (- (caddr p1) (caddr p2))) marge)
			(setq res nil)
		) ; if z
	) ; if y
) ; if x

res

) ; points_egaux




;-------------------------------;
; nom: aumilieu                 ;
; role: test si le point p1 est ;
;       entre les deux points p2;
;       et p3                   ;
; param: p1 => point 3D n°1     ;
;        p2 => point 3D n°2     ;
;        p3 => point 3D n°3     ;
; retour: t si oui              ;
;         nil sinon             ;
; date: 25/04/2007              ;
; BLAES Sébastien               ;
;-------------------------------;
(defun aumilieu( p1 p2 p3 / d1 d2 d3)

(setq d1 (distance '(0.0 0.0 0.0) p1)
      d2 (distance '(0.0 0.0 0.0) p2)
      d3 (distance '(0.0 0.0 0.0) p3)
) ; setq

 	(cond
  	( (or (and (<= d2 d1) (<= d1 d3)) (and (<= d3 d1) (<= d1 d2)))
	 	t	
	) ; vrai

	(t
	  	nil
	) ; sinon c'est faux

) ; cond

) ; aumilieu

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;; CHALLENGE12 ;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;--------------------------------;
; nom: remove-align-bseb         ;
; role: simplifie une suite de   ;
;       points: si trois qui se  ;
;       suivent dans la liste l  ;
;       sont alignés, on supprime;
;       celui du milieu          ;
; param: l => liste de points    ;
; retour: liste simplifiée       :
; date: 08/10/2007               ;
; BLAES Sébastien                ;
;--------------------------------;
(defun remove-align-bseb( l / res cpt lg)

 	(setq res l cpt 1 lg (1- (length l)))

 	(while (< cpt lg)

  	; on test d'abord si les points ne sont pas égaux
  	(cond
	  	((points_egaux (nth (1- cpt) res) (nth cpt res))
			; on retire cpt
			(setq res (vl-remove (nth cpt res) res) lg (1- (length res)))
		) ; cpt-1 = cpt

		((points_egaux (nth cpt res) (nth (1+ cpt) res))
			; on retire cpt+1
			(setq res (vl-remove (nth (1+ cpt) res) res) lg (1- (length res)))
		) ; cpt = cpt+1
		
		; on compare l'angle par rapport à l'axe des x de cpt-1 et cpt
		; avec la droite cpt cpt+1
		((= (abs (angle (nth (1- cpt) res) (nth cpt res))) (abs (angle (nth cpt res) (nth (1+ cpt) res))))
			; on supprime le point au milieu des 2 autres
		 	(setq d1 (distance '(0.0 0.0 0.0) (nth (1- cpt) res))
			      d2 (distance '(0.0 0.0 0.0) (nth cpt res))
			      d3 (distance '(0.0 0.0 0.0) (nth (1+ cpt) res))
			) ; setq

		  	(cond
				( (or (and (<= d1 d2) (<= d2 d3)) (and (<= d3 d2) (<= d2 d1)))
				 	(setq res (vl-remove (nth cpt res) res) lg (1- (length res)))	
				) ; cpt au milieu
			  	( (or (and (<= d2 d1) (<= d1 d3)) (and (<= d3 d1) (<= d1 d2)))
				 	(setq res (vl-remove (nth (1- cpt) res) res) lg (1- (length res)))	
				) ; cpt-1 au milieu

				(t
				 	(setq res (vl-remove (nth (1+ cpt) res) res) lg (1- (length res)))	
				) ; sinon c'est cpt+1 au milieu

			) ; cond
		 	
		)

		(t
		  	; sinon on incrémente cpt
		       	(setq cpt (1+ cpt))
		) ; sinon
		
	) ; cond
) ; while

res

) ; remove-align-bseb

Bred · le 10 octobre 2007

Ma solution revu en un peu plus "stylé"... :P

(defun remove-align (lst / lst-t)
 (setq lst-t lst)
 (mapcar '(lambda (x1) (if (> (length (member x1 lst)) 2)
		  (if (equal (angle x1 (cadr (member x1 lst)))
			     (angle x1 (caddr (member x1 lst))))
		    (setq lst-t (vl-remove (cadr (member x1 lst)) lst-t))))) lst)
 lst-t
 )

On peut tomber sur des mickeys qui font des aller-retour ou
clique deux fois au même endroit !

T'aurais un exemple de liste (pour regarder ça....)

merci

bseb67 · le 10 octobre 2007

Voilou!

(setq lst '((2031.72 887.831 0.0) (1103.09 444.369 0.0) (1800.07 281.238 0.0) (2479.32 281.238 0.0) (1242.68 281.238 0.0) (1242.68 -141.286 0.0) (1242.68 748.925 0.0)))

Bon, il n'y a pas de points confondus

:cool:

Je le remarque en faisant mes lisps, je dois souvent pallier au fait que les données ne sont pas toujours comment elles devraient être, et là, c'est surtout le traitement de ces cas spéciaux qui

t'alourdissent le code et le temps d'exécution.

Sinon, j'aurai fait le même premier code que toi Bred. :)

Et bien pour ce cas là, c'est pas vraiment bon:

(setq lst '((1407.97 589.961 0.0) (1103.09 444.369 0.0) (1800.07 281.238 0.0) (2479.32 281.238 0.0) (1242.68 281.238 0.0) (1242.68 -141.286 0.0) (1242.68 281.238 0.0)))

Car l'aller-retour sur point l'avant avant dernier point, supprime le dernier morceau de ligne.

[Edité le 10/10/2007 par bseb67]

(gile) · le 10 octobre 2007

Super, ça démarre :D

citation extraite du message original:
On peut tomber sur des mickeys qui font des aller-retour ou
clique deux fois au même endroit !

T'aurais un exemple de liste (pour regarder ça....)
merc

Dans le dernier exemple que je donne tu inverses dans l'ordre de la liste (13 2) et (15 2) ; à mon avis dans ce cas, il faut aussi les supprimer, en tout cas j'avais compris comme ça, et ma routine le fait, comme elle supprime les sommets superposés.

Deux versions, une récursive (pour le style)

(defun remove-align (lst)
 (if (cddr lst)
   (if	(inters (car lst) (cadr lst) (car lst) (caddr lst))
     (cons (car lst) (remove-align (cdr lst)))
     (remove-align (cons (car lst) (cddr lst)))
   )
   lst
 )
)

la même avec while (moins concise mais plus rapide)

(defun remove-align (lst / rslt)
 (while (caddr lst)
   (if	(inters (car lst) (cadr lst) (car lst) (caddr lst))
     (setq rslt (cons (car lst) rslt)
    lst	 (cdr lst)
     )
     (setq lst (cons (car lst) (cddr lst)))
   )
 )
 (append (reverse rslt) lst)
)

Bred · le 10 octobre 2007

Ah !

j'avais commencé à regarder avec inters, mais je tournais en rond !!!.....

Bonne idée !

Bred · le 10 octobre 2007

Voilou!
(setq lst '((2031.72 887.831 0.0) (1103.09 444.369 0.0) (1800.07 281.238 0.0) (2479.32 281.238 0.0) (1242.68 281.238 0.0) (1242.68 -141.286 0.0) (1242.68 748.925 0.0)))

:casstet:

Il n'y a aucun point à enlever dans cette liste....

et pour les doublons, tu as ça :

;;; REMOVE_DOUBLES - Suprime tous les doublons d'une liste
(defun remove_doubles (lst)
(if lst
(cons (car lst) (remove_doubles (vl-remove (car lst) lst)))
)
)

... devine de qui c'est ?

(gile) · le 10 octobre 2007

j'avais commencé à regarder avec inters, mais je tournais en rond !!!....

Il s'avère qu'avec les dernières listes de bseb la méthode inters supprime un peu trop de sommets.

Je revois ma copie

(defun remove-align-gile1 (lst)
 (if (cddr lst)
   (if	(equal (angle (car lst) (cadr lst))
       (angle (cadr lst) (caddr lst))
)
     (remove-align-gile1 (cons (car lst) (cddr lst)))
     (cons (car lst) (remove-align-gile1 (cdr lst)))
   )
   lst
 )
)

(defun remove-align-gile2 (lst / rslt)
 (while (caddr lst)
   (if	(equal (angle (car lst) (cadr lst))
       (angle (cadr lst) (caddr lst))
)
     (setq lst (cons (car lst) (cddr lst)))
     (setq rslt (cons (car lst) rslt)
    lst	 (cdr lst)
     )
   )
 )
 (append (reverse rslt) lst)
)

[Edité le 11/10/2007 par (gile)]

Connexion

Challenge 12

Messages recommandés

Matt666

bseb67

bseb67

Bred

Matt666

Matt666

bseb67

(gile)

bseb67

(gile)

Matt666

bseb67

(gile)

bseb67

Bred

(gile)

Bred

Bred

bseb67

Bred

bseb67

(gile)

Bred

Bred

(gile)

Créer un compte ou se connecter pour commenter

Créer un compte

Se connecter

Forums

Naviguer

Activité

Information importante