[Challenge] Grouper des points

(gile) · le 29 mars 2021

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 · le 29 mars 2021

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) · le 29 mars 2021

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 · le 29 mars 2021

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 · le 29 mars 2021

ah que les x, pardon

Luna · le 29 mars 2021

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 · le 29 mars 2021

pour le rendu ? 1 groupe par txt ?

(gile) · le 29 mars 2021

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 · le 29 mars 2021

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) · le 29 mars 2021

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 · le 29 mars 2021

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

j'ai modifié mon code

(gile) · le 29 mars 2021

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

Fraid · le 29 mars 2021

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 · le 29 mars 2021

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

(j(ai modifié mon code)

(gile) · le 29 mars 2021

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 · le 29 mars 2021

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) · le 29 mars 2021

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

Fraid · le 29 mars 2021

Quote

dans une plage [n-5.0, n+5.0

Luna · le 29 mars 2021

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) · le 29 mars 2021

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 · le 29 mars 2021

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) · le 29 mars 2021

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 · le 29 mars 2021

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) · le 29 mars 2021

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 · le 29 mars 2021

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.

Connexion

[Challenge] Grouper des points

Messages recommandés

(gile)

vincentp010

(gile)

Fraid

Fraid

Luna

Curlygoth

(gile)

Fraid

(gile)

Fraid

(gile)

Fraid

Fraid

(gile)

Fraid

(gile)

Fraid

Luna

(gile)

Fraid

(gile)

Luna

(gile)

Fraid

Créer un compte ou se connecter pour commenter

Créer un compte

Se connecter

Forums

Naviguer

Activité

Information importante