Discussion :

[nkd]

Bonjour

Je cherche de l'aide concernant un problème de numérotation de polygones.
le voici :

J'ai plusieurs polygones à l'écran et je cherche un algo efficace en vue de numéroter automatiquement ces polygones
- en partant par le plus haut et dans le sens des aiguilles d'un montre.

je signale que ces polygones sont disposés aléatoirement et peuvent avoir une orientation et une forme quelconques.

(ils ne sont pas rangés comme les quadrillages d'un cahier )

[Kangourou]

Salut,

Si tu consideres le centre de gravite de chaque polygfone, c'est peut-etre plus simple pour trier non ? (calcul d'angles et de distances simplifies)

la methode dont tu parles suggere un algo d'enveloppe convexe, mais dans ce cas tu perdrais les polygones 'a l'interieur'.

une idee pour la numerotation :
- tu choisis un point pour chque polygone (centre de gravite, point le pluis haut ...)
- le point le plus haut est le premier de la numertotation
- tu vcalcules les angles de tous les points avec ce premier point
- tu tries par angle croissant
- tu peux resoudre les ambiguites d'angles egaux en fonction de la distance de chaque point au point origine.

c'est d'apres ce que j'ai compris de ton probleme, j'espere que c'est a peu pres ce que tu cherches.
A+

[nkd]

salut kangourou
merci pour ton algo, je fais rapidement un test et je te fais signe

[nkd]

salut kangourou

j'ai mis en place l'algo que tu m'as conseillé.
Resultat: ça marche mais il y a certains polygones à l'intérieur qui ont un numéro trop grand vu leurs positions.

Supposons que l'ensemble des polygones donne une enveloppe convexe qui a la forme d'un pistolet qui vise au sol. Les polygones se trouvant au niveau de la gachette doivent être numéroter bien avant ceux qui sont sur la trajectoire de la cartouche.

L'angle que donne ce polygone(centre gravité sous entendu) par rapport au point le plus haut est plus petit que celui que donne le polygone gachette.

On ne peux pas avoir un polygone n°8 qui se trouve vers le bas et avoir le n°9 en haut. Selon l'algo c'est possible puisque c'est l'angle qui est prioritaire


N'ya t-il pas un moyen d'uniformiser tous ça partant du même principe angulaire ?
ou
Que faire pour ces cas particuliers qui font flancher l'algo ?

[nkd]

Salut kangourou
j'ai resolu le second problème. Comment ?

Je divise l'ensemble du fichier en 4 zones rectangulaires . Pour m'y prendre je calcule le centre (Xm,Ym) du fichier en recherchant les extrema (Xmax,Xmin,Ymax,Ymin). Je numerote les zones partant du plus haut et de la droite vers la gauche.

Je fais un tri (pour stocker les polygones dans les zones) qui me donne 4 sous fichiers : le polygone retenu dans une zone est celui qui a son centre de gravité à l'interieur de cette zone.

Ensuite je recupère chaque zone dans laquelle j'applique ton algo : c-a-d je tri les polygones en fonction des angles et si les angles sont égaux je prends celui qui a la plus petite distance.


Pour finir je renumerote mes polygones en fonction du numero des zones,
c-a-d les polygones de la zone 1 sont numerotés ensuite ceux de la zone 2 et ainsi de suite.

Merci Kangourou pour ton aide, ça m'a permis de dégrossir le sujet
A+

[Kangourou]

de rien !

on est la pour s'aider...
d'ailleurs je crois que je t'avais promis un bon de code sur un autre post , faut que j'y pense ...

A+

[nkd]

salut kangourou

stp essaie de reflechir à mon second sujet que j'ai nommé numerotation de polygone n°2 posté depuis le 04 avril

merci