Challenge19

[(gile)]

On va essayer quelque chose qui me semble plus facile que le dernier et qui fait un peu appel aux connaissances en géométrie.

 

Il s'agit de faire une ou des routines pour déterminer si une liste de points décrit un polygone convexe, concave ou croisé.

 

http://img526.imageshack.us/img526/7858/polygonesyj7.png

 

Quelques précisions sur le classement des polygones par convexité

[Matt666]

Salut Gile !

On exclut les arcs dans les polylignes ?

 

Sinon il faudra le faire vlisp, nan ?

 

EDIT : En même temps un polygone avec un arc, c'est plus un polygone :P

 

[Edité le 21/12/2007 par Matt666]

[(gile)]

C'est pas la bousculade !!!

 

J'ai un peu regardé, c'est peut-être moins simple que je ne le pensais.

 

Donc, commençons par ce qui me semble le plus simple : déterminer si le polygone est croisé ou non.

Proposition d'algorithme :

- tester s'il existe une intersection entre p1 p2 et p3 p4, puis entre p1 p2 et p4 p5, puis entre p1 p2 et p5 p6 etc...

- si aucune intersection n'est trouvée refaire l'opération avec p2 p3 et le reste de la liste et ainsi de suite.

 

On a donc 2 boucles imbriquées...

[Bred]

J'ai un peu regardé, c'est peut-être moins simple que je ne le pensais.

Ben j'ai bêtement regardé en pensant que la solution seriat avec les angles... jusqu'à ce que je dessine un polygone convexe avec un des angles "aigus"... ce qui plante toutes mes bases...

 

[(gile)]

C'est pour ça que je conseille de commencer par le polygone croisé qui me semble plus facile à déterminer.

Un polygone convexe est un polygone qui n'est ni croisé ni concave (dixit wikipédia).

[Matt666]

Bah oui, il est dur ton challenge !!

 

Ca creuse, ca creuse....

 

A bientot !

Matt.

[bseb67]

Salut!

 

Bon tout d'abord bonne année à tous!Et surtout bonne santé.

Pour moi ce n'est pas trop le cas, j'ai fini l'année 2007 et débuté la 2008 avec la grippe :(,

que j'ai refillé à ma femme :cool:.

 

Retour sur le challenge.

J'ai du faire un truc de ce genre lors de mes cours à la fac. COmme le dit GIle, on peut chercher

le croisé en premier. Faire de bonnes boucles et un petit booléen pour stopper dès le premier

croisement trouvé (ou non si l'on veut compter le nombre de croisements).

 

Par contre, si mes souvenir sont bons, la proposition de bred sur les angles est la meilleure approche pour concave-convexe. Un concave comporte au moins un angle obtu, tandis que les convexes n'ont que des angles aigus.

 

Comme je suis encore en vacances, je n'attequerai le challenge que la semaine prochaine.

 

a+!

 

 

[Edité le 2/1/2008 par bseb67]

[(gile)]

Par contre, si mes souvenir sont bons, la proposition de bred sur les angles est la meilleure approche pour concave-convexe. Un concave comporte au moins un angle obtu, tandis que les convexes n'ont que des angles aigus.

:casstet: :casstet: :casstet:

 

Je ne pense pas...

Un triangle est toujours convexe et a, au plus, un seul angle obtu.

 

Je penserais plutôt à évaluer la position de tous les autres sommets par rapport à un segment (et ce, pour chaque segment bien sûr).

Voir ce challenge.

[bseb67]

Re,

 

J'ai fait une petit erreur sur le terme obtus, :cool:

La géométrie c'est un petit peu loin (bts en 2002).

Obtus c'est entre 90° et 180°, donc correction:

 

Un concave comporte au moins un angle

supérieur à 180°.

Il faut juste savoir le mesurer et le mesurer correctement.

 

 

[Edité le 2/1/2008 par bseb67]

[(gile)]

Voilà plus de 15 jours que j'avais lancé ce challenge et toujours aucune réponse...

 

Je donne donc une solution pour évaluer si la liste de points décrit un polygone croisé.

 

Il s'agit d'une routine appelant deux sous-routines récursives, ça laisse la porte ouverte pour écrire l'équivalent sous forme itérative ou quelque chose de différent.

 

La routine évalue si chaque segment (2 points successifs de la liste) ont une intersection avec chacun des autres segments. Elle retourne T si une intersection est trouvée, nil sinon. Les routines utilisent donc les opérateurs logiques and et or.

 

La première sous routine, SUBR1, requiert 3 arguments : 2 points et une liste de points.

Elle évalue si les deux points ont une intersection avec les deux premiers points de la liste et s'il n'y a pas d'intersection, refait l'évaluation avec les deuxième et troisième points de la liste et ainsi de suite jusqu'à ce qu'une intersection soit trouvée ou que la liste n'ait plus qu'un seul point.

 

La seconde sous routine, SUBR2, requiert un argument : une liste de points.

Elle fait passer les deux premiers points de la liste et la liste privée de ces points à SUBR1 pour trouver une intersection. Si aucune intersection n'est trouvée, le processus est renouvelé avec les deuxième et troisième points et le reste de la liste.

 

SUBR2 n'est pas suffisante pour une évaluation complète. Les deux routines doivent donc être intégrées à une routine principale, CROSSED-P, pour pouvoir évaluer si le dernier segment d'une polyligne fermée (dernier point au premier point) a ou non une intersection avec un des autres segments.

CROSSED-P appelle d'abord SUBR1 avec comme arguments les premiers et deuxième points et le reste de la liste, si aucune intersection n'est trouvée, elle appelle SUBR2 avec comme argument la liste dont on a fait passer le premier élément à la fin.

 

(defun crossed-p (l / subr1 subr2)

 (defun subr1 (p1 p2 l)
   (and (cdr l)
 (or (inters p1 p2 (car l) (cadr l) T)
     (subr1 p1 p2 (cdr l))
 )
   )
 )

 (defun subr2 (l)
   (and (cdddr l)
 (or (subr1 (car l) (cadr l) (cddr l))
     (subr2 (cdr l))
 )
   )
 )

 (or (subr1 (car l) (cadr l) (cddr l))
     (subr2 (cdr (append l (list (car l)))))
 )
) 

[lili2006]

Bonsoir à toutes et tous,

 

Et c'est ce bout de code qui sert à tout ça ???

 

Pfuuu, c'est balaise quand on maitrise.

 

Merci encore (gile) de tes explications.

[(gile)]

Salut lili2006,

 

Je ne suis pas sûr que ce ce soit d'une grande utilité, mais ça sert à évaluer si une liste de points, par exemple les sommets d'une polyligne, décrit un polygone croisé.

 

Par exemple avec les trois polylignes de l'image du début du sujet, l'expression :

 

(crossed-p (mapcar 'cdr (vl-remove-if-not '(lambda (x) (= (car x) 10)) (entget (car (entsel))))))

 

retournera nil pour les deux premières, T (true) pour la troisième.

 

[Edité le 7/1/2008 par (gile)]

[lili2006]

Bonsoir à toutes et tous,

 

Je ne suis pas sûr que ce ce soit d'une grande utilité,

 

Ah, qoui que,...

 

par exemple les sommets d'une polyligne, décrit un polygone croisé.

 

J'en ai eu l'utilité aujourd'hui, moi pour faire une Modélisation Numérique de Terrain (MNT), sans ce code, je n'aurai pas vu le croisement de deux polylignes constituant un de mes contours à exclure du (MNT).

 

Comme quoi, tout sert,...

 

(crossed-p (mapcar 'cdr (vl-remove-if-not '(lambda (x) (= (car x) 10)) (entget (car (entsel))))))

Impecc !!!

 

Merci encore.

[(gile)]

Comme les réponses n'affluent toujours pas (on peut parler d'un véritable "bide"), le donne mes réponses pour tester si la liste décrit un polygone convexe.

 

Une première, qui évalue pour chaque segment qur tous les sommets son "à droite" du segment (si celà s'avérère faut pout le premier segment et le troisième sommet, la liste est inversée).

 

(defun convex-p	(lst / subr1 subr2)
 
 (defun subr1 (a e l)
   (or	(null l)
(and (= ref (	     (subr1 a e (cdr l))
)
   )
 )
 
 (defun subr2 (l)
   (or	(null (cddr l))
(and (subr1 (angle (car l) (cadr l)) (car l) (cddr l))
     (subr2 (cdr l))
)
   )
 )
 
 (setq lst (append lst (list (car lst))))
 (or (		       (angle (car lst) (cadr lst))
	    )
       )
       1e-14
    )
     (setq lst (reverse lst))
 )
 (subr2 lst)
) 

 

On peurt aussi se contenter d'évaluer tous les segments consécutifs, pris 2 par 2 "tournent dans le même sens". Dans ce cas il faut d'abord écarter les polygones croisés : un polygone étoilé remplirait cette condition.

 

(defun convexe (lst)
 (apply '=
 (mapcar
   '(lambda (p1 p2 p3)
      (	    )
   lst
   (append (cdr lst) (list (car lst)))
   (append (cddr lst) (list (car lst) (cadr lst)))
 )
 )
) 

 

Une fonction test pour la synthèse :

 

(defun c:test (/ ent lst)
 (and
   (setq ent (car (entsel)))
   (= (cdr (assoc 0 (entget ent))) "LWPOLYLINE")
   (setq lst (mapcar 'cdr
	      (vl-remove-if-not
		'(lambda (x) (= (car x) 10))
		(entget ent)
	      )
      )
   )
   (cond
     ((crossed-p lst) (alert "Croisé"))
     ((convexe lst) (alert "Convexe"))
     (T (alert "Concave"))
   )
 )
)