[Challenge]Quickhull

[VDH-Bruno]

@didier, Oui bravo, ça fonctionne, tu as implémenté l’algorithme de Graham's il me semble, il te reste encore a implémenter l'algorithme Quickhull

[(gile)]

@didierBravo ! Pas si 'impératif' que ça.
La réponse de @VDH-Bruno ne t'a pas fait d'ombre, tu as implémenté le "parcours de Graham" et Bruno un "quickhull".

Voici ma réponse :
 

;; quickhull
;;
;; La fonction loop est celle qui implémente l'algorihme général
;; (loop p1 p2 pts) cherche dans pts des points à droite du segment p1 p2.
;; - S'il y en a (l), on prend le point le plus éloigné (pt) et on concatène
;;   (loop p1 pt l) avec (loop pt p2 l)
;; - S'il n'y en a pas on garde p2.
;;
;; La fonction filter
;; (filter p1 p2 pts 'pt) renvoie les points de pts qui sont à droite de p1 p2
;; et assigne à pt le point le plus éloigné
;;
;; La fonction area est utilisée pour déterminer si les points sont à droite
;; et quel est le plus éloigné.
;; (area p1 p2 pt) renvoie l'aire algébrique du triangle p1 p2 pt.
;; Cette aire est négative si pt est strictement à droite de p1 p2.
;; Elle est proportionnelle à la distance entre pt et le segment p1 p2.

(defun quickhull (pts / area filter loop lst minX maxX)
  (defun area (p1 p2 p3)
    (- (* (- (car p2) (car p1)) (- (cadr p3) (cadr p1)))
       (* (- (cadr p2) (cadr p1)) (- (car p3) (car p1)))
    )
  )
  (defun filter	(p1 p2 pts outparam / ref a lst)
    (setq ref 0)
    (foreach p pts
      (and (minusp (setq a (area p1 p2 p)))
	   (setq lst (cons p lst))
	   (< a ref)
	   (setq ref a)
	   (set outparam p)
      )
    )
    lst
  )
  (defun loop (p1 p2 pts / l pt)
    (if	(setq l (filter p1 p2 pts 'pt))
      (append (loop p1 pt l) (loop pt p2 l))
      (list p2)
    )
  )
  (setq	lst  (mapcar 'car pts)
	minX (assoc (apply 'min lst) pts)
	maxX (assoc (apply 'max lst) pts)
  )
  (append (loop minX maxX pts) (loop maxX minX pts))
)

 

Modifié le 14 avril 2021 par (gile)
code corrigé suite à la pertinente remarque de VDH-Bruno

[(gile)]

Un nouvelle en F# (pas plus efficiente, mais un peu plus concise).
 

let quickhull_ (pts: Point2d list) =
    let area (p1: Point2d) (p2: Point2d) (p3: Point2d) =
        ((p2.X - p1.X) * (p3.Y - p1.Y)) - ((p2.Y - p1.Y) * (p3.X - p1.X))
    let rightPts p1 p2 pts =
        match List.choose(fun p -> 
            let a = area p1 p2 p
            if a < 0. then Some (a, p) else None) pts with
        | [] -> None
        | lst -> Some (lst |> List.minBy fst |> snd, lst |> List.map snd)
    let rec loop p1 p2 pts =
        match rightPts p1 p2 pts with
        | None -> [p1]
        | Some (p, l) -> loop p1 p l @ loop p p2 l
    let minX = pts |> List.minBy (fun p -> p.X)
    let maxX = pts |> List.maxBy (fun p -> p.X)
    loop minX maxX pts @ loop maxX minX pts

 

[Curlygoth]

(je vais me faire insulter mais c'est pas grave je vais le dire quand meme : )

Le F# Me fait pensé un peu au VBA / VB.NET c'est rigolo ^^

Si la démo de didier sur ces 10.000 points est rapide comme ça... le vba ne fera pâs mieux ! par contre je vais aller au bout de ce challenge et vous donnez du coup le temps nécessaire au code VBA pour traiter 10.000 point voir plus ! parce que la effectivement je pense qu'on pourra comparer "l'efficience de deux code"

J'ai des entetiens a préparer, un véhicule à retaper donc je le ferais pas de suite mais je le ferais ! 

 

[didier]

Bonjour @(gile) @VDH-Bruno

Votre "bravo" me touche, je vous remercie sincèrement.

En effet, je me suis un peu tracassé la tête, on trouve encore la trace de mon "impérativité" dans les définitions de L3,L4...
De toute façon j'ai un résultat qui me plaît, maintenant s'il plaît aux autres et qu'il est efficient c'est "la cerise sur le ponpon".

On se met d'accord pour le prochain challenge au niveau du dépôt des réponses, ça marche ?
Je ne suis pas certain du tout de participer au prochain, car le sujet me parle ou pas et décide de mon implication (si je sens que je peux répondre in fine)

À tous :
Il est possible que je dédie une page de "da-code" à ces sujets, ai-je l'autorisation de vous citer et d'intégrer votre code ?

Amicalement

PS: Je dois vous quitter car il faut que je cherche des pokemon à imprimer pour faire du coloriage, on n'a pas une vie facile ...
 

[VDH-Bruno]

@(gile) Clap clap clap, chapeau bas, pour la concision je ne crois pas que l'on puisse faire mieux, l'air algébrique (qui donne la position, la surface et le donc point le plus éloigné) "mais c'est bien sur" cela ne m'a même pas effleuré l'esprit, pourtant je le sais et je l'ai écrit donc sur ce coup je m'en amuse (c'est pas faute d'avoir réfléchi pour le faire en un passage, set était bien présent en tête si je trouvais ce moyen😉).

Je n'ai aucun regret je m'étais imposé 1h pour écrire le quickHull, j'ai débordé cela m'a pris 1h45, c'est le maximum que je pouvais faire dans le temps imparti. D'avoir participé me permet d’apprécié au mieux ces lignes de codes, un grand MERCI à toi 

[VDH-Bruno]

1 hour ago, didier said:

Il est possible que je dédie une page de "da-code" à ces sujets, ai-je l'autorisation de vous citer et d'intégrer votre code ?

Bonjour @didier

Bien que je sois intimement convaincu que tu trouveras (à raison) toujours plus d'inspiration dans les lignes de (gile) que dans les miennes, si des fois il y en a une ou deux qui te conviennent en ce qui me concerne tout ce qui est sur les forums est libre de droit, être repris est toujours une forme de reconnaissance😉

Pour une date de dépôt je suis plus mitigé, l'esprit d'un challenge est un jeu entre vitesse d'écriture et optimisation des lignes de code, personnellement je n'ai pas d'état d'âme à poster rapidement si je pense que la solution n'est pas optimal (car elle sera facilement détrôner Cf ma réponse sur ce challenge). Par contre si je crois avoir là solution, je temporise au maximum avant de poster, bien qu'à ce petit jeu je me fait bien souvent prendre et m'en amuse😄

Il m'est aussi arrivé de faire une proposition au hasard d'un code, bien après l'émission d'un challenge, pour moi il n'y pas de date limite de temps.

A+ Bruno

[hey_bapt]

Bravo messieurs,

 

désolé de ne pas participer, je ne sais pas coder, je n'avais déjà pas compris le problème et pour moi, "F#" signifie Fa dièse, en musique...

Bref je suis toujours admiratif de voir cette capacité de création de routine, et me dit que certaines routines me feraient très certainement gagner des heures...

 

Cordialement.

[Fraid]

Bonjour,

Chacun vois les challenges comme ils veulent.

C'est pour moi une occasion de programmer en m'amusant.

je ne cherche pas la performance, juste atteindre un but.

La, je n'avais pas beaucoup de temps non plus, et pas envie de tripoter des listes de points.

je suis donc partis avec l'algorithme Fraidskull (voir Strange n°666)

Je ne pense pas qu'il serve un jour de référence....hihihi

Sinon, Didier, je pense que tu peux évité de demander permission d'utilisé du code qui est déjà partagé.

Si on diffuse, c'est pour cela, n'est ce pas?

Sinon, bravo à tous, pour ces exemples de concisions.

[(gile)]

4 hours ago, Curlygoth said:

Le F# Me fait pensé un peu au VBA / VB.NET

Je ne vois pas bien pourquoi, mais si tu arrives à implémenter cet algorithme en 15 lignes de VB(A) normalement formaté, je veux bien manger mon chapeau.

 

2 hours ago, didier said:

ai-je l'autorisation de vous citer et d'intégrer votre code ?

Évidemment, quelle question.

Je suis ravi que ceux qui ont participé se soient amusés, c'est aussi mon cas. Mais rien n'est arrêté, il y a certainement d'autres façons de faire et d'autres langages à explorer...

[didier]

Bonjour @(gile)

Demander la permission est la moindre des choses, effectivement si on diffuse sur un site public on la donne implicitement, cela ne m'empêche pas de te remercier de cette confirmation.
Toutefois, je ne suis pas certain de le faire de sitôt, car le temps manque et j'ai trois idées par minute...

Tu as raison, je vais tenter en C#, afin de me dégourdir les doigts et la mémoire de ce langage

Amicalement
 

[Curlygoth]

Quote

Je ne vois pas bien pourquoi, mais si tu arrives à implémenter cet algorithme en 15 lignes de VB(A) normalement formaté, je veux bien manger mon chapeau.

Soit tranquille tu ne le mangeras pas XD

 

Quote

je ne cherche pas la performance, juste atteindre un but.

Je suis plus dans cette optique là ^^ (enfin pour les challenges)

[Erased]

Salut,

 

votre challenge me fait penser à feu "Jeu Autocad du mois" mis en place par Eric sur son site, il y a fort longtemps, (https://www.caderix.com/journal/spip.php?rubrique13) mais qu'il avait arrêté faute de temps, à mon grand regret. Pour ce challenge nouvelle version, je ne participerai pas : je ne sais pas coder et je n'ai plus d'accès à Autocad, mais je continue de vous lire par curiosité et connaître les possibilités de réalisations.

 

Bonne continuation.

 

PS  : puisque je le cite, j'en profite pour le féliciter (avec du retard) ! Bravo Eric https://www.caderix.com/journal/spip.php?article527

 

Erased.

 

[VDH-Bruno]

 Bonjour @(gile),

Pour le retour (et la petite blague), en détaillant hier soir le fonctionnement de ton QuikHull, je me suis aperçu que tu générais des sommets superposés, graphiquement tu as le bon nombre de coté, mais trop de sommets. 

Pour t'en convaincre en exemple sur polygone convexe à 11 cotés généré avec la commande test,  la ligne de code suivante m'indique 17 sommets....

_$ (cdr (assoc 90 (entget (car (entsel)))))
17

 

J'ai mis un moment à comprendre, mais c'est tout bête, c'est la variable pt qui fait nous un effet de bord... dans le code tu as omis de la localisé dans la fonction appelante loop, une fois fait tout rentre dans l'ordre.😊

A+ Bruno

[(gile)]

Bravo pour ce diagnostic !

[VDH-Bruno]

Bonjour,

Je reviens sur le sujet pour proposer mon 2ème jet de la fonction QuickHull

Dans cette deuxième version j'ai voulu garder l'esprit du premier algorithme, à savoir la fonction filtre les points à droite de la droite (ptA ptB), puis filtre les points à droite de la droite (ptB ptC) parmi les points à gauche de la droite (ptA ptB). De ce fait les aires algébriques à droite de la droite (ptA ptB) ne sont calculé qu'une seule fois.

Voilà j'ai essayé pour le jeu d'allier l'efficience (avec un gain modeste), sans trop sacrifier la concision des lignes de code donné par (gile)

(defun QuickHull (pts / area getQuickHull lst minX maxX)
  (defun area (p1 p2 p3)
    (- (* (- (car p2) (car p1)) (- (cadr p3) (cadr p1)))
       (* (- (cadr p2) (cadr p1)) (- (car p3) (car p1)))
    )
  )
  (defun getQuickHull (ptA ptB ptC pts / a refAB refBC ptAB ptBC lstAB lstBC)
    (if	pts
      (progn
	(setq refAB 0 refBC 0)
	(foreach p pts
	  (if (minusp (setq a (area ptA ptB p)))
	    (and (setq lstAB (cons p lstAB))
		 (< a refAB)
		 (setq refAB a)
		 (setq ptAB p)
	    )
	    (and (minusp (setq a (area ptB ptC p)))
		 (setq lstBC (cons p lstBC))
		 (< a refBC)
		 (setq refBC a)
		 (setq ptBC p)
	    )
	  )
	)
	(append	(getQuickHull ptA ptAB ptB lstAB) (getQuickHull ptB ptBC ptC lstBC))
      )
      (list ptA)
    )
  )
  (setq	lst  (mapcar 'car pts)
	minX (assoc (apply 'min lst) pts)
	maxX (assoc (apply 'max lst) pts)
  )
  (getQuickHull minX maxX minX pts)
)

A+ Bruno

[(gile)]

Joli !

[VDH-Bruno]

1 hour ago, (gile) said:

Joli !

Merci pour la façon suivante de lancer le traitement: 

4 hours ago, VDH-Bruno said:

(getQuickHull minX maxX minX pts)

Je suis assez d'accord, par contre pour la partie qui suit je suis encore mitigé:

4 hours ago, VDH-Bruno said:

(setq refAB 0 refBC 0) (foreach p pts (if (minusp (setq a (area ptA ptB p))) (and (setq lstAB (cons p lstAB)) (< a refAB) (setq refAB a) (setq ptAB p) ) (and (minusp (setq a (area ptB ptC p))) (setq lstBC (cons p lstBC)) (< a refBC) (setq refBC a) (setq ptBC p) )

J'ai essayé des truc plus ou moins farfelu dans le WE, pour en faire quelque chose d’élégant: factorisation, récursion mutuelle, utilisation de set, imbrication de or et and etc.. A par obscurcir et compliquer le code j'ai pas réussi à traiter cette partie mieux que ça..

[Curlygoth]

fausse alerte...

ne prends pas en compte certains exceptions

 

[didier]

Bonjour @Curlygoth

Je ne comprends malheureusement pas ce que tu écris.

Est-il possible de faire des messages un peu moins sibyllins ? Il n'y pas de taxes sur l'utilisation des touches du clavier.
Une explication, un développement de la remarque facilite la lecture et la compréhension.

En reprenant ton dernier message je lis : Fausse alerte, de quelle alerte parles-tu ?
Et ensuite : ne prends pas en compte certaines exceptions de quelles exceptions est-il question ?
Je ne dis pas que tes remarques sont infondées, je dis qu'elles sont obscures.

Amicalement

[Curlygoth]

Bonjour didier

J'ai malheureusement écrit le code de mon quickhull un peu vite...

donc c'est une

Citation

"fausse alerte"

car mon code

Citation

ne prend pas en compte certaines exceptions..

. mais je me rapproche de la vérité 😉