[Challenge] Grouper des points

[(gile)]

Salut,

Un nouveau challenge (tout langage accepté).

L'objectif est de définir une fonction pour grouper les points (coordonnées) d'une liste en fonction de leur coordonnée X avec une tolérance de 10 unités.
La fonction devra prendre comme argument une liste de points 2d (x y) ou 3d (x y z) et renvoyer les points groupés sous la forme que permet le langage utilisé (en LISP ce sera forcément une liste de sous-listes, avec d'autre langages, ça peut-être une autre structure de données : un tableau déchiqueté, un dictionnaire, ...).

Exemple, avec la liste suivante en entrée :

(setq pts
       '((14.4 4.7)
	 (4.8 0.7)
	 (8.0 0.9)
	 (9.3 4.7)
	 (-14.3 14.3)
	 (-6.3 14.2)
	 (-13.6 7.5)
	 (-1.9 -3.2)
	 (2.4 -4.9)
	 (6.6 11.2)
	 (-6.6 4.7)
	)
)

on devrait obtenir 3 groupes :

((-6.6 4.7) (-13.6 7.5) (-6.3 14.2) (-14.3 14.3))
((2.4 -4.9) (-1.9 -3.2) (4.8 0.7))
((6.6 11.2) (9.3 4.7) (8.0 0.9) (14.4 4.7))

On pourra ensuite pousser un peu plus loin pour rendre la fonction plus générique en passant la tolérance en argument, puis en groupant par X et Y.

[vincentp010]

Je ne comprend pas comment tu définis la séparation avec ta tolérance de 10 unités.

Qu'est ce qui empêche (2.4 -4.9) d'être groupé avec (-6.6 4.7) ?

[(gile)]

Si tu groupes (2.4 -4.9) avec (-6.6 4.7), ce qui est envisageable, tu décales les groupes et (4.8 0.7) ne pourra plus être dans le même groupe que (2.4 4.9).

Tout dépend de l'algorithme de groupage...

[Fraid]

Comprend pas, peux tu expliquer à quoi correspond le décalage

on groupes les points qui sont à moins de 10 unités de distance?

cela ne correspond pas à ton exemple alors

[Fraid]

ah que les x, pardon

[Luna]

Coucou,

Grâce à la nouvelle structure du site, je viens de découvrir ce forum :3

Ce n'est pas très opti' mais voici ma première proposition au challenge :
 

(defun mergepts (pt-list fuzz / mn i lst grp)

	(defun grouppts (pt-list fuzz / lst)

		(setq lst 	(list
					(vl-remove-if '(lambda (pt) (< (+ mn fuzz) (car pt))) pt-list)
					(vl-remove-if-not '(lambda (pt) (< (+ mn fuzz) (car pt))) pt-list)
				)
		)

	)

	(setq mn (apply 'min (mapcar 'car pt-list))
	      i 0
	)
	(while pt-list
		(setq grp (grouppts pt-list (* (setq i (1+ i)) fuzz))
		      lst (cons (car grp) lst)
		      pt-list (cadr grp)
		)
	)
	(reverse lst)

)

Quote

Commande: (setq pt-lst '((14.4 4.7) (4.8 0.7) (8.0 0.9) (9.3 4.7) (-14.3 14.3) (-6.3 14.2) (-13.6 7.5) (-1.9 -3.2) (2.4 -4.9) (6.6 11.2) (-6.6 4.7)))
Commande: (mergepts pt-lst 10)
(
   ((-14.3 14.3) (-6.3 14.2) (-13.6 7.5) (-6.6 4.7))
   ((4.8 0.7) (-1.9 -3.2) (2.4 -4.9))
   ((14.4 4.7) (8.0 0.9) (9.3 4.7) (6.6 11.2))
)

Bisous,
Luna

Modifié le 29 mars 2021 par Luna

[Curlygoth]

pour le rendu ? 1 groupe par txt ?

[(gile)]

25 minutes ago, Curlygoth said:

pour le rendu ? 1 groupe par txt ?

quel rendu ? quel txt ?

On a une collection de points (en VBA j'imagine que c'est un tableau de variants de type tableau de 2 ou 3 Doubles). On passe ce tableau à une fonction (Function en VBA) qui groupe les points par coordonnée X à 10 unités près et retourne les groupes dans le type de collection que tu veux (en VBA, j'imagine un tableau déchiqueté -un tableau de tableaux de points, à moins qu'il esxiste des structures de données plus adaptées).

[Fraid]

Bonjour,

Mon petit truc

(defun groupt (lstpt tol / ret cpt l pt)
	(setq lstpt (vl-sort lstpt '(lambda (x y) (< (car x) (car y))))
		  cpt 1 
		  l (list (car lstpt))
	)
	(while (setq pt (nth cpt lstpt))
	  (if (< (abs(- (caar l)(car pt))) tol)
		(setq l (append l (list pt)))
		(setq ret (append ret (list l)) l (list pt))
	  )
	  (setq cpt (1+ cpt))
	)
	(append ret (list l))
)

 

Modifié le 29 mars 2021 par Fraid

[(gile)]

Super ! Ça joue.

@Luna Super, ça fonctionne, il y  a peut-être moyen d'optimiser, de rendre plus générique, de grouper par X et Y... mais ne te presse pas trop de donner des réponses pour ne pas décourager les autres.

@Fraid Ça semble un bon début, mais il manque des points dans la liste renvoyée.

À tous, il y a encore plein de réponses possible, en cherchant l'optimisation, la concision, la lisibilité, la généricité, ...

[Fraid]

Effectivement le dernier groupe n'étais pas pris en compte

j'ai modifié mon code

[(gile)]

@Fraid Il me semble que les points (6.6 11.2) et (8.0 0.9) devraient être dans le denier groupe...

[Fraid]

 

4 hours ago, (gile) said:

Tout dépend de l'algorithme de groupage...

Selon la méthode employée, on auras des groupes différents, comme tu l'as dit.

la, je suis partis sur la différence avec le 1er point de chaque groupe

[Fraid]

En changeant juste le vl-sort, j'ai des groupes différents

(j(ai modifié mon code)

[(gile)]

1 hour ago, Fraid said:

Selon la méthode employée, on auras des groupes différents, comme tu l'as dit.

la, je suis partis sur la différence avec le 1er point de chaque groupe

OK, au temps pour moi, j'ai mal posé l'énoncé. Ton algorithme fonctionne avec l’énoncé tel que posé dans le premier message.
Quand je parlais d'une tolérance de  10 unités, je pensais les points dont la coordonnée X est dans une plage [n-5.0, n+5.0[, autrement grouper les points par colonnes de 10 unités  de large, parce que pour la suite, j'envisageais un groupage par X et Y (quadrillage 10x10 ou nxn).

[Fraid]

tu t'est un peu mélangé les pédales la...

si c'est 5 alors dans ta liste de retour (14.4 4.7) devrais être seul alors...

[(gile)]

Non, (14.4 4.7) est dans la plage [5.0, 15.0[

[Fraid]

Quote

dans une plage [n-5.0, n+5.0

 

[Luna]

Si l'énoncé n'est pas clair, rien ne vas plus ! En effet l'exemple ici présenté peut être lu de plusieurs manières différentes :

- On définit le bornage à partir de la valeur minimal de la liste (ici -14.3) permettant ainsi de créer les bornages [-14.3 , -4.3[, [-4.3 , 5.7[ et [5.7 , 15.7[
- On définit un bornage centrée sur 0 et d'un pas d'unités 10 permettant ainsi de créer les bornages [-15.0 , -5.0[, [-5.0 , 5.0[ et [5.0 , 15.0[

Ainsi avec l'exemple donné, impossible en soit de différencier les deux avec l'énoncé actuel. Mais sur des listes différentes, les résultats seront non fonctionnels. Bon bah dans ce cas, on retourne à nos claviers !

Concernant le groupement en X et Y, en quoi cela consiste précisément ? Faut-il que les X et Y respectent la même règle (ce qui risque donc de créer de nombreuses sous-listes d'un unique point) ou bien c'est d'avoir le choix entre le groupement des X et le groupement des Y ?
En d'autres termes, le résultat attendu pour l'exemple en groupement X et Y doit correspondre à cela ?

Quote

((-14.3 14.3) (-13.6 7.5) (-6.3 14.2)) ;; X -> [-15.0 , -5.0[ et Y -> [5.0 , 15.0[
((-6.6 4.7)) ;; X -> [-15.0 , -5.0[ et Y -> [-5.0 , 5.0[
((-1.9 -3.2) (2.4 -4.9) (4.8 0.7)) ;; X -> [-5.0 , 5.0[ et Y -> [-5.0 , 5.0[
((6.6 11.2)) ;; X -> [5.0 , 15.0[ et Y -> [5.0 , 15.0[
((8.0 0.9) (9.3 4.7) (14.4 4.7)) ;; X -> [5.0 , 15.0[ et Y -> [-5.0 , -5.0[

 

Bisous,
Luna

[(gile)]

Je suis vraiment désolé pour la confusion.
Au départ, dans mon esprit, c'était un groupage par intervalles de 10 unités du type [-15, -5[, [-5, 5[, [5, 15[ ... Mais quand @Fraid a commencé du plus petit x, je me suis dit pourquoi pas, tant qu'on respecte un pas de 10 unités. En plus je trouvais intéressante l'idée de commencer par trier la liste. Je n'ai pas voulu fermer de porte, mais avec un groupage par la distance depuis le 1er point de chaque groupe, on n'a plus forcément un pas régulier.

2 hours ago, Luna said:

Concernant le groupement en X et Y, en quoi cela consiste précisément ? Faut-il que les X et Y respectent la même règle (ce qui risque donc de créer de nombreuses sous-listes d'un unique point) ou bien c'est d'avoir le choix entre le groupement des X et le groupement des Y ?
En d'autres termes, le résultat attendu pour l'exemple en groupement X et Y doit correspondre à cela ?

Quote

((-14.3 14.3) (-13.6 7.5) (-6.3 14.2)) ;; X -> [-15.0 , -5.0[ et Y -> [5.0 , 15.0[
((-6.6 4.7)) ;; X -> [-15.0 , -5.0[ et Y -> [-5.0 , 5.0[
((-1.9 -3.2) (2.4 -4.9) (4.8 0.7)) ;; X -> [-5.0 , 5.0[ et Y -> [-5.0 , 5.0[
((6.6 11.2)) ;; X -> [5.0 , 15.0[ et Y -> [5.0 , 15.0[
((8.0 0.9) (9.3 4.7) (14.4 4.7)) ;; X -> [5.0 , 15.0[ et Y -> [-5.0 , -5.0[

C'est exactement à ça que je pensais. On peut envisager de spécifier le pas via un argument (ou deux pour un pas différent en X et en Y).

[Fraid]

Un essai qui produit un groupe par point 

(defun groupt (lstpt tol / ret l di)
	(foreach pt1 lstpt
		(setq l (list pt1))
		(foreach pt2 lstpt
			(setq di (distance pt1 pt2))
			(if (and (/= di 0)(< di tol))
				(setq l (append l (list pt2)))
			)
		)
		(setq ret (append ret (list l)))
	)
	ret
)

(GROUPT pts 10.0)

->
(((14.4 4.7) (8.0 0.9) (9.3 4.7)) 
((4.8 0.7) (8.0 0.9) (9.3 4.7) (-1.9 -3.2) (2.4 -4.9)) 
((8.0 0.9) (14.4 4.7) (4.8 0.7) (9.3 4.7) (2.4 -4.9)) 
((9.3 4.7) (14.4 4.7) (4.8 0.7) (8.0 0.9) (6.6 11.2)) 
((-14.3 14.3) (-6.3 14.2) (-13.6 7.5)) 
((-6.3 14.2) (-14.3 14.3) (-13.6 7.5) (-6.6 4.7)) 
((-13.6 7.5) (-14.3 14.3) (-6.3 14.2) (-6.6 4.7)) 
((-1.9 -3.2) (4.8 0.7) (2.4 -4.9) (-6.6 4.7)) 
((2.4 -4.9) (4.8 0.7) (8.0 0.9) (-1.9 -3.2)) 
((6.6 11.2) (9.3 4.7)) 
((-6.6 4.7) (-6.3 14.2) (-13.6 7.5) (-1.9 -3.2)))

 

[(gile)]

1 hour ago, Fraid said:

Un essai qui produit un groupe par point 

Là on s'éloigne carrément.

L'idée de ce challenge m'est venue de cette demande sur le forum Autodesk .NET et j'ai repensé à ce challenge sur TheSwamp où qjchen, qui lance les hostilités avec une routine LISP qui traite 10000 points en 45 secondes arrivera à traiter ces mêmes points en 3.2 secondes toujours en LISP mais en implémentant un algorithme "divide and conqueer" qui utilise le groupement des points "par colonnes" (réponse #23), puis en 0.79 secondes en groupant les points dans un quadrillage (CF réponse #41).

Il s'agirait donc bien de grouper les points par plages de 10 unités
- soit dans des intervalles de ... [-15, -5[, [-5, 5[, [5, 15[
- soit en partant du plus petit X mais en respectant le pas de 10 : [-14.3, -4.3[, [-4.3, 4.3[, 4.3, 14.3[ ...

[Luna]

Petite erreur de syntaxe sur 

1 minute ago, (gile) said:

- soit en partant du plus petit X mais en respectant le pas de 10 : [-14.3, -4.3[, [-4.3, 4.3[, 4.3, 14.3[ ...

car si on définit un écart de 10, on aurait plutôt [-14.3, -4.3[, [-4.3, 5.7[, [5.7, 15.7[ ...

Bon aller j'y retourne en essayant de répondre au challenge de manière plus générale (probablement plus longue aussi) T_T

Bisous,
Luna

[(gile)]

1 minute ago, Luna said:

car si on définit un écart de 10, on aurait plutôt [-14.3, -4.3[, [-4.3, 5.7[, [5.7, 15.7[ ...

Oui, tu as raison. Je vais me coucher...

[Fraid]

8 minutes ago, (gile) said:

Là on s'éloigne carrément

Oui, mais je trouvais cela rigolo en peux de fonctions.

et pas tant que cela si on nettoie la liste des redondances.