Aller au contenu

[Challenge] Grouper des points


(gile)
 Partager

Messages recommandés

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.

Gilles Chanteau - gileCAD -
Développements sur mesure pour AutoCAD
ADSK_Expert_Elite_Icon_S_Color_Blk_125.png

Lien vers le commentaire
Partager sur d’autres sites

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) ?

Aide au téléchargement du cadastre dgfip-download-helper
Insertion de photos géolocalisées exif https://www.dropbox.com/s/gkf6o9ac2hxen97/exifscr.zip?dl=0
Script correction BUG SPDC V2, propriétaire département 21 et 22 : https://greasyfork.org/scripts/442400-spdcv2/code/SPDCV2.user.js

Lien vers le commentaire
Partager sur d’autres sites

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

...plus je sais où je suis, moins je sais où je vais....

Extrait d'une double interview simultanée d'une particule élémentaire.

Lien vers le commentaire
Partager sur d’autres sites

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é par Luna
Lien vers le commentaire
Partager sur d’autres sites

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).

Gilles Chanteau - gileCAD -
Développements sur mesure pour AutoCAD
ADSK_Expert_Elite_Icon_S_Color_Blk_125.png

Lien vers le commentaire
Partager sur d’autres sites

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é par Fraid

...plus je sais où je suis, moins je sais où je vais....

Extrait d'une double interview simultanée d'une particule élémentaire.

Lien vers le commentaire
Partager sur d’autres sites

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é, ...

Gilles Chanteau - gileCAD -
Développements sur mesure pour AutoCAD
ADSK_Expert_Elite_Icon_S_Color_Blk_125.png

Lien vers le commentaire
Partager sur d’autres sites

 

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

...plus je sais où je suis, moins je sais où je vais....

Extrait d'une double interview simultanée d'une particule élémentaire.

Lien vers le commentaire
Partager sur d’autres sites

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).

Gilles Chanteau - gileCAD -
Développements sur mesure pour AutoCAD
ADSK_Expert_Elite_Icon_S_Color_Blk_125.png

Lien vers le commentaire
Partager sur d’autres sites

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

Lien vers le commentaire
Partager sur d’autres sites

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).

Gilles Chanteau - gileCAD -
Développements sur mesure pour AutoCAD
ADSK_Expert_Elite_Icon_S_Color_Blk_125.png

Lien vers le commentaire
Partager sur d’autres sites

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)))

 

...plus je sais où je suis, moins je sais où je vais....

Extrait d'une double interview simultanée d'une particule élémentaire.

Lien vers le commentaire
Partager sur d’autres sites

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[ ...

Gilles Chanteau - gileCAD -
Développements sur mesure pour AutoCAD
ADSK_Expert_Elite_Icon_S_Color_Blk_125.png

Lien vers le commentaire
Partager sur d’autres sites

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

Lien vers le commentaire
Partager sur d’autres sites

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.

...plus je sais où je suis, moins je sais où je vais....

Extrait d'une double interview simultanée d'une particule élémentaire.

Lien vers le commentaire
Partager sur d’autres sites

Rejoindre la conversation

Vous pouvez publier maintenant et vous inscrire plus tard. Si vous avez un compte, connectez-vous maintenant pour publier avec votre compte.

Invité
Répondre à ce sujet…

×   Collé en tant que texte enrichi.   Coller en tant que texte brut à la place

  Seulement 75 émoticônes maximum sont autorisées.

×   Votre lien a été automatiquement intégré.   Afficher plutôt comme un lien

×   Votre contenu précédent a été rétabli.   Vider l’éditeur

×   Vous ne pouvez pas directement coller des images. Envoyez-les depuis votre ordinateur ou insérez-les depuis une URL.

Chargement
 Partager

×
×
  • Créer...

Information importante

Nous avons placé des cookies sur votre appareil pour aider à améliorer ce site. Vous pouvez choisir d’ajuster vos paramètres de cookie, sinon nous supposerons que vous êtes d’accord pour continuer. Politique de confidentialité